Острием по топологии или в поисках односвязности

[Dmitry Tkachenko]

iancaple, я правильно понимаю, что Вы пытаетесь построить пример линейно связного множества (не графа), которое невозможно представить в виде объединения двух односвязных подмножеств?

Это я к тому, что если закрашенное жёлтым --- тоже рассматриваемое множество, то можно вытащить средний и тот, что по диагонали правее:

(зелёные точки на вырезанном - это выколотые точки)

Для графа такие конструкции не подойдут, ведь, можно отделить все внутренности от оболочки, а с ними уже делать всё, что хочешь:

[Munin]

Вы продолжаете путать деление на подмножества и разрывы/склейки топологии. С такой подменой понятий, конечно же, ответ на ваш вопрос отрицательный, и даже двух "подмножеств" не надо.

[iancaple]

Действительно, этот мой пример с решеткой ничего не доказывает, так как разрез не обязан быть простым путем, допускаются "Т-образности".
Но и самой задачи уже нет.

[Dmitry Tkachenko]

Munin в сообщении #1059144 писал(а):

конечно же, ответ на ваш вопрос отрицательный

Вы можете доказать это?


Вот три картинки. На первой изображен граф с топологией, индуцированной с $\mathbb{R}^2$. На второй изображено его разбиение на два дерева. На третей изображен односвязный граф, который можно получить из графа, что на первой картинке, отсоединяя рёбра, но, при этом, его нельзя разбить на два дерева.

Munin в сообщении #1059144 писал(а):

даже двух "подмножеств" не надо.

Я хочу сказать, что отсоединяя рёбра можно добиться дерева, но это не значит, что мы получим разбиение исходного графа на два дерева.

-- 04.10.2015, 23:44 --

Munin в сообщении #1059144 писал(а):

С такой подменой понятий

Приведите, пожалуйста, правильные понятия. Хочу понять, где я их подменяю.

-- 04.10.2015, 23:51 --

iancaple в сообщении #1059163 писал(а):

Но и самой задачи уже нет.

Вы можете доказать или опровергнуть утверждение ниже?

Утверждение. Линейно связный, неодносвязный, простой неориентированный граф с топологией, индуцированной с $\mathbb{R}^2$ (то есть разрешается оставлять рёбра открытыми), всегда можно представить в виде двух деревьев.

[Munin]

Dmitry Tkachenko в сообщении #1059190 писал(а):

На третей изображен односвязный граф, который можно получить из графа, что на первой картинке, отсоединяя рёбра, но, при этом, его нельзя разбить на два дерева.

Вы, наверное, слова "дерево" не понимаете. "Отсоедините" от вашего третьего "графа" одно ребро или даже одну концевую точку - вот и будет вам второе дерево.

Dmitry Tkachenko в сообщении #1059190 писал(а):

Приведите, пожалуйста, правильные понятия.

Я уже привёл.

[Dmitry Tkachenko]

Munin в сообщении #1059196 писал(а):

"Отсоедините" от вашего третьего "графа" одно ребро или даже одну концевую точку - вот и будет вам второе дерево.

Это будет разбиение третьего графа на два дерева, а не первого.

Munin в сообщении #1059196 писал(а):

Я уже привёл.

Тогда я повторюсь: Вы можете доказать или опровергнуть утверждение ниже?

Утверждение. Линейно связный, неодносвязный, простой неориентированный граф с топологией, индуцированной с $\mathbb{R}^2$ (то есть разрешается оставлять рёбра открытыми), всегда можно представить в виде двух деревьев.

-- 05.10.2015, 01:24 --

Dmitry Tkachenko в сообщении #1059190 писал(а):

Вот три картинки. На первой изображен граф с топологией, индуцированной с $\mathbb{R}^2$. На второй изображено его разбиение на два дерева. На третей изображен односвязный граф, который можно получить из графа, что на первой картинке, отсоединяя рёбра, но, при этом, его нельзя разбить на два дерева.

Да, тут я не правильно выразил идею. Должно быть так:

На третей изображен односвязный граф, который можно получить из графа, что на первой картинке, отсоединяя рёбра, но, при этом, его нельзя разбить на два дерева так, чтобы это было разбиение первого графа на два дерева.

[NSKuber]

Dmitry Tkachenko в сообщении #1059203 писал(а):

На третей изображен односвязный граф, который можно получить из графа, что на первой картинке, отсоединяя рёбра, но, при этом, его нельзя разбить на два дерева так, чтобы это было разбиение первого графа на два дерева.

Брррр, а почему это не будет разбиением первого графа на два дерева?
Пусть третий граф получен из первого последовательностью действий (отсоединений) $F$. Как было сказано, третий граф одним действием $G$ можно разбить на два дерева. Тогда последовательность действий $H=FG$ (конкатенация) разбивает первый граф на два дерева. И предложенное разбиение третьего на два дерева тем самым является и разбиением первого графа на два дерева.
В какой момент превращения графа из первого в третий вы запрещаете ему как-либо относиться к первому?

[iancaple]

Dmitry Tkachenko в сообщении #1059190 писал(а):

Вы можете доказать или опровергнуть утверждение ниже?
Утверждение. Линейно связный, неодносвязный, простой неориентированный граф с топологией, индуцированной с $\mathbb{R}^2$ (то есть разрешается оставлять рёбра открытыми), всегда можно представить в виде (теоретико-множественной суммы) двух (непересекающихся) деревьев.

Конечно.
1.По теореме существования остовного дерева возьмем это дерево. Это связный односвязный подграф, содержащий все вершины исходного графа. Значит, все ребра графа, не входящие в остовное дерево, соединяют две уже имеющиеся вершины дерева. Их можно представлять как ребра, ведущие в новые висячие вершины, добавление новых висячих вершин ("листьев") и ребер к ним оставляет дерево-деревом.
2.Получено представление графа в виде одного дерева. Любое дерево содержит хотя бы одну висячую вершину. Будем считать ее, вместе с ведущим к ней открытым ребром, вторым деревом. Например, на третьей Вашей картинке можно отделить правое верхнее ребро в качестве "второго дерева"

[Munin]

Dmitry Tkachenko в сообщении #1059203 писал(а):

Тогда я повторюсь: Вы можете доказать или опровергнуть утверждение ниже?

Поскольку вы решили повторяться, а не слушать, что вам говорят, то обращаюсь к модераторам, а из разговора выхожу.

[Lia]

Ну а что модераторы. Dmitry Tkachenko, скажите, Ваш третий граф на картинке - дерево?

[Dmitry Tkachenko]

Lia, да.

iancaple, основная задача вот эта:
Задача. Существует ли линейно связное множество $L,$ которое можно представить в виде (теоретико-множественной суммы) не меньше, чем трёх, односвязных (непересекающихся) подмножеств.

[Munin]

Dmitry Tkachenko
В таком случае, приведите определения графа и дерева.

[iancaple]

Dmitry Tkachenko в сообщении #1059702 писал(а):

основная задача вот эта:
Задача. Существует ли линейно связное множество $L,$ которое можно представить в виде (теоретико-множественной суммы) не меньше, чем трёх, односвязных (непересекающихся) подмножеств.

В смысле -меньше трех нельзя? Вряд ли.
Одна из версий скатерти Серпинского - линейно связное, неодносвязное множество, являющееся объединением контура единичного квадрата и замкнутых крестов всевозможных рангов. Одно линейно связное множество определю как дерево с бесконечным числом ребер, построенное так, как на рисунке, вместе с построением скатерти. Тогда дополнение скатерти до него тоже односвязно (любой замкнутый путь на скатерти, не стягиваемый в точку, пересекается с построенным деревом)

Подобным образом (строя одно из множеств разбиения как дерево), мне кажется, можно обойтись и с версией скатерти, в которой кресты -открытые, а также с линейно связным множеством "квадрат, из которого выброшены все рациональные точки".

(Оффтоп)

Несмотря на отсутствие строгости в теме (происходящее от недостатка квалификации хоть у Dmitry Tkachenko, хоть у меня), она может тянуться сколь угодно долго сразу по двум путям: 1)поиск смысла, а потом поиск строгости 2) поиск строгости, а потом смысла...

[Dmitry Tkachenko]

iancaple в сообщении #1059837 писал(а):

Несмотря на отсутствие строгости в теме (происходящее от недостатка квалификации хоть у Dmitry Tkachenko, хоть у меня), она может тянуться сколь угодно долго сразу по двум путям: 1)поиск смысла, а потом поиск строгости 2) поиск строгости, а потом смысла...

Существует ли линейно связное множество в $\mathbb{R}^2,$ которое нельзя представить в виде объединения двух односвязных подмножеств? Под односвязным подмножеством понимаем линейно связное множество, в котором любая петля стягивается в точку.

[Munin]

Существует, вам такие были предъявлены, см., например, картинку с жёлтыми квадратиками, или первую из трёх картинок в post1059190.html#p1059190