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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 44 промежуточные версии 11 участников)
Строка 1: Строка 1:
 +
<br/>
 +
{| class="standard" border=0
 +
|[[Файл:planar_graph.png|250px|thumb|left|Пример планарного графа. Синим контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]]
 +
|
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые, соединяющие соответствующие вершины, причем
+
[[Основные_определения_теории_графов|Граф]] '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно  «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем
−
<br /> 1) кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
+
# Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
−
<br /> 2) две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
+
# Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
−
<br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.
+
Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.
 
}}
 
}}
 +
 +
 
{{Определение
 
{{Определение
 +
|id= defplanar
 
|definition=
 
|definition=
−
Граф называется '''планарным''', если он обладает укладкой на плоскости. Всевозможные укладки планарных графов на плоскости будем называть '''плоскими''' графами.
+
Граф называется '''планарным''' ''(англ. planar graph)'', если он обладает укладкой на плоскости. '''Плоским''' ''(англ. plane graph, planar embedding of the graph)'' называется граф уже уложенный на плоскости.
 
}}
 
}}
 +
|}
 +
{| class="standard" border=0
 +
|
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями'''. Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
+
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' ''(англ. 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.
 +
 
 +
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов ]]
 
[[Категория: Укладки графов ]]

Текущая версия на 19:14, 4 сентября 2022


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



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


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

Это свойство позволяет в некоторых случаях просто доказывать непланарность некоторых графов, например непланарность [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]: теорема Понтрягина-Куратовского.

Теорема:
В трехмерном евклидовом пространстве любой граф укладывается.
Доказательство:
[math]\triangleright[/math]
Все вершины произвольного графа [math]G[/math] помещаем в различных точках координатной оси [math]OX[/math]. Рассмотрим пучок плоскостей, проходящих через ось [math]OX[/math], и зафиксируем [math]|E|[/math] различных таких плоскостей. Теперь каждое ребро [math](u, v)[/math] изобразим полуокружностью, проходящей в соответствующей плоскости через вершины [math]u, v[/math]. Ясно, что различные ребра не будут пересекаться кроме как в общих вершинах.
[math]\triangleleft[/math]

См. также

Примечания

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

Источники информации

  • Асанов М, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
  • Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 126. — ISBN 978­-5­-397­-00622­-4.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Укладка_графа_на_плоскости&oldid=84686»