Двойственный граф

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

На рис. 4.7 показана идея построения двойственного графа, изображенного пунктирными линиями. Из этого построения видно, что все графы, двойственные являются топологически эквивалентными, поэтому обычно говорят просто о двойственном графе ( Заметим, что если граф, двойственный к то когда несвязен.)

Рис. 4.7.

Упражнения

(см. скан)

Определение. Граф называется триоалентным или кубическим, если он является однородным графом степени 3.

Теорема 4.8. Все грани графа, двойственного плоской трехзначной связной карте, являются трехсторонними и число их четно.

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

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

Теорема 4.9. (Краус) [29]. Необходимое и достаточное условие, при котором граф является смежностным, состоит в том, что существует разбиение его ребер на полные подграфы такое, что нет вершины графа, принадлежащей более чем двум подграфам.

Упражнения

(см. скан)

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

Определение. Прямолинейным графом называется плоский граф, в котором каждге ребро является отрезком прямой линии.

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

Фари доказал следующую теорему.

Теорема 4.10. Каждый обыкновенный плоский граф изоморфен прямолинейному графу.

Докажем эту теорему с помощью последовательности лемм

Лемма 4.11. Если граф изоморфен прямолинейному графу, то каждый из его подграфов также изоморфен прямолинейному графу.

Доказательство, Если изоморфен прямолинейному графу а подграф получается удалением вершин и дуг, не входящих в этот подграф, то соответствующая операция в дает прямолинейный подграф, изоморфный рассматриваемому подграфу в (Здесь не есть граф, двойственный

Лемма 4.12. Каждый обыкновенный плоский граф является подграфом плоской триангуляции с тем же самым числом вершин.

Доказательство. Предположим, что содержит, по крайней мере, четыре вершины. (Случай трех или большего числа вершин оставляем для упражнения.) Построим плоскую триангуляцию которая содержит в качестве подграфа. Если грань две вершины не связанные ребром, то соединим и ребром, целиком лежащим в Получаем новый граф, который опять является обыкновенным. Продолжим такой процесс соединения несвязных пар вершин на грани, пока каждая пара вершин не будет связана ребром. После окончания процесса получим обыкновенный граф с тем же самым числом вершин. Очевидно, связен, ибо в противном случае существует грань смежная с двумя компонентами для которой можно выбрать внутри одной из компонент, внутри другой и соединить их ребром в что противоречит построению Покажем, что плоская триангуляция, предварительно заметив, что если некоторая грань ограничена только одним ребром, то граф состоит из этого ребра и двух его вершин. Грань не может быть ограничена двумя ребрами, так так тогда граф содержал бы только три вершины. Оба случая противоречат сделанному предположению о четырех вершинах. Таким образом, граница каждой грани состоит, по крайней мере, из трех ребер Если они не образуют цикла, то существует, по крайней мере, четыре вершины на границе Теперь содержит ребра, связывающие эти вершины, т. е. (рис, 4.8), и делящие плоскость На четыре грани, граница каждой из которых включает

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

Следующие две леммы необходимы для доказательства леммы 4.15.

Рис. 4.8.

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

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

Если в лемме 4.13 (предполагается, что она лежит на внутренней грани и связанные с ней ребра удаляются, то образуется пустая область внутри и если затем соединить с не пересекающимися

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

Лемма 4.14. Если граф не является обыкновенным, то содержит цикл их трех ребер, который разделяет две вершины.

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

Лемма 4.15. Каждая плоская триангуляция обыкновенно плоского графа изоморфна прямолинейному графу.

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

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

из то внутренняя область оказалась бы пустой. Выбирая точку внутри и проводя отрезки мы получим граф, изоморфный Если не обыкновенный, то по лемме 4.14 в существует цикл из трех ребер, разделяющий две вершины. Цикл вместе с наружными ребрами образует плоскую триангуляцию графа а с внутренними ребрами — плоскую триангуляцию графа Оба графа содержат самое большее вершин и, следовательно, по индуктивному предположению они изоморфны прямолинейным графам и соответственно. В графе внутренняя область цикла соответствующая оказывается пустой, С другой стороны, лежит внутри цикла соответствующего

При соответствующем выборе аффинного преобразования можно отобразить на Д] так, чтобы смежные грани в отображались на смежные грани. В результате получим прямолинейный граф, изоморфный Теорема 4.10 доказана.