497
правок
Изменения
Нет описания правки
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями''' (faces). Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
}}
Для плоских графов есть простое соотношение, называемое [[Формула_Эйлера|формулой Эйлера]]: <tex>V - E + F = 2</tex>, где <tex>V</tex> {{---}} вершины (''vertex''), <tex>E</tex> {{---}} ребра (''edges''), <tex>F</tex> {{---}} грани (''faces'').
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex>K_5</tex> и <tex>K_{3,3}</tex>: [[Теорема Понтрягина-Куратовского| теорема Понтрягина-Куратовского]].
{{Теорема
|statement=
В трехмерном эквлидовом пространстве любой граф укладывается.
|proof=
Все вершины произвольного графа <tex>G</tex> помещаем в различных точках координатной оси <tex>OX</tex>. Рассмотрим пучок плоскостей, проходящих через ось <tex>OX</tex>, и зафиксируем <tex>|E|</tex> различных таких плоскостей. Теперь каждое ребро <tex>(u, v)</tex> изобразим полуокружностью, проходящей в соответствующей плоскости через вершины <tex>u, v</tex>. Ясно, что различные ребра не будут пересекаться кроме как в общих вершинах.
}}
