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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 6 участников)
Строка 15: Строка 15:
 
|id= defplanar
 
|id= defplanar
 
|definition=
 
|definition=
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости.
+
Граф называется '''планарным''' ''(англ. planar graph)'', если он обладает укладкой на плоскости. '''Плоским''' ''(англ. plane graph, planar embedding of the graph)'' называется граф уже уложенный на плоскости.
 
}}
 
}}
 
|}
 
|}
Строка 22: Строка 22:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' (faces). Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
+
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' ''(англ. faces)''. Одна из граней не ограничена, ее называют '''внешней''' ''(англ. external)'' гранью, а остальные {{---}} '''внутренними''' ''(англ. unbounded)'' гранями.
 
}}
 
}}
  
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <tex>V - E + F = 2</tex>, где <tex>V</tex> {{---}} вершины (''vertex''), <tex>E</tex> {{---}} ребра (''edges''), <tex>F</tex> {{---}} грани (''faces'').
+
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <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>]].
 
Это свойство позволяет в некоторых случаях просто доказывать [[Непланарность K5 и K3,3|непланарность некоторых графов, например непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]].
Строка 37: Строка 37:
 
|definition=  
 
|definition=  
 
[[Файл:Gomeomorf.png|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>*.  
Строка 45: Строка 45:
  
 
{{Теорема
 
{{Теорема
|statement=
+
|statement=  
В трехмерном эквлидовом пространстве любой граф укладывается.
+
В трехмерном евклидовом пространстве любой граф укладывается.
 
|proof=
 
|proof=
 
Все вершины произвольного графа <tex>G</tex> помещаем в различных точках координатной оси <tex>OX</tex>. Рассмотрим пучок плоскостей, проходящих через ось <tex>OX</tex>, и зафиксируем <tex>|E|</tex> различных таких плоскостей. Теперь каждое ребро <tex>(u, v)</tex> изобразим полуокружностью, проходящей в соответствующей плоскости через вершины <tex>u, v</tex>. Ясно, что различные ребра не будут пересекаться кроме как в общих вершинах.  
 
Все вершины произвольного графа <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.