Непланарность графов

[gogoshik]

Подскажите, плиз, достаточно ли будет при доказательстве того, что граф не планарен использовать проверку по формуле Эйлера?

[Someone]

А как Вы собираетесь применять формулу Эйлера?

[gogoshik]

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

[Someone]

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

и граней

А грани-то Вы где возьмёте?

[gogoshik]

Ну, можно обойтись и без них. Есть соотношение в котором учитываются только $\lvert V\rvert$ и $\lvert E\rvert$. Ну, а если граф получится изобразить на бумаге, то можно подсчитать и грани.

[Someone]

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

Если граф изобразить на бумаге, то можно подсчитать и грани.

Ну, если уж Вам удалось изобразить граф на бумаге так, что там можно посчитать грани, то нафиг их считать? И так ясно, что граф планарный.

[gogoshik]

Someone в сообщении #1327529 писал(а):

Ну, если уж Вам удалось изобразить граф на бумаге так, что там можно посчитать грани, то нафиг их считать? И так ясно, что граф планарный.

Согласен. Тогда воспользуемся тем соотношением, которое без граней.

[Someone]

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

[Munin]

gogoshik
Вы про теорему Куратовского слышали?

[gogoshik]

Someone, то есть в решении само неравенство выводить (доказывать) не требуется и можно просто сказать, воспользуемся вот этим неравенством?

-- 18.07.2018, 23:34 --

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

Вы про теорему Куратовского слышали?

Слышал, но не более. Ну, а разве она тут нужна, почему просто нельзя воспользоваться неравенством (следствием из формулы Эйлера)?

[VAL]

Обычно, формулу Эйлера применяют для доказательства отсутствия планарности графа, используя рассуждение от противного.
Классический пример - доказательство того, что $K_5$ (один из двух графов, фигурирующих в теореме Понтрягина-Куратовского) не планарен.
Пусть $K_5$ планарен. Тогда $f = e+2-v = 10+2-5=7$. Но каждая грань окружена не менее чем тремя ребрами, а каждое ребро разделяет две грани.
Поэтому $2f\ge 3e$, т.е. $20\ge 21$ - противоречие.

-- 19 июл 2018, 07:54 --

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

gogoshik
Вы про теорему Куратовского слышали?

Разумеется, имеет смысл начинать с этого критерия.
Однако, проверка наличия/отсутствия подграфов, стягиваемых к $K_5$ либо $K_{3,3}$ не всегда простая задача. В отличие, например, от критерия эйлеровости.
Поэтому иногда проще воспользоваться оценкой с помощью формулы Эйлера.

[Someone]

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

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

Ну откуда я знаю? Вдруг преподаватель требует от Вас привести полное формальное доказательство, начиная с аксиом математической логики и теории множеств… Но если неравенство известное, то я бы его просто применил. А уж если бы преподаватель начал спрашивать, откуда взялось это неравенство, стал бы объяснять.

Но Вы всё разговорами ограничиваетесь, а попыток решения пока нету. Берите уж это ваше неравенство и пробуйте его применить.

[gogoshik]

VAL в сообщении #1327571 писал(а):

Но каждая грань окружена не менее чем тремя ребрами, а каждое ребро разделяет две грани.
Поэтому $2f\ge 3e$

У Вас какое то хитрое неравенство. У меня $3f\leqslant2e$. Подставив его в формулу Эйлера, получим $e \leqslant 3v - 6$.

[Someone]

Ну так с вашим-то графом что? Так и будем воду в ступе толочь?

[VAL]

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

VAL в сообщении #1327571 писал(а):

Но каждая грань окружена не менее чем тремя ребрами, а каждое ребро разделяет две грани.
Поэтому $2f\ge 3e$

У Вас какое то хитрое неравенство. У меня $3f\leqslant2e$.

Виноват
Буковки $f$ и $e$ местами поменял, в силу своей природной рассеянности, усиленной приобретенной расхлябанностью.