223
правки
Изменения
Нет описания правки
Планарный граф, это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально:
{{Определение
|definition=
Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые<ref name="ЖК">Жордановыми кривыми, неформально говоря, называют крывые без самопересечений, которые можно «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем<br /> 1) криваяКривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;<br /> 2) две Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
<br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.
}}
{{Определение
|definition=
Граф называется '''планарным''', если он обладает укладкой на плоскости. Всевозможные укладки планарных графов на плоскости будем называть '''плоскимиПлоским графом''' графаминазывается граф уже уложенный на плоскости.
}}
{{TODO|t= здесь картинка}}
{{Определение
|definition=
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями'''(faces). Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
}}
{{TODO|t= здесь картинка с ребрами внутри грани и показывающие внещнюю грань}}
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <tex>V - E + F = 2</tex>, где <tex>V</tex> {{---}} вершины(''vertex''), <tex>E</tex> {{---}} ребра(''edges''), <tex>F</tex> {{---}} грани(''faces'').
Это свойство позволяет в некоторых случаях просто доказывать [[Непланарность K5 и K3,3|непланарность некоторых графов, например непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]].
Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:
{{Определение
|definition= Введем отношение <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/>
==Литература==
