Хи для графа. Как найти без вложения?

[Nartu]

В этом и суть. (задача не учебная)
Сам я смотрел книги Оре("Графы и их применение", "Теория Графов"), которые советовали в соответствующем разделе. Я, наверное слепой и не увидел там такой темы.

В общем я пришел к выводу, что надо использовать "мягкость" графа: "покрутить", "повертеть" и минимизировать неустранимые пересечения рёбер на плоскости.
Пусть их количество будет $N$. В принципе именно в них и должны быть "дырки" поверхности рода $N$, куда граф приятно вложится. Конечно, граф неориентирован, хотя это, наверное и не важно...

Здесь был раздел с моим наблюдением того, что кол-во граней неплоского графа $G$ равно кол-ву граней плоского $H$, который получится удалением пересекающихся рёбер $G$, приведённого к минимуму пересечений. Я ошибался.
Это работало для $K_{3,3}$, $K_5$ и виновника этого сообщения(по-моему уже приведён к минимуму $N$):

$$\xymatrix{ \circ\ar@{-}[rrrrrrr]\ar@{-}[ddddddd]&&&&&&&\circ\ar@{-}[ddddddd]\ar@{-}[llllddd]\\ &&\circ\ar@{-}[llu]\ar@{-}[ld]\ar@{-}[rrrdd]&&&&&&\\ &\circ&&&&&&&\\ &&&\circ\ar@{-}[llu]\ar@{-}[rd]\ar@{-}[rr]&-&\circ\ar@{-}[rd]\ar@{-}[ld]&&&\\ &&\circ\ar@{-}[uuu]\ar@{-}[luu]&&\circ\ar@{-}[ll]\ar@{-}[rrrdddd]\ar@{-}[rrrddd]&&\circ\ar@{-}[ruuuu]\ar@{-}[llllldd]&&\\ &&&&&&&&\\ &\circ\ar@{-}[luuuuuu]\ar@{-}[ruu]&&&&&&&\\ \circ\ar@{-}[rrrrrrr]\ar@{-}[ru]\ar@{-}[ruuuuu]&&&&&&&\circ\ar@{-}[luuu]\\ }$$

$$E=24, V=12 , F=6$$

Правильно ли посчитал? Это главный вопрос. Есть мысли, что это торический...но сомневаюсь

В принципе я уже читал другие темы, но там или Не-граф или уже вложен, а за алгоритмы поиска подграфов $K_{3,3}$ или $K_5$ узнал об их сложности, что эта задача нетривиальная.
Разве моя проблема сложнее, если уже известно, что граф неплоский?

Теорема Понтрягина-Куратовского только об определении графа как планарного или нет. А удаление вершин, рёбер и склейку вершин надо не любую брать а какие-то конкретные, на сколько я понял.

[sqribner48]

Nartu

Nartu в сообщении #1422495 писал(а):

Здесь был раздел с моим наблюдением того, что кол-во граней неплоского графа $G$ равно кол-ву граней плоского $H$, который получится удалением пересекающихся рёбер $G$, приведённого к минимуму пересечений.

Вы тут не правы.
Вспомним определения.

Цитата:

Плоским графом называется граф, вершины которого являются точками плоскости, а ребра --- непрерывными плоскими линиями без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им вершины

Цитата:

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

Оба определения из книги "Лекции по теории графов" авторы: В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич.
Из второго определения следует, что у неплоских графов нет граней. А вернее --- понятие грани определено только для плоских графов.
А из первого определения следует, что в неплоском графе, уложенном на плоскости, найдется хотя бы одна пара вершин, которые невозможно соединить жордановой кривой, не пересекающей ребра графа.

[Nartu]

Вы меня опередили. Я тут немного по-своему разобрался... оно будет ниже.

sqribner48 в сообщении #1424186 писал(а):

Оба определения из книги "Лекции по теории графов" авторы: В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич.
Из второго определения следует, что у неплоских графов нет граней. А вернее --- понятие грани определено только для плоских графов.
А из первого определения следует, что в неплоском графе, уложенном на плоскости, найдется хотя бы одна пара вершин, которые невозможно соединить жордановой кривой, не пересекающей ребра графа.

Хмм, а это неплохо... Видимо грани "есть" только для плоских графов, или ещё для вложенных в ориентируемую поверхность(тор,крендель)?

Из подготовленного письма:

Так, я осознал свою глупость! Грани предложенного графа посчитаны неправильно!

Быстро нашел на ютубе обучающие видео на английском(3-летней давности). Ссылки не сюда. Помогло.

Так вот, всё,что надо было вспомнить - дуальность графов. И опус:

Nartu в сообщении #1422495 писал(а):

надо использовать "мягкость" графа: "покрутить", "повертеть" и минимизировать неустранимые пересечения рёбер на плоскости.
Пусть их количество будет $N$. В принципе именно в них и должны быть "дырки" поверхности рода $N$, куда граф приятно вложится.

Это анти-научная ересь!

Можно нужную поверхность склеить из 2-мерных клеток-многоугольников с количеством рёбер, равным степени соответствующей вершины. Есть гипотеза, что это минимальная (двусторонняя), в которую граф вложим... Можно посчитать эйлерову хар-тику уже этой поверхности (без края).
В такую вкладывались у меня $\mathbf{K}_{3,3}$ , $\mathbf{K}_5$ , $\mathbf{K}_6$ и тот граф по-выше. Я так же проверил для ещё четырёх: $\mathbf{K_{3,3}}$ с добавкой 8-и рёбер и $\mathbf{K}_6$ без одного ребра, и двух планарных, - работает.
В результате, если сохранить рёбра по швам склеек, получится некий граф, тоже вложенный в созданную поверхность;
пример случая для $\mathbf{K}_6$ показал, что этот граф не дуален $\mathbf{K}_6$ . Для планарных получалась сфера $\left(\mathbf{S}^2\right)$ .

Не знаю, будет ли это справедливо с графом со счётно-бесконечным количеством вершин и рёбер.

Если этот метод действительно работает, я наверняка изобрёл велосипед.

[Nartu]

Что ж, $\mathbf{K}_7$ вложим в Тор. Метод построения поверхности рабочий, но гипотеза опроверглась. Думаю, в Тор довольно много графов вкладывается... Было бы неплохо построить наименьший контрпример для него... Задача оказалась сложнее... Не знаю, хватит ли сил и желания продолжать, но некоторый интерес остался.

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

И спасибо за ответы.

[Nartu]

$\mathkb{K}_8$ В тор уже не вкладывается. Тогда мне надо было это проверить, это же не долго!..

Инетерестное наблюдение: 8-угольник показался мне минимальным многоугольником, склейками пар рёбер которого можно сделать поверхность 2-го рода. И если его полный граф не вложился в Тор, есть гипотеза, что это рабочий критерий вложимости, правда, для полных графов, и, наверное, только поверхностей рода >0. Собственно критерий:

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

И я снова её опровергну...........

[Nartu]

Что ж, время идёт, а я решил занятся некоторыми разделами, смежными с вопросом в оглавлении. Это в основном топология и группы с кольцами по видеоурокам Шестопалова, для начала. Я как-то спрашивал его о более конкретных направлениях и получил ответ: инварианты узлов, графов; геометрическая топология... Копать надо в этих направлениях.

Маловероятно, что мне что-то удастся решить. Возможно лучше "прощупать" сложность этой задачи (оглавления) для начала.

Я уверен, уже есть частные результаты касательно вопроса.

Бонусом могу сказать, что у меня не получилось вложить $\mathbf{K_8}$ в крендель. Здесь бросатся гипотезами бессмысленно. Нужны знания... (я признался )

[Pphantom]

Nartu, если вы не заметили, из 6 сообщений темы 5 написаны вами (в т.ч. 4 последних). Не надо превращать тему в личный блог, подождите реакции собеседников.