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

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

Версия 10:25, 13 декабря 2011

Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины

Планарный граф (planar graph), это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально:


Определение:
Граф обладает укладкой в пространстве [math]L[/math], если он изоморфен графу, вершинами которого являются некоторые точки
пространства, а ребрами — жордановы кривые [1], соединяющие соответствующие вершины, причем


1) Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
2) Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.


Соответствующий граф, составленный из точек пространства и жордановых кривых из [math]L[/math], называют
укладкой исходного графа.


Определение:
Граф называется планарным, если он обладает укладкой на плоскости.
Плоским графом (plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости.
Полный двудольный граф [math]K_{3,3}[/math]. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений.


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

Определение:
Gomeomorph.jpg

Введем отношение [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.