Изменения

[[Основные_определения_теории_графов|Граф ]] '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые<ref name="ЖК">Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем<br /> 1) кривая# Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;<br /> 2) две # Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.<br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.

Граф называется '''планарным''' ''(англ. planar graph)'', если он обладает укладкой на плоскости. Всевозможные укладки планарных графов на плоскости будем называть '''плоскимиПлоским''' ''(англ. plane graph, planar embedding of the graph)' графами' называется граф уже уложенный на плоскости.

Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' ''(англ. faces)''. Одна из граней не ограничена, ее называют '''внешней''' ''(англ. external)'' гранью, а остальные {{---}} '''внутренними''' ''(англ. unbounded)'' гранями.}} Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <tex>V - E + F = 2</tex>, где <tex>V</tex> {{---}} вершины, <tex>E</tex> {{---}} ребра, <tex>F</tex> {{---}} грани. Это свойство позволяет в некоторых случаях просто доказывать [[Непланарность K5 и K3,3|непланарность некоторых графов, например непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]. Понятно, что любой граф, содержащий подграф <tex>K_5</tex> или <tex>K_{3,3}</tex> непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:|[[Файл:K33.png|200px|thumb|Полный двудольный граф <tex>K_{3,3}</tex>. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений ребер.]]|}{{Определение|id=def_hmp|definition= [[Файл:Gomeomorf.png|350px|right]]Введем отношение <tex>R</tex> следующим образом: два графа находятся в отношении <tex>R</tex>, если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежными ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).<br/>Отношением '''гомеоморфизма''' (или '''топологической эквивалентности''') назовем [[Транзитивное_замыкание|транзитивное замыкание]] отношения <tex>R</tex>: <tex>R</tex>*. }} Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex>K_5</tex> и <tex>K_{3,3}</tex>: [[Теорема Понтрягина-Куратовского| теорема Понтрягина-Куратовского]]. {{Теорема|statement= В трехмерном евклидовом пространстве любой граф укладывается.|proof=Все вершины произвольного графа <tex>G</tex> помещаем в различных точках координатной оси <tex>OX</tex>. Рассмотрим пучок плоскостей, проходящих через ось <tex>OX</tex>, и зафиксируем <tex>|E|</tex> различных таких плоскостей. Теперь каждое ребро <tex>(u, v)</tex> изобразим полуокружностью, проходящей в соответствующей плоскости через вершины <tex>u, v</tex>. Ясно, что различные ребра не будут пересекаться кроме как в общих вершинах.

==ЛитератураСм. также==* [[Формула_Эйлера|Формула Эйлера]]* [[Локализация_в_ППЛГ_методом_полос_%28персистентные_деревья%29|Локализация в ППЛГ методом полос (персистентные деревья)]] ==Примечания==<references/> ==Источники информации==* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 126. — ISBN 978­-5­-397­-00622­-4.