Редактирование: Укладка графа на плоскости

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
<br/>
+
----
{| class="standard" border=0
+
[[Файл:Planar_graph.jpg|300px|thumb|right|Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины]]
|[[Файл:planar_graph.png|250px|thumb|left|Пример планарного графа. Синим контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]]
+
Планарный граф (planar graph), это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально:
|
+
 
 
{{Определение
 
{{Определение
 +
|neat=neat
 
|definition=
 
|definition=
[[Основные_определения_теории_графов|Граф]] '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно  «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем
+
Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки <br/> пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют крывые без самопересечений, которые можно  «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем
# Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
+
<br /> 1) Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
# Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
+
<br /> 2) Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.
+
<br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют <br/>'''укладкой''' исходного графа.
 
}}
 
}}
 
  
 
{{Определение
 
{{Определение
|id= defplanar
 
 
|definition=
 
|definition=
Граф называется '''планарным''' ''(англ. planar graph)'', если он обладает укладкой на плоскости. '''Плоским''' ''(англ. plane graph, planar embedding of the graph)'' называется граф уже уложенный на плоскости.
+
Граф называется '''планарным''', если он обладает укладкой на плоскости. <br/>
 +
'''Плоским графом''' (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)''. Одна из граней не ограничена, ее называют '''внешней''' ''(англ. external)'' гранью, а остальные {{---}} '''внутренними''' ''(англ. unbounded)'' гранями.
+
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' (faces). Одна из граней не ограничена, ее &nbsp;<br/> называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
 
}}
 
}}
 
+
<div style='clear:left;'></div>
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <tex>V - E + F = 2</tex>, где <tex>V</tex> {{---}} вершины, <tex>E</tex> {{---}} ребра, <tex>F</tex> {{---}} грани.
+
<br/>
 +
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <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=  
[[Файл:Gomeomorf.png|350px|right]]
+
[[Файл:Gomeomorph.jpg|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>*.  
Строка 44: Строка 41:
 
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <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.
 
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов ]]
 
[[Категория: Укладки графов ]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: