Изменения

Планарный граф<br/>{| class="standard" border=0|[[Файл:planar_graph.png|250px|thumb|left|Пример планарного графа. Синим контуром обозначены грани, это такой граф, который можно изобразить на плоскости без пересеченийза исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и тогда говорят, что такой граф обладает укладкойвершины. Говоря немного более формально:]]|

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

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

|}{{TODO|tclass= здесь картинка}}"standard" border=0|

Плоский граф разбивает плоскость на несколько областей, называемых '''гранями'''''(англ. faces)''. Одна из граней не ограничена, ее называют '''внешней''' ''(англ. external)'' гранью, а остальные {{---}} '''внутренними''' ''(англ. unbounded)'' гранями.

Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <tex>V - E + F = 2</tex>, где <tex>V</tex> {{---}} вершины(''vertex''), <tex>E</tex> {{---}} ребра(''edges''), <tex>F</tex> {{---}} грани(''faces'').

Понятно, что любой граф, содержащий подграф <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 на ребро между вершинами смежных смежными ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).{{TODO|t=картинка}}

<references/>  ==Источники информации==* Асанов М, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 126. — ISBN 978­-5­-397­-00622­-4.