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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 33 промежуточные версии 11 участников)
Строка 1: Строка 1:
[[Файл:Planar_graph.jpg|300px|thumb|left|Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины]]
+
<br/>
Планарный граф (planar graph), это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально:
+
{| class="standard" border=0
 
+
|[[Файл:planar_graph.png|250px|thumb|left|Пример планарного графа. Синим контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]]
 +
|
 
{{Определение
 
{{Определение
|neat=neat
 
 
|definition=
 
|definition=
Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки <br/> пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно  «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем
+
[[Основные_определения_теории_графов|Граф]] '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно  «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем
<br /> 1) Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
+
# Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
<br /> 2) Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
+
# Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
<br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют <br/>'''укладкой''' исходного графа.
+
Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.
 
}}
 
}}
 +
  
 
{{Определение
 
{{Определение
 +
|id= defplanar
 
|definition=
 
|definition=
Граф называется '''планарным''', если он обладает укладкой на плоскости. <br/>
+
Граф называется '''планарным''' ''(англ. planar graph)'', если он обладает укладкой на плоскости. '''Плоским''' ''(англ. plane graph, planar embedding of the graph)'' называется граф уже уложенный на плоскости.
'''Плоским графом''' (plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости.
 
 
}}
 
}}
[[Файл:K33.jpg|300px|thumb|right|Полный двудольный граф <tex>K_{3,3}</tex>. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений.]]
+
|}
 
+
{| class="standard" border=0
 +
|
 
{{Определение
 
{{Определение
|neat=1
 
 
|definition=
 
|definition=
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' (faces). Одна из граней не ограничена, ее &nbsp;<br/> называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
+
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' ''(англ. faces)''. Одна из граней не ограничена, ее называют '''внешней''' ''(англ. external)'' гранью, а остальные {{---}} '''внутренними''' ''(англ. unbounded)'' гранями.
 
}}
 
}}
<div style='clear:left;'></div>
+
 
<br/>
+
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <tex>V - E + F = 2</tex>, где <tex>V</tex> {{---}} вершины, <tex>E</tex> {{---}} ребра, <tex>F</tex> {{---}} грани.
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <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>]].
 
Это свойство позволяет в некоторых случаях просто доказывать [[Непланарность K5 и K3,3|непланарность некоторых графов, например непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]].
  
 
Понятно, что любой граф, содержащий подграф <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=  
 
|definition=  
[[Файл:Gomeomorph.jpg|350px|right]]
+
[[Файл:Gomeomorf.png|350px|right]]
Введем отношение <tex>R</tex> следующим образом: два графа на находятся в отношении <tex>R</tex>, если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).
+
Введем отношение <tex>R</tex> следующим образом: два графа находятся в отношении <tex>R</tex>, если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежными ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).
 
<br/>
 
<br/>
 
Отношением '''гомеоморфизма''' (или '''топологической эквивалентности''') назовем [[Транзитивное_замыкание|транзитивное замыкание]] отношения <tex>R</tex>: <tex>R</tex>*.  
 
Отношением '''гомеоморфизма''' (или '''топологической эквивалентности''') назовем [[Транзитивное_замыкание|транзитивное замыкание]] отношения <tex>R</tex>: <tex>R</tex>*.  
Строка 40: Строка 44:
 
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex>K_5</tex> и <tex>K_{3,3}</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/>  
+
<references/>
  
==Литература==
+
==Источники информации==
 
* Асанов М, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
 
* Асанов М, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
 
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 126. — ISBN 978­-5­-397­-00622­-4.
 
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 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.