Эйлерова характеристка и неравенство Эйлера

[gogoshik]

Подскажите, пожалуйста!

Эйлерова характеристика двумерных топологических многогранников может быть посчитана по формуле: $\chi = v - e + f$. Для односвязных многогранников и графов верна формула $\chi = v - e + f = 2$. Эйлерова характеристика замкнутой ориентируемой поверхности связана с её родом $g$ и определяется соотношением $\chi = 2 - 2g$.

Каким образом от этих соотношений перейти к неравенству Эйлера $v - e + f \geqslant 2 - 2g$, выражающий критерий расположения связного графа на поверхности рода $g$?

[gogoshik]

Есть такая идея. Не моя. Посмотрите.

Нарисуем граф на поверхности рода $g$. Имеем равенство $v - e + f = 2 - 2g$. Покажем, что при следующих операциях на графе (добавление новой вершины на одном из ребер, добавление ребра имеющего одну общую вершину с уже нарисованным графом, добавление ребра соединяющего две вершины уже нарисованного графа) число $v - e + f $ может лишь только уменьшится. И из этого следует неравенство.

Я не понимаю, почему это число уменьшается?

[zcorvid]

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

Подскажите, пожалуйста!

Эйлерова характеристика двумерных топологических многогранников может быть посчитана по формуле: $\chi = v - e + f$. Для односвязных многогранников и графов верна формула $\chi = v - e + f = 2$. Эйлерова характеристика замкнутой ориентируемой поверхности связана с её родом $g$ и определяется соотношением $\chi = 2 - 2g$.

Каким образом от этих соотношений перейти к неравенству Эйлера $v - e + f \geqslant 2 - 2g$, выражающий критерий расположения связного графа на поверхности рода $g$?

Для начала нужно разобраться в формулировке. Что такое $v$ и $e$ для графа - понятно, а что такое $f$? Что такое "грань" абстрактного графа? Для вложенного графа $G \subset \Phi$ можно сказать так - грань это связная компонента дополнения $\Phi - G$, но это требует наличия вложения, и поэтому в таком виде для критерия вложимости графа в поверхность это определение применять будет трудно.

[gogoshik]

Точнее будет сказать так. Пусть на поверхности рода $g$ нарисован без самопересечений связный граф с $v$ вершинами и $e$ ребрами. Обозначим через $f$ число граней. Тогда $v - e + f \geqslant 2 - 2g$

[gogoshik]

Проверьте, пожалуйста. Допустим критерий $v - e + f \geqslant 2 - 2g$ верен.

Будем рассматривать только графы с одной вершиной и некоторым числом $n$ ребер (петель). Назовем такой граф букетом $n$ петель. Тогда из критерия следует неравенство $2g \geqslant n + 1 - F$. Я хочу доказать, если это неравенство выполняется, тогда рассматриваемые графы вкладываются в поверхность.

Пусть $G$ -- произвольный букет $n$ петель. Возможны два случая: (1) $G$ не содержит пересекающиеся петли; (2) $G$ содержит не менее одной пары пересекающихся петель. В случае (1) очевидно, что $G$ вкладывается в сферу. Рассмотрим случай (2). Известно, что в этом случае $f < n$ (пока без пояснений). Положим $f = n - 1$. Тогда $2g \geqslant n + 1 - F = n + 1 - n + 1 = 2$ или $g \geqslant 1 $. Осталось показать, что если $G$ имеет одну и более пересекающиеся ленточки и $g \geqslant 1 $, тогда $G$ вложим в поверхность рода $g$. Это следует из теоремы, которая утверждает, что любой букет петель с конечным числом ленточек можно вложить в некоторую замкнутую ориентируемую поверхность путем добавления некоторого числа ручек.

Будет ли справедливо такое доказательство?

[Slav-27]

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

Пусть на поверхности рода $g$ нарисован без самопересечений связный граф с $v$ вершинами и $e$ ребрами. Обозначим через $f$ число граней. Тогда $v - e + f \geqslant 2 - 2g$

Я бы стал думать так. Пусть граф вложен в поверхность. Исключим его оттуда; поверхность распадётся на какие-то связные компоненты. Если все они диски, то наш граф реализует клеточное разбиение поверхности, и поэтому должно быть равенство (из выражения для эйлеровой характеристики через число клеток). Если какая-то связная компонента не диск, то на ней есть нетривиальный цикл. Найдём на границе компоненты вершину графа и приделаем к ней ребро, лежащее внутри компоненты и реализующее этот цикл. Вершин осталось столько же, сколько было, рёбер стало на 1 больше. Граней осталось столько же по следующей причине: Предположим, напротив, что наша компонента распалась на несколько кусков. Поскольку граф связный, то граница компоненты была связна, значит, в один из кусков (назовём его 2-м) эта граница не попала. Значит, цикл, который мы вырезали, тривиален, поскольку он тривиален на 2-м куске. А на 2-м куске он тривиален потому, что так всегда бывает: если из поверхности без края вырезать диск, то граница будет тривиальна на том, что осталось. Это не очень очевидно; если умеете писать длинную точную последовательность пары, то будет довольно просто, а если нет, то придётся соображать, клеить поверхность из многоугольника, вероятно. Таким образом мы будем увеличивать количество рёбер, пока не достигнем равенства.

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

Ваше доказательство я не понял. Первая непонятность -- что такое $F$.

[gogoshik]

Спасибо. Я опечатался. Вместо $F$ везде должно быть $f$.


Вы же поняли, что это доказательство другого утверждения из предположения что первое (неравенство) уже доказано?

[Slav-27]

Хорошо, тогда в чём заключается "критерий"? Что значит "если неравенство выполняется , то граф вкладывается"? Если рассматривается абстрактный граф (никуда не вложенный), то что такое $f$, а если он уже вложен в поверхность, то что вы ещё хотите про него узнать?

[gogoshik]

Допустим у нас есть доказанное утверждение.

Утверждение. Пусть на поверхности рода $g$ нарисован без самопересечений связный граф с $v$ вершинами и $e$ ребрами. Обозначим через $f$ число граней. Тогда $v - e + f \geqslant 2 - 2g$.

Теперь я хочу доказать следующее.

Букет $n$ петель вложим в поверхность рода $g$ тогда и только тогда, когда $2g \geqslant n + 1 - f$.

Часть <<тогда>> тривиальна и следует из утверждения. Осталось доказать <<только тогда>>. Доказательство этой части я и попросил проверить.

[Slav-27]

Я не понимаю, в чём заключается утверждение части "только тогда". И, по-видимому, что вы называете "букет" -- тоже не понимаю. Это абстрактный граф или куда-то вложенный?

[gogoshik]

Букет -- это абстрактный граф с одной вершиной и некоторым количеством петель. В данном случае число петель равно $n$.

Часть "только тогда" формулируется (как я думаю) так.

Если для букета $n$ петель выполняется условие $2g \geqslant n + 1 - f$, тогда букет вложим в поверхность (т.е. его можно расположить на поверхности без пересечений петель кроме пересчения в общей вершине) рода $g$.

Ну да, еще нужно сказать, что для букета петель $f$ -- это число граничных компонент букета. Граничная компонента -- связная часть множества тех его точек, к которым он подходит <<с одной стороны>> (т.е. это те области, которые ограничивают петли, включая внешнюю или бесконечную область).

[Slav-27]

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

Букет -- это абстрактный граф

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

Если для букета $n$ петель выполняется условие $2g \geqslant n + 1 - f$

А $f$ тогда что такое? Для абстрактного графа?

[Munin]

Ваш "букет $n$ петель" всегда вкладывается в любую поверхность, потому что он вкладывается в плоскость.

[Slav-27]

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

Пусть $G$ -- произвольный букет $n$ петель. Возможны два случая: (1) $G$ не содержит пересекающиеся петли; (2) $G$ содержит не менее одной пары пересекающихся петель. В случае (1) очевидно, что $G$ вкладывается в сферу.

И что такое "абстрактный граф" вам понять тоже надо.

(Оффтоп)

Я ушёл как минимум до завтра.

-- 23.02.2019, 01:26 --

Определение есть там: https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)#%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F.

[gogoshik]

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

Ваш "букет $n$ петель" всегда вкладывается в любую поверхность, потому что он вкладывается в плоскость.

Не так. Не поэтому. Могут быть и пересекающиеся петли которые ограничивают вложение в плоскость или сферу. Например дан букет $n=2$ петель и петли пересекаются, если граф расположить (нарисовать) на сфере. Тогда, чтобы устранить пересечение, нужно приклеить к сфере одну ручку и одну из петель провести по ней. Полученная добавлением ручки поверхность будет рода $g = 1$ или тор. На торе можно свободно (без пересечений) расположить две петли с одной общей вершиной, одну по меридиану, другую по параллели.

-- 23.02.2019, 00:31 --

Slav-27 в сообщении #1377845 писал(а):

А $f$ тогда что такое? Для абстрактного графа?

сообщение #1377843