Книжное вложение графа (трудности с пруфом)

[gogoshik]

Будьте любезны, помогите с построением правильного доказательства. Я не могу некоторую идею уложить в аккуратное доказательство.

Утверждение. Любой граф можно нарисовать без самопересечений (реализуется) в книжке с некоторым количеством листов, зависящим от графа. Более точно, для любого $n$ существует $k$, а также $n$ точек и $n(n - 1)/2$ несамопересекающихся ломаных в книжке с $k$ листами, таких что каждая пара точек соединена некоторой ломаной и никакая ломаная не пересекает внутренности другой ломаной.

Доказательство (эскиз). Рассмотрим граф с самопересекающимися ребрами. Поместим вершины графа в различные точки на общей оси (т.е. оси пересечения листов или плоскостей книжки). Для каждой пары пересекающихся ребер добавим (выберем) листы (плоскости), проходящую через общую ось таким образом, чтобы различные ребра графа соответствовали различным плоскостям. Это всегда можно сделать добавлением нового листа (плоскости) книжки в силу конечности множества ребер.

[gogoshik]

Может так всё и оставить? Или это нельзя считать доказательством? Боюсь, что преподаватель зарубит.

[gogoshik]

Апдейт задачи. Помогите, плиз, закончить доказательство.

Утверждение. Любой граф можно нарисовать без самопересечений в книжке с тремя листами.

Лемма. Графы $K_{5}$ и $K_{3,3}$ можно нарисовать без самопересечений в книжке с тремя листами.

Доказательство. Рассмотрим граф $G$. Если $G$ не содержит подграфа, гомеоморфного графу $K_{5}$ или $K_{3,3}$, тогда $G$ планарный (по теореме Куратовского). Следовательно $G$ можно нарисовать в книжке с одним листом. Пусть теперь $G$ содержит подграф, гомеоморфный графу $K_{5}$ или $K_{3,3}$. (Вот тут я запутался и не знаю как написать, что можно воспользоваться леммой).

[alcoholist]

gogoshik
я бы обошелся без леммы... Нарисовал бы максимальное дерево на одном из листов, а потом бы доказал, что оставшиеся ребра можно без самопересечений прилепить

Или конструктивно: Построим вложение полного $n$-графа в книжку с тремя листами. Любой граф есть подграф полного графа.

[gogoshik]

alcoholist, благодарю.

[sqribner48]

gogoshik

gogoshik в сообщении #1345207 писал(а):

Утверждение. Любой граф можно нарисовать без самопересечений в книжке с тремя листами.

alcoholist в сообщении #1345334 писал(а):

Построим вложение полного $n$-графа в книжку с тремя листами.

Вообще-то это не совсем так. Если сделать запрос «книжное вложение графов», то Википедия даст следующий результат:

Цитата:

Книжная толщина любого полного графа с $n$ вершинами равна в точности
$\lceil n/2 \rceil$.
Этот результат даёт верхнюю границу максимальной книжной толщины любых графов с $n$ вершинами.

Доказательство этого можно найти в работе:
Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory. — 1979. — Т. 27, вып. 3. — С. 320–331. — DOI:10.1016/0095-8956(79)90021-2
(легко можно скачать по DOI с сайта А. Элбакян - sci-hub.tw)
Проверьте (т.е. скачайте) и убедитесь в этом сами

[alcoholist]

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

Если сделать запрос «книжное вложение графов»

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

[sqribner48]

Уважаемый alcoholist
Мои слова

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

Проверьте (т.е. скачайте) и убедитесь в этом сами

были написаны только для ТС. Он студент и ему полезно во всем разобраться.
Вот Вы написали

alcoholist в сообщении #1345719 писал(а):

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

А разве не именно это изложено в определении утверждения, которое должен доказать ТС?

gogoshik в сообщении #1343626 писал(а):

Утверждение. Любой граф можно нарисовать без самопересечений (реализуется) в книжке с некоторым количеством листов, зависящим от графа. Более точно, для любого $n$ существует $k$, а также $n$ точек и $n(n - 1)/2$ несамопересекающихся ломаных в книжке с $k$ листами, таких что каждая пара точек соединена некоторой ломаной и никакая ломаная не пересекает внутренности другой ломаной.

В приведенной цитате вроде не написано, что «рёбра могут переходить со страницы на страницу (через корешок)».
Может быть ТС должен быть дать более точную формулировку утверждения.

[Someone]

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

В приведенной цитате вроде не написано, что «рёбра могут переходить со страницы на страницу (через корешок)».

Зачем разрешать то, что не запрещено? Если бы было запрещено, то это должно быть написано явно. Если пойти по вашему пути, то получится полный абсурд. Возьмём, например, теорему Пифагора и запретим в ней все треугольники, про которые явно не сказано, что они разрешены. В результате теорема будет неприменима ни к одному треугольнику: в теореме не написано, что стороны треугольника могут иметь рациональные длины; в теореме не написано, что стороны треугольника могут иметь иррациональные длины.

[alcoholist]

Спасибо, Someone!

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

В приведенной цитате вроде не написано

В приведенной цитате всё написано. Что такое "нарисовать" (комбинаторное вложение), понятно из предыдущих постов.

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

не написано, что «рёбра могут переходить со страницы на страницу (через корешок)»

Выбросьте (мысленно) один лист, тогда никакого "корешка", не останется, будет просто плоскость.