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

[Dmitry Tkachenko]

В линейно связном множестве $L$ петлёй будем называть непрерывное отображение $f \colon [0,1] \to L,$ такое, что $f(0)=f(1)$ и $\forall x,y\in (0,1), x\ne y \colon f(x) \ne f(y).$

Подмножество $M$ линейно связного множества $L$ назовём односвязным, если оно линейно связно и, либо в нём нет петель, либо любая петля в нём стягивается в точку.

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

Интересны множества в $\mathbb{R}^2, \mathbb{R}^3.$ Например, кольцо в $\mathbb{R}^2$ можно представить в виде объединения двух односвязных подмножеств. Также как и тор в $\mathbb{R}^3.$ Мне сложно представить как это можно сделать со скатертью Серпинского. Возможно, это и есть пример к задаче.

Интересно рассмотреть планарные графы, но не совсем в привычном понимании. Уточняю: когда мы рассматриваем какой-то граф, например, квадрат, то, пытаясь представить его в виде объединения односвязных подмножеств, можем производить операцию типа: в одной из вершин отсоединяем сторону квадрата от другой стороны, но сама вершина остаётся только на одной из этих сторон, а на другой (в том месте, где была вершина) остаётся проколотая точка.

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

[kp9r4d]

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

[iancaple]

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

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

Планарность, очевидно, ни при чем. Пропущено условие, что исходный граф связен. А еще что пропущено?

[Dmitry Tkachenko]

iancaple, да, граф должен быть линейно связным.
В каждой вершине отсоединяем один из концов петли (на этом конце остается выколотая точка). Затем, в одной из вершин отсоединяем сторону (также, у отсоединенной стороны выколотая точка). Получим односвязное множество.

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

[iancaple]

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

iancaple, да, граф должен быть линейно связным.
В каждой вершине отсоединяем один из концов петли (на этом конце остается выколотая точка). Затем, в одной из вершин отсоединяем сторону (также, у отсоединенной стороны выколотая точка). Получим односвязное множество.

Но не связное, и это неинтересно, эдак можно повыбрасывать все вершины или все ребра, смотря которых больше, и останется точно односвязное. Действительно, любой цикл по графу должен содержать хоть какие-то вершины и какие-то ребра, а если одной из этих категорий нет вообще...Я думал, Вы запретите ребра-петли, тогда ответ неясен пока.
"Гипотеза" чем-то похожа на теорему существования остовного дерева в любом связном неориентированном графе, разница в допустимых операциях: в теореме выбрасываются ребра, не трогая вершин, а здесь - ребро и одна из инцидентных ему вершин.

[Munin]

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

В каждой вершине отсоединяем один из концов петли (на этом конце остается выколотая точка). Затем, в одной из вершин отсоединяем сторону (также, у отсоединенной стороны выколотая точка). Получим односвязное множество.

И что? Как вы его потом объединять будете, и с чем? Вы не путаете понятия объединения и склейки?

[Dmitry Tkachenko]

iancaple, хорошо, давайте запретим рёбра-петли и поставим вопрос таким образом: всегда ли планарный граф можно разбить на два дерева? Но, мы сейчас рассматриваем граф не в обычном понимании. А точнее: отсоединения одно ребро от другого, вершина остаётся лишь на одном из них, а на другом --- выколотая точка. То есть, введена некоторая топология.

Кружочки --- это выколотые точки. Соединяем $C_1$ с $C$, $B_1$ с $B$ и $A_1, A_2$ с $A.$

[Munin]

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

А точнее: отсоединения одно ребро от другого, вершина остаётся лишь на одном из них, а на другом --- выколотая точка. То есть, введена некоторая топология.

Точнее, не введена, а нарушена. Изначально на графе уже была топология, топология одномерного клеточного пространства (CW-комплекса).

[iancaple]

Ну конечно то что у Вас на картинке , можно и с любым связным графом проделать, пока не превратится в дерево. Берем любой цикл и разрываем его, так как это был цикл, связность не нарушится. Все кончится деревом, с поправкой, что некоторые висячие вершины дерева "выколотые".
Я пока не увидел тут "олимпиадной задачи", а просто обсуждение всего вообще.

[kp9r4d]

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

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

А точку, через которую провели, мы просто выкинули?

[Dmitry Tkachenko]

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

Ну конечно то что у Вас на картинке , можно и с любым связным графом проделать, пока не превратится в дерево. Берем любой цикл и разрываем его, так как это был цикл, связность не нарушится. Все кончится деревом, с поправкой, что некоторые висячие вершины дерева "выколотые".
Я пока не увидел тут "олимпиадной задачи", а просто обсуждение всего вообще.

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

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

это можно сделать со скатертью Серпинского

kp9r4d, прошу прощения! Я имел в виду следующее:


Munin, не совсем понимаю, что именно нарушается. Я сейчас не рассматриваю граф в привычном смысле. Сейчас это определённые кривые в $\mathbb{R}^2.$

Хмм... А как Вы введёте структуру CW-комплекса для графа, у которого в единственной вершине счётное количество вложенных друг в друга петель и больше ничего?

-- 01.10.2015, 18:11 --

Ааа, я понял. Munin, Вы правы. Просто, как я уже написал выше, давайте прекратим рассматривать графы, так как это сбивает с толку. Например, если рассмотреть конструкцию "в единственной вершине счётное количество вложенных друг в друга петель" в $\mathbb{R}^2$, то она вроде как не будет эквивалентна никакому CW-комплексу. В смысле гомотопически.

[Munin]

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

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

Это, кажется, называется "гавайская серьга". В общем, и графом её назвать можно с трудом.

[Dmitry Tkachenko]

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

Я пока не увидел тут "олимпиадной задачи", а просто обсуждение всего вообще.

Вот же она:

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

В линейно связном множестве $L$ петлёй будем называть непрерывное отображение $f \colon [0,1] \to L,$ такое, что $f(0)=f(1)$ и $\forall x,y\in (0,1), x\ne y \colon f(x) \ne f(y).$

Подмножество $M$ линейно связного множества $L$ назовём односвязным, если оно линейно связно и, либо в нём нет петель, либо любая петля в нём стягивается в точку.

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

-- 01.10.2015, 22:36 --

Munin, спасибо! Прочитал о "гавайской серьге". Именно такой пример я и имел в виду, не знал, что он имеет характерное название.

[Dmitry Tkachenko]

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

Я пока не увидел тут "олимпиадной задачи", а просто обсуждение всего вообще.

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

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

[iancaple]

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

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

Исправляетесь помалу, наверное в этом преимущество форумов перед всякими там блогами. Добавить к формулировке теперь надо всего 3 пункта:1)неодносвязный (а то дерево одно) 2)без петель 3) без дублирующих друг друга ребер (короче, простой неориентированный)
Вот тут раскрашены внутренние области
и видим, что разность числа цветных и белых областей 5. Разбиение на 2 дерева можно представить как непрерывный извилистый разрез, пересекающий некоторые ребра, расположение начала и конца разреза в цветных областях может компенсировать 2 единицы из этой разности, выйти временно в неограниченную область можно не чаще чем дважды... не хватает смен цвета.