Графы из многоугольников

Плоский связный геометрический граф G называется графом из многоугольников, если каждая его грань ограничена не менее чем тремя ребрами, и каждое ребро является смежным двум граням. Так, например, плоский граф, изображенный на рис. 89, является графом из многоугольников, а граф на рис. 90 таковым не является сразу по двум причинам: во-первых, в нем есть грани, ограниченные всего одним и двумя ребрами, и, во-вторых, одно из ребер графа является перешейком и смежным только одной грани (внешней).

Рис. 89 Рис. 90

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

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

Теорема 12. В любом плоском графе без перешейков количество граней, ограниченных нечетным числом ребер, — четно.

Действительно, обозначим через а * (h) количество ребер, ограничивающих грань h. Так как каждое ребро графа примыкает ровно к двум его граням, то сумма всех ребер, ограничивающих все грани, равна удвоенному числу ребер графа:

Так как сумма, входящая в левую часть формулы (2.3.2), есть четное число, то в нее может входить лишь четное число нечетных слагаемых.

Следствие. Сумма всех ребер, ограничивающих все грани плоского графа без перешейков, равна удвоенному числу его ребер.

Замечание. Если рассмотреть граф G', двойственный графу G, и обозначить через Н' вершину, двойственную грани h, то число О *(h) является ничем иным, как степенью <7 (Н') вершины Н'. Поэтому теорема 12 (и вытекающее из ее доказательства следствие) являются просто переформулировками теоремы 1 (и соответствую-щего следствия) для двойственного графа. Так как в двойственных графах перешейки соответствуют петлям, а степень петли при подсчете степеней учитывается дважды, то, естественно, при подсчете числа ребер, ограничивающих грани, перешеек следует учитывать также два раза. Приняв такое соглашение, можно расширить область применения доказанных выше теоремы и следствия, которые будут справедливы для любого плоского графа.

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

Предложение 1. Для любого графа из

многоугольников справедливо неравенство:

Действительно, для лк>бой грани h рассматриваемого графа можно записать о *(К)>3. Следовательно, используя боимулу (2.3.2), получим:

Предложение 2. Для любого графа из

многоугольников справедливо неравенство:

Действительно, из формулы Эйлера для плоского графа следует, что / = 2 + е — v. Подставляя найденное для/выражение в неравенство (2.3.3), получим:

2е > 3(2 + e-v) 3v > 6 + е е< 3(v — 2).

Заметим, что доказанное неравенство можно обобщить для несвязных графов.

Предложение 3. Пусть задан граф G, каждая компонента связности которого является графом из многоугольников. Тогда для графа G справедливо неравенство (2.3.4).

Доказательство. Пусть граф G имеет п компонент связности G, G₂, ?.?, G_n, являющихся графами из многоугольников. Тогда для каждой компоненты мы можем записать неравенство вида (2.3.4):

Предложение доказано.

Суммируя эти п неравенств, получим:

Частным случаем графов из многоугольников являются плоские связные графы, каждая грань которых ограничена одним и тем же числом ребер (т.е. <�т*(А) = п = const для каждой грани К). Такие графы называются графами из п-угольников. Граф, двойственный графу из n-угольников, является однородным графом степени п. Для графа из n-угольников справедливы следующие равенства, вытекающие из формул (2.3.2) и (2.3.1):

Граф из треугольников называется плоской триангуляцией. Для плоской триангуляции неравенства (2.3.3) и (2.3.4) превращаются в равенства, а количества ребер и граней плоской триангуляции с v вершинами вычисляются по формулам:

Важность этого класса плоских графов раскрывается следующей теоремой.

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

Для доказательства опишем процесс построения плоской триангуляции G', являющейся сверхграфом исходного графа G.

1 этап 0добавление перешейков между

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

2 этап (измельчение граней). Предположим, что в графе G/ имеется грань h> на границе которой есть две несмежные вершины. Тогда можно соединить эти вершины ребром, целиком лежащим в Л и не пересекающим другие ребра графа. После этого грань h разобьется на две грани, каждая из которых ограничена меньшим числом ребер, чем h. После конечного числа таких операций получим искомый сверхграф, являющийся плоской триангуляцией.