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