Укладка графа на плоскости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<br/>
 
<br/>
 
{| class="standard" border=0
 
{| class="standard" border=0
|[[Файл:planar_graph.png|250px|thumb|left|Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]]
+
|[[Файл:planar_graph.png|250px|thumb|left|Пример планарного графа. Синим контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]]
 
|
 
|
 
{{Определение
 
{{Определение
Строка 27: Строка 27:
 
Понятно, что любой граф, содержащий подграф <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>. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений.]]
+
[[Файл:K33.png|200px|thumb|Полный двудольный граф <tex>K_{3,3}</tex>. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений ребер.]]
 
|}
 
|}
 
{{Определение
 
{{Определение

Версия 02:01, 23 марта 2012


Пример планарного графа. Синим контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.
Определение:
Граф обладает укладкой в пространстве [math]L[/math], если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами — жордановы кривые [1], соединяющие соответствующие вершины, причем
  1. Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
  2. Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
Соответствующий граф, составленный из точек пространства и жордановых кривых из [math]L[/math], называют укладкой исходного графа.


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

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

Это свойство позволяет в некоторых случаях просто доказывать непланарность некоторых графов, например непланарность [math]K_5[/math] и [math]K_{3,3}[/math].

Понятно, что любой граф, содержащий подграф [math]K_5[/math] или [math]K_{3,3}[/math] непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:

Полный двудольный граф [math]K_{3,3}[/math]. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений ребер.
Определение:
Gomeomorf.png

Введем отношение [math]R[/math] следующим образом: два графа на находятся в отношении [math]R[/math], если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).

Отношением гомеоморфизма (или топологической эквивалентности) назовем транзитивное замыкание отношения [math]R[/math]: [math]R[/math]*.


Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math]K_5[/math] и [math]K_{3,3}[/math]: теорема Понтрягина-Куратовского.

Примечания

  1. Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно «нарисовать одним росчерком пера».

Литература

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