4.2. Плоские графы

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

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

Возможен и обратный процесс, т. е. граф со сферы можно отобразить на плоскость при условии, что выбранный северный полюс не совпадает ни с одной точкой графа. (Интересные осложнения возникают, если северный полюс совпадает с вершиной графа. Последний в этом случае отображается в бесконечность, что приводит к дополнительным трудностям.) Заметим, что любая область графа, изображенного на плоскости, может быть сделана внешней с помощью двух отображений. Сначала граф отображается на сферу таким, чтобы южный полюс соприкасался с точкой внутри рассматриваемой грани. Затем производится обратное отображение на плоскость. При этом бывший северный полюс используется как точка контакта сферы с плоскостью, а бывший южный полюс — как центр проекций.

(см. скан)

Рис. 4.1.

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

Вернемся теперь к вопросу определения плоских графов и приведем основные сведения, необходимые для доказательства теоремы Понтрягина — Куратовского. Обыкновенный граф, который имеет наименьшее число вершин и не является плоским, есть полный граф из пяти вершин, показанный на рис. 4.2.

Рис. 4.2.

Рис. 4.3.

Такой граф будем называть графом Понтрягина-Куратовского 1-го типа (см. лемму 4.4). Очевидно, что если любой граф содержит такой пята вершинный граф (или, вообще, любой неплоский граф) в качестве подграфа, то он обязательно неплоский. Примером неплоского графа, который не содержит упомянутого полного графа, является граф в задаче трех пунктах обслуживания и трех домах», приведенный на рис. 4.3. Будем называть такой граф графом Понтрягина — Куратовского 2-го типа. Название «граф обслуживания» возникает из задачи соединения домов с каждым из пунктов обслуживания посредством коммуникаций, которые не пересекаются друг с другом (т. е. образуют плоский граф). Как показано в лемме 4.4, это незозможно сделать для Графы Понтрягина — Куратовского 1-го и 2-го типов позволяют определить наиболее общее условие существования плоского графа.

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

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

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

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

Лемма 4.2 (теорема Менгера — Дирака [14]). Если две вершины графа без точек сочленения с числом вершин и если цепь, соединяющая эти вершины, то существуют две цепи связывающие которые не имеют других общих вершин и при движении вдоль каждой, из которых вершины цепи встречаются в порядке возрастания их индексов.

Доказательство. Теорема доказывается по индукции. Теорема справедлива, если цепь состоит из пары вершин, связанных единственным ребром. Предположим теперь, что теорема верна для любой пары вершин, если длина цепи, связывающей их, равна самое большее и покажем, что она верна для простой цепи длины Обозначим, и предположим, что цепь, соединяющая Пусть вершины расположены в порядке По предположению индукции, связаны двумя цепями удовлетворяющими условиям теоремы. Заметим, что часть которая соединяет может быть одной из двух простых цепей или Так как не является точкой сочленения, то она не разделяет и следовательно, существует цепь, соединяющая и не проходящая через Эта цепь

содержит часть которая соединяет последнюю вершину в последовательности с вершиной

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

и

удовлетворяют условиям теоремы.

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

и

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

Лемма 4.3. Связный плоский граф с вершинами, ребрами и гранями (включая внешнюю или бесконечную грань) удовлетворяет формуле Эйлера

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

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

Лемма 4.4. Подграфы Понтрягина — Куратовского являются неплоскими.

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

В случае графа 1-го типа каждая грань ограничивается, по крайней мере, тремя ребрами, откуда а так как то мы снова получили противоречие: .

Второе доказательство. Другое доказательство леммы 4.4 основано на теореме Жордана о кривой, в которой утверждается, что простая замкнутая кривая (гемеоморфная окружности) делит плоскость на две области, общей границей которых является сама кривая. Следствием этой теоремы является тот очевидный факт, что простая кривая, соединяющая две точки, каждая из которых лежит в разной области, пересекает границу. Для доказательства того, что граф 2-го типа является плоским, соединим два пункта обслуживания с двумя домами, как показано на рис. 4.4, образовав жорданову кривую. Третий пункт расположен либо внутри, либо снаружи грант, ограниченной этой кривой. Предположим, он расположен внутри грани. (Если он расположен снаружи и связан с домом, то другой пункт должен быть внутри грани.) Соединим этот пункт с

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

Для доказательства того, что граф 1-го типа является неплоским, рассмотрим четыре точки, попарно соединенные друг с другом (рис. 4.5).

Рис. 4.4.

Рис. 4.5.

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

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

Теорема 4.5. (теорема Понтрягина — Куратовского). Граф является плоским тогда и только тогда, когда он не содержит подграфа, изоморфного с точностью до вершин степени 2 одному из подграфов Понтрягина — Куратовского.

(см. скан)

(см. скан)

Приведем доказательство теоремы 4.5, данное Бержем [3]. Оно существенно переработано по сравнению с вариантом первоначального доказательства Куратовского [30].

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

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

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

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

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

В случае (1) существует точка сочленения с, через которую проходит каждая цепь между Одна ко это приводит к противоречию, так как при удалении с граф распадается на две компоненты Пусть из получены соответственно присоединением ребер и

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

В силу этого по лемме 4.2 существуют две цепи, соединяющие и образующие простой цикл (т. е. они не имеют других общих точек). Следовательно, содержит простой цикл. Используем наличие этого цикла для опровержения предположелия о том, что граф неплоский.

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

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

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

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

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

кроме того, пересекают в чередующихся между собой точках

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

Рис. 4.6.

Очевидно не может совпасть с Но может случиться, что Рассмотрим все эти случаи.

1. Пусть Это приводит к графу 2-го типа, который противоречит гипотезе.

2. Пусть ей принадлежат (если то и мы получаем граф 2-го типа.

3. Если то, предположив, например, что мы получим граф 2-го типа.

4. Если то мы можем положить если это не так, то получаем либо случай 1,

либо 3. При сделанном предположении нужно рассмотреть две возможности.

(а) Цепи соединяющие имеют более одной общей вершины. В этой ситуации мы получаем граф 2-го типа.

(в) Цепи соединяющие имеют только одну общую вершину. Данная ситуация приводит к графу 1-го типа.

Как показано на рис. 4.6, случай приводит к графу 1-го типа, а все остальные случаи — к графу 2-го типа. Таким образом, мы в любом случае получаем противоречие, т. е. приходим к неплоскому графу, и теорема доказана. (Заметим, что на рис. 4.6 кружками и квадратиками показаны вершины, определяющие подграфы Понтрягина — Куратовского. Вершины на рис. 4.6 (2) и (3) соответственно должны рассматриваться как вершины степени 2.)

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

Теорема 4.6. (Маклейп). Необходимое и достаточное условие, при котором граф является плоским, состоит в том, что граф должен содержать базис цикла (см. матричное представление графов) и один дополнительный цикл такой, чтобы эта совокупность циклов ровно дважды содержала каждое ребро графа.

Теорема 4.7. (Уитии). Необходимое и достаточное условие, при котором граф является плоским, состоит в том, чтобы он имел двойственный граф (см. ниже).