223
правки
Изменения
Нет описания правки
[[Файл:Planar_graph.jpg|300px|thumb|right|Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины]]<div style='clear:left;'></div>Планарный граф(planar graph), это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально:
{{Определение
|neat=neat
|definition=
Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки <br/> пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют крывые без самопересечений, которые можно «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем
<br /> 1) Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
<br /> 2) Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
<br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют <br/>'''укладкой''' исходного графа.
}}
{{Определение
|definition=
Граф называется '''планарным''', если он обладает укладкой на плоскости. <br/>'''Плоским графом''' (plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости.
}}
[[Файл:K33.jpg|300px|thumb|right|Полный двудольный граф <tex>K_{{TODO|t= здесь картинка}3,3}</tex>. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений.]]
{{Определение
|neat=1
|definition=
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями'''(faces). Одна из граней не ограничена, ее <br/> называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
}}
Это свойство позволяет в некоторых случаях просто доказывать [[Непланарность K5 и K3,3|непланарность некоторых графов, например непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]].
Понятно, что любой граф, содержащий подграф <tex>K_5</tex> или <tex>K_{3,3}</tex> непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:
{{Определение
|definition= [[Файл:Gomeomorph.jpg|350px|right]]Введем отношение <tex>R</tex> следующим образом: два графа на находятся в отношении <tex>R</tex>, если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).{{TODO|t=картинка}}
<br/>
Отношением '''гомеоморфизма''' (или '''топологической эквивалентности''') назовем [[Транзитивное_замыкание|транзитивное замыкание]] отношения <tex>R</tex>: <tex>R</tex>*.
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex>K_5</tex> и <tex>K_{3,3}</tex>: [[Теорема Понтрягина-Куратовского| теорема Понтрягина-Куратовского]].
==Смотри также==
* [[Двойственный_граф_планарного_графа| Двойственный граф планарного графа]]
==Примечания==
<references/>
==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы* ''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 126. — ISBN 978-5-397-00622-4.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
