Изменения
Нет описания правки
[[Файл:Planar_graph.jpg|300px|thumb|left|Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]]Планарный граф (planar graph), это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально:
{{Определение
|neat=neat
|definition=
[[Основные_определения_теории_графов|Граф ]] '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки <br/> пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем
<br /> 1) Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
<br /> 2) Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
|definition=
Граф называется '''планарным''', если он обладает укладкой на плоскости. <br/>
'''Плоским графом''' (plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости.
}}
[[Файл:K33.jpg|300px|thumb|right|Полный двудольный граф <tex>K_{3,3}</tex>. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений.]]
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex>K_5</tex> и <tex>K_{3,3}</tex>: [[Теорема Понтрягина-Куратовского| теорема Понтрягина-Куратовского]].
==Примечания==
