Граф, изображенный на плоскости, называется плоским графом, если его ребра не пересекаются в точках, отличных от вершин графа. Заметим, что данное понятие касается только геометрического изображения графа, но не графа как множества вершин и связей. Часто один и тот же граф может быть изображён как плоский, так и как не плоский.
Важное практическое приложение плоских графов - прокладка коммуникаций между объектами при условии, что пересечение коммуникаций нежелательно.
Теперь об одном важном свойстве плоских графов. Сначала важное понятие. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Заметим, что часть плоскости, лежащая "вне" фигуры графа, также подходит под определение грани и считается гранью. При определении граней графа нужна осторожность - опасно пренебрегать выражением "не содержащая других циклов" в определении термина. Так, на рис. 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г. Алгоритм работает за линейное время.
Важное практическое приложение плоских графов - прокладка коммуникаций между объектами при условии, что пересечение коммуникаций нежелательно.
Теперь об одном важном свойстве плоских графов. Сначала важное понятие. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Заметим, что часть плоскости, лежащая "вне" фигуры графа, также подходит под определение грани и считается гранью. При определении граней графа нужна осторожность - опасно пренебрегать выражением "не содержащая других циклов" в определении термина. Так, на рис. 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г. Алгоритм работает за линейное время.