Как доказать, что граф планарный?

Question

[asault_ceko]

Как доказать что этот граф планарный, используя две теоремы:
Теорема: Понтрягина - Куратовского.
Граф является плоским (планарным) тогда и только тогда, когда он не содержит подграфа, который гомеоморфен одному из графов Понтрягина - Куратовского.
Теорема: Граф является плоским (планарным), когда он не содержит подграфа, который стягивается к одному из графов Понтрягина-Куратовского.
Я понимаю эти теоремы, но не понимаю, как их использовать для произвольного графа. Не могли бы вы, пожалуйста, натолкнуть на мысль или объяснить, как использовать?
Вот мой граф:

Графы Понтрягина - Куратовского:

Answer 1

[Alexandroppolus]

Твой граф стягивается в К33, т.е. он не планарный. Если я правильно понял принцип стягивания.

Конкретно, тебе требуется:
1) стянуть в одну вершину три самые правые.
2) стянуть ребро малого равностороннего треугольника, которое пересекается другим ребром.
3) никогда больше не выкладывать сюда граф, у которого вершины не обозначены буквами или числами, потому что это пипец как их описывать!!

Comments

[asault_ceko]

sorry

Answer 2

[Wataru]

Если вы уверены, что он планарный, то его надо нарисовать без пересечений ребер. Подвигайте вершины туда-сюда.

А теоремы эти используют как раз, чтобы доказать, что граф не планарный. Тогда вы берете как-то стягиваете его вершины и получаете K33 или K5. Значит не планарный.

Доказать отсутствие таких стягиваний очень муторно. Надо перебирать все варианты. Типа, что будет если мы вот эти 2 вершины стягиваем в одну? А если нет? В первом случае, а стягиваем ли мы туда вот эту третью? А если нет? И так у вас 100500 случаев. Если очень граматно выбрать вершины, то есть шанс, что количество вариантов будет не слишком большое. Если видите, что стянутый граф можно нарисовать без самопересечений, дальше стягивать не надо.

Comments

[asault_ceko]

Да, я это прекрасно понимаю, именно поэтому и не понимаю, как эти теоремы использоватьXD Типа представьте граф на 100 вершин и там это все перебрать... Именно поэтому я зашел на форум спросить есть ли какой-то оптимальный подход к использованию этих теорем. Ребра я двигать пробовал, не повезло)) Как еще тогда можно доказать, что он планарный? Мы с дискретки просто не проходили еще что-то большее кроме этого по планарности.

[Wataru]

asault_ceko, нет какого-то простого алгоритма. Для больших графов - только компьютер сможет все проверить.