Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7. Планарность и двойственность

В этой главе мы обсудим два важных понятия теории графов: планарность и двойственность. Сначала мы рассмотрим планарные графы и установим их некоторые свойства. Будут обсуждаться также характеризации планарных графов, данные Куратовским, Вагнером, Харари и Таттом, Мак-Лейном. Затем мы обсудим определение Уитни двойственных графов, которое дано, исходя из циклов и разрезающих множеств, и свяжем это понятие с, казалось бы, не имеющим к нему отношения понятием планарности.

Двойственность очень интересна для специалистов в области электрических цепей. Этот интерес обусловлен тем, что напряжение и ток в электрической цепи являются двойственными переменными. Их двойственность следует из законов Кирхгофа. Закон Кирхгофа для напряжений дается, исходя из циклов, а закон Кирхгофа токов — исходя из разрезающих множеств. Двойственность циклов и разрезающих множеств обсуждалась в гл. 2 и 4. Она станет очевидной в гл. 10, в которой мы покажем, что множества циклов и разрезающих множеств имеют одинаковую алгебраическую структуру.

7.1. Планарные графы

Говорят, что граф G укладывается на поверхности S, если его можно нарисовать на этой поверхности таким образом, что его ребра пересекаются только в своих концевых вершинах. Граф называется планарным, если его можно уложить на плоскости. Описанное изображение планарного графа G называется планарной укладкой графа G.

Две планарные укладки графа представлены на рис. 7.1. В одной из них (рис. 7.1, а) все ребра изображены в виде отрезков прямых линий, тогда как в другой (рис. 7.1, б) одно из ребер изображено в виде кривой линии. Заметим, что ребро, соединяющее вершины а и d на рис. 7.1, б, нельзя изобразить в виде прямой линии, если все остальные ребра изображены так, как показано.

Очевидно, что если граф имеет петли или параллельные ребра, то ни в какой из его планарных укладок нельзя изобразить все ребра в виде отрезков прямых линий. Здесь, естественно, возникает вопрос: для каждого ли планарного графа G существует укладка, в которой все ребра могут быть изображены в виде отрезков прямых? Как

устанавливается в следующей теореме, ответ на этот вопрос — положительный.

Теорема 7.1. Для каждого простого планарного графа существует планарная укладка, в которой все ребра графа можно изобразить в виде отрезков прямых линий.

Рис. 7.1. Две планарные укладки графа.

Этот результат получен независимо авторами работ [7.1-7.3].

Если граф не укладывается на плоскости, то его можно уложить на некоторой другой поверхности. Покажем, что укладываемость графа на плоскости и на сфере эквивалентны, т. е. если граф укладывается на плоскости, то он укладывается на сфере, и наоборот. В доказательстве этого утверждения используется понятие так называемой стереографической проекции сферы на плоскость, описываемое ниже.

Рис. 7.2. Стереографическая проекция.

Допустим, что мы положили сферу на плоскость (рис. 7.2). Назовем точку соприкосновения южным полюсом, а диаметрально противоположную точку на сфере — северным полюсом N. Пусть Р — произвольная точка на сфере. Тогда точка , в которой прямая, соединяющая точки N и Р пересекает плоскость, называется стереографической проекцией точки Р на плоскости. Очевидно, что между точками на сфере и их стереографическими проекциями на плоскости существует взаимно-однозначное соответствие.

Теорема 7.2. Граф G укладывается на плоскости тогда и только тогда, когда он укладывается на сфере.

Доказательство. Пусть G — укладка графа G на сфере. Положим сферу на плоскость так, чтобы северный полюс не был ни вершиной, ни точкой на ребре укладки

Тогда образ G в стереографической проекции — это укладка графа G на плоскости, поскольку ребра укладки G пересекаются только в своих концевых вершинах, а между точками на сфере, и их образами в стереографической проекции существует взаимно-однозначное соответствие.

Обратное доказывается аналогично.

Два основных непланарных графа, называемые графами Куратовского, представлены на рис. 7.3. Один из них — полный граф на пяти вершинах, а другой —

Рис. 7.3. Основные непланарные графы.

Называем эти графы основными непланарными графами потому, что они играют основополагающую роль в характеризации планарности, данной Куратовским (разд. 7.3). Непланарность этих графов устанавливается в следующем разделе.

До того как мы закончим этот раздел, хотелось бы указать, что в работе [7.4] доказано, что разделимый граф планарен тогда и только тогда, когда планарны его блоки. Поэтому, касаясь вопросов, связанных с укладкой на плоскости, будет достаточно, если мы рассмотрим только неразделимые графы.

<< Предыдущий параграф Следующий параграф >>
Оглавление