Граф, изображенный на плоскости, называется плоским графом, если его ребра не пересекаются в точках, отличных от вершин графа. заметим, что данное понятие касается только изображения графа, но не графа как множества вершин и связей. часто один и тот же граф может быть изображён как плоский, так и как не плоский. важное практическое приложение плоских графов - прокладка коммуникаций между объектами при условии, что пересечение коммуникаций нежелательно. теперь об одном важном свойстве плоских графов. сначала важное понятие. гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. заметим, что часть плоскости, лежащая "вне" фигуры графа, также подходит под определение грани и считается гранью. при определении граней графа нужна осторожность - опасно пренебрегать выражением "не содержащая других циклов" в определении термина. так, на рис. 2 область 2-4-3-5-2 не является гранью - она ограничена простым циклом, но сама содержит простой цикл 2-3-5-2. теперь собственно свойство. пусть в - количество вершин в графе, г - количество граней в плоском представлении графа, р - количество рёбер в графе. тогда получаем формулу эйлера: в + г - р = 2 для связного графа. для несвязного графа с k компонентами связности формула имеет вид в + г - р = k + 1. подставьте в неё k=1 и сравните с предыдущей. интересное совпадение, не правда ли? формула эйлера для выпуклых многогранников также заметим, что формула эйлера выполняется для выпуклых многогранников. и это не случайно: выпуклый многогранник может быть представлен как плоский граф, если вершины и рёбра многогранника рассматривать как вершины и рёбра графа. теперь покажем это на деле: возьмём n-угольную пирамиду с выпуклым многоугольником в основании и "превратим" её в плоский граф (см. рис. 3). у пирамиды n+1 граней (основание и n боковых граней), n+1 вершин (n в основании и одна "обособленная") и 2n рёбер (n в основании и n соединяющих "обособленную" вершину" с остальными). легко проверить - формула эйлера тут работает. теперь разберёмся с плоским графом на рис. 3 справа. аналогично несложно понять, что имеются n+1 вершин и 2n рёбер. теперь разберёмся с гранями. их опять n+1 (n граней-треугольников и "внешняя" грань вне фигуры). снова формула эйлера работает: n+1+n+1-2n=2. сейчас похожий фокус проделаем с n-угольной призмой. имеем n+2 граней (два основания и n боковых граней), 2n вершин (по n вершин в каждом основании) и 3n рёбер (по n в каждом основании и ещё n соединяющих основания). получаем b + г - р = 2. теперь разбираемся с графом. количество вершин и рёбер считается легко. граней снова n+2: "внутренний" n-угольник, n четырехугольников и "внешняя" грань. и снова формула эйлера работает. планарные графы и проверка на планарность планарный граф - граф, который может быть изображён как плоский. пример планарного графа: не всякий граф является планарным графом. согласно теореме куратовского-понтрягина (иногда её также называют теоремой понтрягина-куратовского, а иногда и вовсе опускают одну из фамилий), граф планарен тогда и только тогда, когда он не содержит подграфов типов, на рис. 6. на основе теоремы куратовского-понтрягина просто получить один примечательный вид непланарных графов. поскольку полный граф с 5 вершинами непланарен, а полный граф с n> 5 вершинами содержит такой подграф, то верно следующее. полный граф с n> 4 вершинами обязательно непланарен. на первый взгляд кажется, что всё просто - у нас лишь два типа "вредных" подграфов. на самом же деле анализа большого графа на наличие таких подграфов весьма непроста. одним из алгоритмов, проверяющих, планарен ли граф, является алгоритм, разработанный в 1970г. хопкрофтом и тарьяном и улучшенный ими в 1974г. алгоритм работает за линейное время.
Спасибо
Популярные вопросы