Укладка графа на плоскости — различия между версиями
м |
м (поправлено форматирование) |
||
| Строка 1: | Строка 1: | ||
| − | [[Файл:Planar_graph.jpg|300px|thumb|left|Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]] | + | {| class="standard" border=0 |
| − | + | |[[Файл:Planar_graph.jpg|300px|thumb|left|Пример планарного графа. Оранжевым контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.]] | |
| + | | | ||
{{Определение | {{Определение | ||
| − | |||
|definition= | |definition= | ||
| − | [[Основные_определения_теории_графов|Граф]] '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки | + | [[Основные_определения_теории_графов|Граф]] '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем |
| − | + | # Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет; | |
| − | + | # Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам. | |
| − | + | Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа. | |
}} | }} | ||
| − | |||
{{Определение | {{Определение | ||
| − | |||
|definition= | |definition= | ||
Граф называется '''планарным''', если он обладает укладкой на плоскости. '''Плоским''' (plane graph, planar embedding of the graph) <br/>называется граф уже уложенный на плоскости. | Граф называется '''планарным''', если он обладает укладкой на плоскости. '''Плоским''' (plane graph, planar embedding of the graph) <br/>называется граф уже уложенный на плоскости. | ||
}} | }} | ||
| − | + | |} | |
| − | + | {| class="standard" border=0 | |
| + | | | ||
{{Определение | {{Определение | ||
| − | |||
|definition= | |definition= | ||
| − | Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' (faces). Одна из граней не ограничена, ее | + | Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' (faces). Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями. |
}} | }} | ||
| − | |||
| − | |||
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <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''). | ||
| Строка 29: | Строка 25: | ||
Понятно, что любой граф, содержащий подграф <tex>K_5</tex> или <tex>K_{3,3}</tex> непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение: | Понятно, что любой граф, содержащий подграф <tex>K_5</tex> или <tex>K_{3,3}</tex> непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение: | ||
| + | | | ||
| + | [[Файл:K33.jpg|300px|thumb|Полный двудольный граф <tex>K_{3,3}</tex>. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений.]] | ||
| + | |} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
Версия 22:53, 17 января 2012
|
Для плоских графов есть простое соотношение, называемое формулой Эйлера: , где — вершины (vertex), — ребра (edges), — грани (faces). Это свойство позволяет в некоторых случаях просто доказывать непланарность некоторых графов, например непланарность и . Понятно, что любой граф, содержащий подграф или непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение: |
| Определение: |
 Введем отношение следующим образом: два графа на находятся в отношении , если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).
|
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных и : теорема Понтрягина-Куратовского.
Примечания
- ↑ Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно «нарисовать одним росчерком пера».
Литература
- Асанов М, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
- Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 126. — ISBN 978-5-397-00622-4.
