@asault_ceko

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

Как доказать что этот граф планарный, используя две теоремы:
Теорема: Понтрягина - Куратовского.
Граф является плоским (планарным) тогда и только тогда, когда он не содержит подграфа, который гомеоморфен одному из графов Понтрягина - Куратовского.
Теорема: Граф является плоским (планарным), когда он не содержит подграфа, который стягивается к одному из графов Понтрягина-Куратовского.
Я понимаю эти теоремы, но не понимаю, как их использовать для произвольного графа. Не могли бы вы, пожалуйста, натолкнуть на мысль или объяснить, как использовать?
Вот мой граф:
66159dd7f2d39879295355.jpeg
Графы Понтрягина - Куратовского:
66159e853a899854486705.jpeg
  • Вопрос задан
  • 201 просмотр
Пригласить эксперта
Ответы на вопрос 2
Alexandroppolus
@Alexandroppolus
кодир
Твой граф стягивается в К33, т.е. он не планарный. Если я правильно понял принцип стягивания.

Конкретно, тебе требуется:
1) стянуть в одну вершину три самые правые.
2) стянуть ребро малого равностороннего треугольника, которое пересекается другим ребром.
3) никогда больше не выкладывать сюда граф, у которого вершины не обозначены буквами или числами, потому что это пипец как их описывать!!
Ответ написан
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Если вы уверены, что он планарный, то его надо нарисовать без пересечений ребер. Подвигайте вершины туда-сюда.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы