Хочу определить планарен граф или нет. Если он непланарен, то естественно нужно это доказать. Есть критерий Понтрягина-Куратовского

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу из пяти вершин (K5) или графу «домики и колодцы» (K3,3).

(Из Википедии)

Не могу разобраться как это применять на практике. Покажите, как это делается, скажем на графе:

http://s13.postimg.org/98plsra6v/IMG_20140518_021533.jpg

Я понимаю, что вершины стягиваются, но в каком порядке брать вершины и как потом узнать, что в нет есть подграф, стягивающийся, скажем, в K3,3.

UPD: Хорошо, тогда вот такой http://s10.postimg.org/7gahmyk6x/IMG_20140518_021533.jpg Как к нему применить критерий?

задан 18 Май '14 2:19

изменен 18 Май '14 3:01

10|600 символов нужно символов осталось
2

Данный граф является планарным, поэтому теорему Понтрягина - Куратовского применять не нужно, а надо указать укладку графа на плоскости без самопересечений.

Пусть верхние вершины на рисунке обозначены через A, B, C, D, а нижние через 1, 2, 3, 4. Граф является двудольным; A соединена с 1, 2, 3; B соединена с 1, 2, 4; С соединена с 1, 3, 4; D соединена с 2, 3, 4.

Нарисуем прямоугольник с вершинами A2D3. На стороне 2D поместим точки B и 4, на стороне A3 -- точки 1 и C. Соединим B и 1, а также 4 и C. Добавим соединения 2 - D и A - 3 с внешней стороны прямоугольника. Получим требуемую укладку графа без самопересечений.

ссылка

отвечен 18 Май '14 2:53

Как вы это определили? Опыт, я понимаю, но ведь есть алгоритм / способ решения. Ну и ещё, раз уж граф этот планарен, отредактировал вопрос - нарисовал другой граф. Покажите, пожалуйста, на нем.

(18 Май '14 2:59) ssh
1

Я сначала попробовал поискать подграф типа $%K_5$% или $%K_{3,3}$%, а когда это не получилось, то стал искать укладку. Алгоритмы здесь, по сути, чисто теоретические, и основаны всё равно на переборе вариантов.

В новом примере у Вас изображён граф Петерсена с двумя добавленными рёбрами. Он не планарен. Если стереть несколько рёбер, то можно получить подграф, гомеоморфный $%K_{3,3}$%. А ещё проще убрать два "лишних" ребра, а потом стянуть в точку 5 рёбер, соединяющих "внешнюю" и "внутреннюю" часть. После этого получается $%K_5$%.

(18 Май '14 3:16) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,699

задан
18 Май '14 2:19

показан
1070 раз

обновлен
18 Май '14 3:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru