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