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