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

Квант 1981, №7 с. 11, 13, 14, 15, 16 Тег 1T1R

В. Болтянский

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

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

Три домика и три колодца

Граф $A$ называется вложимым в плоскость, если существует на плоскости граф $A'$ , геометрный $A$ . Так, граф, составленный из ребер tetraэдра, и граф, составленный из ребер куба, вложимы в плоскость (рис. 1).

Приведем два примера графов, не вложимых в плоскость.

Пример 1 («домики и колодцы»). На плоскости даны шесть точек: $D_1, D_2, D_3$ (домики) и $K_1, K_2, K_3$ (колодцы); можно ли на плоскости проведи тропики от каждой домика к каждой колодцу так, чтобы никакие две тропики не пересекались?

Рис. 1.
Рис. 2.

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

Позному достаточно установить справедливо доказываемого утверждения в случае, когда каждый из циклов $x, y$ состоит из одной ломанной, домашорфной окружности. Сдвинув чуть-чуть вершины циклов $x$ и $y$ , мы можем добиться того, чтобы индекс $I(x, y)$ не изменился и никакой отрезок, входящий в цикл $x$ , не был паралелен никакому отрезку, входящему в $y$ . Выберем террь прямую $l$ , не паралелную ни одной прямой, соединяющей какую-либо вершину цикла $x$ с какой-либо вершиной цикла $y$ , и будем непрерывно перемещать цикл $x$ (как твердое целое) паралелно прямой $l$ (рис. 5). Индекс пересечения $I(x, y)$ мог бы изменяться лишь в те моменты, когда вершины двужущего цикла $x$ проходят через ребра неподвижного цикла $y$ или когда ребра цикла $x$ проходят через вершины цикла $y$ (вершины цикла $x$ не могут попасть в вершины цикла $y$ в силу выбора прямой $l$ ). Однако, как показывает рисунок 6, в момент, когда неокоторое ребро $a$ цикла $x$ проходит через вершину $q$ цикла $y$ , число точек пересечения не меняет свое четность, а потому индекс пересечения $I(x, y)$ не меняется. То же происходит и при прохождения вершин цикла $x$ через ребра цикла $y$ .

Итак, в течение всего движения индекс пересечения не меняется, является инвариантом. Но в конце концов цикл $x$ попадает в положение, в котором он совсем не имеет общих точек с $y$ (см. рис. 5), так что индекс пересечения становится равным нулю. Следовательно, и первоначально было $I(x, y) = 0$ .

Невложимость полного пативершинного графа

Теперь мы в состоянии доказать, что граф $P_2$ , рассмотренный в примере 2, не вложим в плоскость. Соединним ломаными попарно 5 точек на плоскости, не обращая пока внимание на пересечения. Ребра-ломаны, не имеющие общих концов, условия называются нестеменными. Обозначим через $J$ сумму индексов пересечения по всем параметRESх ребер. Конечно, число $J$ зависит от того, каким образом нарисованы на плоскости ребра. Если бы их удалилось нарисовать без пересечений, число $J$ оказалось бы равным нулю. Однако мы доказем, что при любом

способ проверения ребер число J оказывает нечетным. Тем самым будет доказано, что граф $P_2$ не вложим в плоскость.

Предположим, что мы меняем положение одного ребра, скажем $M_1M_2$ . Первоначальное положение этого ребра обозначим через $x$ , а его новое положение через $x'$ . Несмежными с ребром $M_1M_2$ являются три ребра ( $M_3M_4$ , $M_4M_5$ , $M_5M_3$ ). Замкнутая ломаная $M_3M_4M_5$ (возможно, пересекающая себя) является циклом; обозначим его через $y$ (рис. 7). Ломанные $x$ и $x'$ , вместе взятые, также образуют цикл. Поскольку индекс пересечения любых двух циклов равен нулю:

$I(x \cup x', y) = 0,$

число точек пересечения ребра $x$ с циклом $y$ (то есть со всеми несмежными ему ребрами) имеет ту же четность, что и число точек пересечения ребра $x'$ с циклом $y$ .

Таким образом, при замене ребра $x$ ребром $x'$ число $J$ не меняет свое четность.

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

Итак, либо для всех расположений ребер число $J$ четно, либо для всех расположений нечетно. На рисунке 3 имеется только одна точка пересечения (разумеется, кривые ребра на этом рисунке можно заменить ломаными). Таким образом, на рисунке 3 число $J$ равно единице, а потому для любого расположения ребер оно нечетно и, значит, $P_2$ не вложим в плоскость.

Задачи

Докажите, что граф $P_1$ из примера 1 не вложим в плоскость.
Ребрами графа служат стороны и наиболее диагонали правильного $n$ -угольника

$(n > 3)^*$ . Докажите, что при четном $n$ этот граф может быть вложен в плоскость, а при нечетном — нет.

Ребрами графа служат стороны и наиболее диагонали*) правильного $2n$ -угольника. Докажите, что при $n \geqslant 3$ этот граф не вложим в плоскость.
Ребрами графа служат стороны и наиболее диагонали*) (их $2n+1$ правильного $(2n+1)$ -угольника. Докажите, что этот граф не вложим в плоскость.

Нельзя ли проще?

Выше (см. рисунки 5, 6) мы доказали, что индекс пересечения любых двух циклов на плоскости равен нулю. Возможно, читатель предложит следующое более простое доказательство: будем вигнаться по замкнутой ломаной $x$ ; в каждой точке пересечения с замкнутой ломаной $y$ мы будем либо входить во внутреннюю область ломаной $y$ , либо выходить из нее во внешнюю область; так как точки входа и точки выхода через точку число точек входа равно числу точек выхода; значит, общое число точек пересечения ломаных $x$ и $y$ четно.

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

Teорема Жордана

Замкнутая линия, гомеomorphная окружности, называется простой замкнутой.

*) Притом «диагонали» учитку приподняты в пространство и поэтому попарно не пересекаются.

нутой линей. Теорема Жордана состоит в том, что всякая простая замкнутая линия, расположенная на плоскости, разбивает эту плоскость на две области (внутреннюю и внешнюю). Поясим смысл этой теоремы. Пусть $l$ — простая замкнутая линия на плоскости. Возьмем точки, $p, q$ , не лежащие на линии $l$ . Если $p$ и $q$ можно соединить ломаной, не пересекающейся с $l$ , то считают, что точки $p$ и $q$ лежат в одной и той же области относительно линии $l$ . Если же любая ломаная, соединяющая точки $p$ и $q$ , обязательно пересекает $l$ , то считают, что $p$ и $q$ лежат в разных области. Теорема Жордана утверждает, что линия $l$ определяет на плоскостировно две области.

Не следует думать, что теорема Жордана утверждает нечто совершенное. Каждыйся ее «очевидность» объясняется лишь тем, что на ум обычно приходит очень простые линии (окружность, контур выпуклого многоугольника и т. п.). В общем же случае утверждение

Рис. 8.

нце теоремы Жордана не так уж очень видно. На рисунке 8 изображена простая замкнутая ломана (это можно проверить, обведя линию карандашом). Однако вовсе не очень видно, что плоскость разрезана этой линии на две области; например, далеко не сразу поняты, в какой области (внутренней или внешней) лежат точки $a, b, c, d$ .

Мы приведем доказательство теоремы Жордана, основанное на применении индекса пересечения. При этом ограничимся случаем, когда $l$ — не произвольная простая замкнутая линия на плоскости, а простая замкнутая ломана.

Пусть $b_1, b_2, \dots, b_n$ — последовательные звенья ломаной $l$ . Проведем отрезок, пересекающий звено $b_1$ в точке $a$ , и возьмем на этом отрезке две точки $p, p'$ , расположенные по разные стороны звена $b_1$ на одном и том же расстоянии от него. Через точки $p$ проведем отрезок, параллельный звену $b_1$ , до точки его пересечения с биссертрикой угла между звеньями $b_1$ и $b_2$ (рис. 9). Из этой точки пересечения проведем отрезок, параллельный $b_2$ , до пересечения с биссертрикой угла между звеньями $b_2$ и $b_3$ и т. д. В результате мы получим ломаную $x$ , звенья которого находится на одном и том же расстоянии от соответствующих звеньев ломаной $l$ . Если при этом точка $p$ была взята достаточно близко к $a$ , то построенная линия $x$ не пересекает $l$ , и проядь вдоль линии $l$ , должна вернуть либо в точку $p$ , либо в $p'$ . Легко понять, однако, что в точку $p'$ ломаная $x$ принадлежит если бы ломана $x$ соединяла точки $p$ и $p'$ , то, присоединив к $x$ отрезок $pp'$ , мы получили бы цикл, который с циклом $l$ пересекается в единственной точке $a$ , то есть индекс пересечения этих двух циклов был равен 1, что невозможно. Итак, $x$ представляет собой замкнутую ломаную, выходящую из точки $p$ , один раз проходящий вдоль ломаной $l$ и возвращающийся в точку $p'.$ Аналогично получается замкнутая ломана $x'$ , выходящая из $p'$ , один раз проходящий вдоль ломаной $l$ и возвращающейся в точку $p'$ .

Пусть теперь $c$ — произвольная точка, не лежащая на линии $l$ . Тогда ее можно содействить, не пересекая $l$ , либо с точкой $p$ , либо с точкой $p'$ : достаточно проверки из точки $c$ луч, пересекающий линии $x, x'$ , и от точки $c$ пройти до первой точки пересечения этого луча с какой-либо из линии $x, x'$ , а затем по этой линии до точки $p$ или $p'$ .

Нетрудно понять, что если из точки $c$ проведены две различные ломаны $y, z$ , не пересекающие $l$ и оказывающиеся в одной из точки $p, p'$ , то обе они оказываются в одной и той же точке. В самом деле, если бы ломана $y$ соединяла точку $c$ с $p$ , а ломана $z$ соединяла точку $c$ с $p'$ (рис. 10), то ломана $y \cup z$ вместе с отрезком $pp'$ составляла бы цикл, индекс пересечения которого с циклом $l$ равнялся 1, что невозможно.

Тепер уже нетрудно доказать теорему Жордана. Обозначим через $U$ множество всех точек плоскости, которые можно, не пересекая $l$ , соединить с точкой $p$ , а через $V$ — множество точки, которые можно, не пересекая $l$ , соединить с точкой $p'$ . Тогда $U$ и $V$ и будут теми двумя области, на которых линии $l$ разбиает плоскость. В самом деле, если точки

$c_1, c_2$ принадлежат одной области (скажем, $U$ ), то существует ломанные $y_1, y_2$ , не пересекающие $l$ , которые соединяют $c_1$ и $c_2$ с точкой $p$ . Объединение их представляет собой ломаную, соединяющую $c_1$ и $c_2$ и не пересекающую $l$ . Итак, две точки, принадлежшие одной области, можно соединить ломаной, не пересекающей $l$ (инначе, как и выше, мы получили бы цикл, имеющий с $l$ индекс пересечения 1).

Тем самым теорема Жордана (для случая простой замкнутой ломаной) доказана.

Заметание. Все «далекие» точки плоскости расположены в одной и той же области относительно линии $l$ (рис. 11). Поэтому одна из двух области, определяемых линей $l$ , не ограниченная, а другой — ограниченная. Неограниченную область называют внешней, а ограниченной — внутренней. Точки внешней области характеризуется тем, что из этих точки можно проверить ломанные, не пересекающие $l$ и уходящие как уггодно daleko от $l$ ; точки внутренней области этим свойством не обладают.

Задание.

Если ломана $l$ — очень сложная, то определить «на глаз», в какой области (внутренней или внешней) лежит точка $a$ , трудно: для этого нужно выяснить, можно ли, отправляясь из точки $a$ , выйти из «лабириента», образованного линейей $l$ (см. рис. 8). Докажите, что если луч, исходящий из точки $a$ и не проходящий через вершины ломаной $l$ , пересекает $l$ в четном числе точки, то точка $a$ лежит во внешней области (то есть выбраться из «лабириента» можно), а если в нечетном, то точка $a$ лежит во внутренней области.
На плоскости проведены $k$ ломанных линии, каждой из которых соединяет две заданные точки $p$ и $q$ . Докажите, что если других ломанные попарно не имеют, то плоскость разбиита на $k$ области.