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

[Munin]

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

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

Видимо, вы не понимаете, что означает "граф, не вкладывающийся в плоскость (сферу)". Ваш букет всегда вкладывается. Не вкладываются графы $K_5$ и $K_{3,3}.$ Но они вкладываются в сферу с одной ручкой. Насколько я понимаю, $K_6$ не вкладывается уже и в такую сферу, хотя я не могу сказать, сколько ручек ему необходимо.

[gogoshik]

Вы видимо меня не понимаете. Петли двигать нельзя. Допустим в букете есть 2 петли и они пересекаются на плоскости. Т.е. нарисован на листе бумаге такой букет. Вам не разрешено повернуть петли так, что они не будут перескаться.

Сказать по другому на букете задан циклический порядок обхода концов петель в выбранном направлении ориентации. Пусть в букете есть две петли $x$ (с концами $x_1, x_2$) и $y$ (c концами $y_1, y_2$) . Выберем направление ориентации вокруг вершины по часовой стрелке. Тогда концы будут идти в порядке $x_{1}y_{1}x_{2}y_{2}$ -- петли пересекаются. Так вот этот порядок при расположении на какой нибудь поверхности менять нельзя. На плоскости (листе бумаги) или сфере это будут пересекающиеся петли. Ваша задача подобрать поверхность такого минимального рода на которой петли в заданном порядке будут расположены без пересечений -- это будет означать вложение данного букета в поверхность этого рода.

Я хочу доказать утверждение:

Цитата:

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

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

[Slav-27]

gogoshik
Кажется, я начинаю понимать. Вы рассматриваете не абстрактный граф, а граф, который всё-таки где-то нарисован. Обратите внимание, что стандартное определение графа не такое. В стандартном смысле граф задаётся списком вершин и списком рёбер между ними, причём ни вершины, ни рёбра не должны состоять из точек какого-либо пространства. Точное определение (бывает несколько вариантов) смотрите в статье, на которую я ссылался выше.

Возможно, вы пытаетесь доказать следующее.

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

Это утверждение, очевидно, неверно.

К сожалению, понимать вас мне очень трудно, и если на этот раз я не угадал, то помочь вам, наверно, ничем не смогу. Учитесь понятно говорить по-русски.

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

Сказать по другому на букете задан циклический порядок обхода концов петель в выбранном направлении ориентации. Пусть в букете есть две петли $x$ (с концами $x_1, x_2$) и $y$ (c концами $y_1, y_2$) . Выберем направление ориентации вокруг вершины по часовой стрелке.

Например, здесь непонятно ничего. Что такое "направление ориентации"? что такое "концы петель" и почему их много, когда у букета вершина только одна? что такое "направление ориентации вокруг вершины"? И это не единственные вопросы, всё остальное, что вы тут написали, примерно так же непонятно.

[Munin]

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

Вы видимо меня не понимаете. Петли двигать нельзя.

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

Удачи вам.