Изменения

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

Укладка графа на плоскости

1257 байт добавлено, 19:38, 6 марта 2018
Нет описания правки
Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.
}}
 
 
{{Определение
|id= defplanar
|definition=
Граф называется '''планарным''''' (англ. ''planar graph)''), если он обладает укладкой на плоскости. '''Плоским''''' (англ. plane graph, planar embedding of the graph) '' называется граф уже уложенный на плоскости.
}}
|}
{{Определение
|definition=
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''''' (англ. faces)''. Одна из граней не ограничена, ее называют '''внешней''' ''(англ. external)'' гранью, а остальные {{---}} '''внутренними''' ''(англ. unbounded)'' гранями.
}}
 Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <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>]].
|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.
 
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
202
правки

Навигация