Укладка графа на плоскости — различия между версиями
| Строка 1: | Строка 1: | ||
| + | Планарный граф, это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые, соединяющие соответствующие вершины, причем | + | Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые <ref name="ЖК">Жордановыми кривыми, неформально говоря, называют крывые без самопересечений, которые можно «нарисовать одним росчерком пера».</ref>, соединяющие соответствующие вершины, причем |
| − | <br /> 1) | + | <br /> 1) Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет; |
| − | <br /> 2) | + | <br /> 2) Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам. |
<br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа. | <br /> Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа. | ||
}} | }} | ||
| + | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Граф называется '''планарным''', если он обладает укладкой на плоскости. | + | Граф называется '''планарным''', если он обладает укладкой на плоскости. |
| + | '''Плоским графом''' называется граф уже уложенный на плоскости. | ||
}} | }} | ||
| + | {{TODO|t= здесь картинка}} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Плоский граф разбивает плоскость на несколько областей, называемых '''гранями'''. Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями. | + | Плоский граф разбивает плоскость на несколько областей, называемых '''гранями'''(faces). Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями. |
}} | }} | ||
| + | {{TODO|t= здесь картинка с ребрами внутри грани и показывающие внещнюю грань}} | ||
| + | |||
| + | Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <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= Введем отношение <tex>R</tex> следующим образом: два графа на находятся в отношении <tex>R</tex>, если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку). | ||
| + | {{TODO|t=картинка}} | ||
| + | <br/> | ||
| + | Отношением '''гомеоморфизма''' (или '''топологической эквивалентности''') назовем [[Транзитивное_замыкание|транзитивное замыкание]] отношения <tex>R</tex>: <tex>R</tex>*. | ||
| + | }} | ||
| + | |||
| + | Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex>K_5</tex> и <tex>K_{3,3}</tex>: [[Теорема Понтрягина-Куратовского| теорема Понтрягина-Куратовского]]. | ||
| + | ==Примечания== | ||
| + | <references/> | ||
==Литература== | ==Литература== | ||
Версия 06:13, 13 декабря 2011
Планарный граф, это такой граф, который можно изобразить на плоскости без пересечений, и тогда говорят, что такой граф обладает укладкой. Говоря немного более формально:
| Определение: |
| Граф обладает укладкой в пространстве , если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами — жордановы кривые [1], соединяющие соответствующие вершины, причем
Соответствующий граф, составленный из точек пространства и жордановых кривых из , называют укладкой исходного графа. |
| Определение: |
| Граф называется планарным, если он обладает укладкой на плоскости. Плоским графом называется граф уже уложенный на плоскости. |
TODO: здесь картинка
| Определение: |
| Плоский граф разбивает плоскость на несколько областей, называемых гранями(faces). Одна из граней не ограничена, ее называют внешней гранью, а остальные — внутренними гранями. |
TODO: здесь картинка с ребрами внутри грани и показывающие внещнюю грань
Для плоских графов есть простое соотношение, называемое формулой Эйлера: , где — вершины(vertex), — ребра(edges), — грани(faces).
Это свойство позволяет в некоторых случаях просто доказывать непланарность некоторых графов, например непланарность и .
Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:
| Определение: |
| Введем отношение следующим образом: два графа на находятся в отношении , если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежных ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).
TODO: картинка
|
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных и : теорема Понтрягина-Куратовского.
Примечания
- ↑ Жордановыми кривыми, неформально говоря, называют крывые без самопересечений, которые можно «нарисовать одним росчерком пера».
Литература
- Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
