Изменения

Перейти к: навигация, поиск

Укладка графа на плоскости

326 байт добавлено, 06:33, 13 декабря 2011
м
Нет описания правки
Это свойство позволяет в некоторых случаях просто доказывать [[Непланарность K5 и K3,3|непланарность некоторых графов, например непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]].
Понятно, что любой граф, содержащий подграф <tex>K_5</tex> или <tex>K_{3,3}</tex> непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:
{{Определение
|definition= Введем отношение <tex>R</tex> следующим образом: два графа на находятся в отношении <tex>R</tex>, если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).
==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
* ''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 126. — ISBN 978­-5­-397­-00622­-4.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
223
правки

Навигация