§ 36. Плоские p-графы

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

пересекаться лишь в вершинах. В этом случае также говорят, что граф «отображается на плоскость». Можно говорить также о возможности отображения графа на другие поверхности (сферу, тор и т. п.), но мы будем рассматривать лишь отображения на плоскость.

Например, граф на рис. 163 плоский, а граф на рис. 154 — нет.

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

Рис. 153

Рис. 154

Например, -граф на обладает девятью гранями где бесконечная грань.

Некоторые важные теоремы о плоских p-графах. Приведем несколько простых теорем, доказательства которых читатель найдет в [8].

1) Для плоского -графа с вершинами, ребрами и гранями справедливо соотношение

2) Во всяком плоскдм -графе найдется вершина, степень которой не превосходит 5.

3) Всякий плоский -граф является -хроматическим.

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

Двойственный граф плоского связного p-графа. Рассмотрим плоский связный -граф в котором нет вершин отепени, меньшей 2; поставим ему в соответствие некоторый плоский связный -граф называемый двойственным к Каждой грани графа сопоставим вершину графа каждому ребру сопоставим ребро в 62, соединяющее вершины соответствующие граням примыкающим к ребру

Например (см. рис. 155), граф (пунктирные линии и кружки) двойствен графу (сплошные линии и точки).

Заметим, что может как совпадать, так и не совпадать с Например, граф на рис. 155 является -графом, является -графом.

Использование слова «двойственный» оправдано тем, что если двойственный граф к то двойственный граф к

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

Рис. 155.

Пусть задан частичный подграф графа Будем называть куском графа относительно

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

2) а также ребро концы которого принадлежат вместе с его концами.

Алгоритм использует последовательный процесс присоединения к некоторому плоскому частичному подграфу цепи оба конца которой (и только они) — вершины Эта цепь разобьет одну из граней на две.

В качестве начального плоского графа выбирают некоторый цикл графа Чтобы перейти от подграфа предварительно рассматривают все куски графа относительно

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

1. Некоторый кусок не совместим ни с какой гранью графа Тогда граф не плоский.

2 Какой-либо кусок совместим с единственной гранью графа Тогда выберем в этом куске цепь такую, что оба ее конца (и только они) принадлежат Дополняя ребрами и вершинами этой цепи, получаем проводя внутри грани

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

Рис. 156.

Рис. 157.

Пример. Проиллюстрируем этот алгоритм на примере графа на рис. 156.

Шаг 1. Берем произвольный цикл, например , представляющий плоский граф (рис. 157, а). Грани

Куски графа относительно

Шаг 2. Определяем Все куски совместимы с двумя гранями (случай 3). Выбираем, например, цепь (1, 3, 5) из куска и проводим ее в грань В о. Эта грань в заменяется двумя гранями: внутренней к (1, 3, 5, 1) и внутренней к (1, 2, 6, 5, 3, 1) (рис. 157,б).

Куски относительно

Шаг 3. Определяем Кусок совместим лишь с одной гранью (случай 2). Цепь должна быть помещена в грань которую она разобьет на две грани: внутреннюю внутреннюю к (1, 2, 6, 3, 1) (рис. 157, в).

Куски относительно

Шаг 4. Определяем Кусок совместим с двумя нями (случай 3). Возьмем, например, цепь (1, 4, 2) и поместим ее в грань Получаем две новые грани: внешнюю к внутреннюю к (1, 4, 2; 1) (рис. 157, г). Куски относительно

Шаг 5. Определяем Кусок совместим лишь с одной гранью (случай 2). Помещаем единственную цепь в и получаем новые грани: внешнюю к (1, 4, 6, 5, 1) и внутреннюю к (2, 4, 6, 2).

Таким образом, получаем плоское изображение графа