Топология графов

5

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

Топология графов

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

Граф (конечный) — это множество точек (вершин графа), соединенных — на плоскости или в пространстве — конечным числом дуг (ребер графа), причем дуги пересекаются только в вершинах*) (рис. 1).

В большей части статьи для нас будет важно, что граф — это некотора фигура (множество всех точек дуг); выделенные точки этой фигуры —

*) В общей теории графов принято несколько иное — «абстрактное» — определение графа (ср. «Квант», 1981, № 3, с. 18).

вершины — мы будем часто игнорировать.

Какие графы одинаковы?

Ангел топологии считает одинаковыми геометрические графы — такие графы $G_1$ и $G_2$, для которых существует непрерывное (без разрывов) и обратное (без скливиный) отображение $h$: $G_1 \rightarrow G_2$ множество $G_1$ на все множество $G_2$ (такое отображение называется геометрическим*)).

*) При определении геометризма произвольных фигуры требуется еще непрерывность обратного отображения $h^{-1}$ (для конечных графов она выполняется автоматически, что нам шпенул на уход без доказательства ангел топологии).

6

Из этого определения следует, что два графа геометрины, в частности, если, как угодно изгибая и растявая ребра, но не допуская разрывов и скливианный, можно один из них наложить на другой. На рисунке 2, $a$ показано, как можно окружность превращать в восчмерку; однако это не означает, что окружность и восчмерка геометрины (ведь при этом превращении произшло скливиание двух точек). Okружность можно превращать и в полупервал, но для этого ее нужно разровать и лишь потом распрямить. Поскольку разрывы не разрешены, такое превращение не будет геометризмом; к тому же, полупервал не является графом. А вот контур треугольника и контур квадрата геометрины, и оба они геометрины окружности, что показано на рисунке 2, $6$.

Заметим, что не всегда удается, как в этом примере, реализовать геометриное отображение $h$: $G_1 \rightarrow G_2$ изгибанием, растяжением и скатнем графов в самом пространстве. Так, пара зацепленных окружностей (рис. 3) геометрина пале незацепленных, хотя в пространстве расцепить их, не разрывая, неозможно.

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

Пример 1. Будем представлять себе буквы русского алфавита в виде линей. Буквы Г, Л, М, П, С геометрины между собой. Буквы Е, У, Т, Ч, Ш, Ц, Э также геометрины между собой, но не геометрины указанным ранее буквам. Буква О не геометрина

никакой другой букве русского алфавита *).

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

Простейшие инварианты

Свойства фигур, которые сохраняются при переходе от фигуры к геометриной ей фигуре, называются тополoeческими свойствами фигур, или тополoeческими инвариантами (от латинского слова invariant — неизменный). Изучением тополoeческих свойства фигур и занимается топология.

Чаще всего применяют такие тополoeческие инварианты, которые являются числами (или других алгебраических объеками), так как

7

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

Дейстительно, доказывая, что нечто можно простить (у нас — геометорфизм $h: A \rightarrow B$), достаточно придумать один вариант этого построения. А как доказать, что нечто не льзя построить? Для этого нужно перебрать всевозможны е варианты построения (у нас — отображений $h: A \rightarrow B$) и проверить, что ни один вариант не годится (не является геометорфизмом). Но общую отображений $h: A \rightarrow B$ бесконечно много, всех не проверить. Как бы?

Здесь и помогают числовые инварианты. Пусть каждой фигуре $A$ рассматриваемого класса приписывается число $q(A)$, причем геометорфным фигурам приписываются одно и то же число. Пусть фигуры $A$ и $B$ таковы, что $q(A) \neq q(B)$. тогда они не могут быть геометорфными, нельзя построить геометорфизм $h: A \rightarrow B$!

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

Пример 2. Буква $B$ представляет собой фигуру, состоящую из двух не связанных между собой частей. Большинство остальных букв русского алфавита состоит из одного связного куска (исключение состав-ляют буквы $I$, $E$). Число связывах «кусков», из которых состоит фигура (говорят также: число компонент фигуры), является топологическим инвариантом. Поэтому буква $B$ не геометоморфна, например, букве $O$, букве $П$, букве $Ц$ и т. д.

Пример 3. На восеммерке (рис. 4, $a$) имеется такая точка $x$, что после ее удаления (рис. 4, $b$) мы получаем не связную фигуру (содержащую большее одной компоненты). Точку, обладающего этим свойством, называют разбиающей точки фигуры. Никакая отличная от $x$ точка восеммерки не является разбиающей (рис. 4, $b$).

Если точка $x$ фигуры $A$ является разбиающей, она остается такой при любом геометорфизме фигуры $A$, аналогично — для неразбиающей точки. Поэтому число разбиающих точки данной фигуры есть ее топологический инвариант, число неразбиающих точки — также топологический инвариант.

Задачи

1. Для каждой из букв русского алфавита указываете, сколько разбиающих и неразбиающих точки она содержит. Докажите, что буквы $O$, $Г$, $T$, $B$ попарно не геометорфны.

2. Докажите, что для любой натурального $n$ существует фигура, содержащая равное $n$ разбиающих точки, а также фигура, содержащая равное $n$ неразбиающих точки.

Пример 4. Пусть $A$ — граф и $x$ — его вершина. Число ребер графа $A$, сходящих в $x$, называется индексом вершины $x$ в графе $A$ (при этом netля — ребро с началом и концом в одной и той же вершине $x$ — считается за два ребра, либо она входит в $x$ двумя своими концами). На рисунке 5 вершины $a, b, c, d$ имеют индексы 1, 2, 3, 4 соответственно. Число вершин индекса $n \neq 2$, содержащих в графе, — топологический инвариант. Почему приходится исключать вершины индекса 2?

Задачи

3. Докажите, что буквы $IO$ и $Ф$ не геометорфны. Указан ие. Воспользовитесь тем, что число вершин индекса $k (k \neq 2)$ является инвариантом.

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

5. Пусть $G$ — граф. Через $a_k(G)$ обозначаем число вершин этого графа, имеющих индексы $k$. Докажите, что число ребер графа $G$

8

правно

$$\frac{1}{2} (a_1(G) + 2a_2(G) + 3a_3(G) + \dots).$$

6. Докажите, что во всяком графе число вершин, имеющих нечетный индекс, четно.

Кёнигсбергские места

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

Задачи

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

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

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

С уникурсальными графами связана задача о кёнигсбергских местах, рассмотренная еще Эйлером. В то время в Кёнигсберге было семь мест через реку Прегель (рис. 6, a). Задача состоит в том, чтобы выяснить, можно ли, прогуливаясь по городу, пройти через каждый мест точно по одному разу. Сопоставим с планом города неокоторый граф: вершина Л обозначает левый берег, Π — правый берег, А и Б — острова, а ребра графа соответствуют местам (рис. 6, б). В этом графе все четыре вершины имеют нечетный индекс. Следовательно, граф не уникурсален, и потому требуемого маршрута не существует.

Задачи

10. Докажите, что, добавив еще один мест (где уголно на плане рисуна 6, a), мы получим схему города, по которой можно пройти через каждый местровно по одному разу.

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

Как построить связный граф

Всякий граф можно «построить», добавляя одно ребро за другим (разумеется, при этом нужно будет отмечать и вершины графа). Нумерация ребер графа на рисунке 7 выбрана так, что при вычерчивании графа в соответствии с этой нумерацией все время получаются связные графы. Если бы, однako, мы занумеровали ребра в обратном порядке, то при вычерчивании у нас сначала получался бы не с вя з ный граф. Оказывается, во всяком связном графе существует такая нумерация ребер, что при вычерчивании графа в соответствии с этой нумерацией все время получается связные графы. Это утверждение можно назвать «теоремой о вычерчивании связных графов».

Задачи

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

13. Выведите из утверждения предыдущей задачи теорему о вычерчивании связных графов.

9

14. Докажите, что любые две вершины связного графа $G$ можно соединить в $G$ простой цепочка ребер — такой цепочка, что объединение ребер этой цепочки представляется собой линию, гомеomorphную отрезку.

Сколько деревьев в лесу?
Контуром в графе называется замкнутая цепочка ребер, объединение которых представляется собой линию, гомеomorphную отрезку (рис. 8). Связный граф, не содержащий ни одного контура, называется деревом (рис. 9). Докажем, что в любом дереве число вершин и число ребер $P$ связаны соотношение

$$B - P = 1.$$ (1)

Для доказательства проведем индукцию по числу ребер $P$. При $P = 1$ (дерево состоит только из одного ребра и имеет две вершины) соотношение (1) справедливо. Предположим, что для любого дерева, имеющего $n$ ребер, соотношение (1) уже доказано, и пусть $G$ — дерево, имеющее $n + 1$ ребер. Так как граф $G$ — связный, его можно получить из некоторого связного графа $G'$ добавлением одного ребра $r$. Граф $G'$ содержит $n$ ребер и тоже является деревом (почему?). По предположению индукции соотношение (1) для графа $G'$ справедливо, и потому в нем имеется $n + 1$ вершин. Заметим теперь, что только один добавляемого ребра $r$ является вершиной графа $G'$ (инчете, в силу задачи 14, при добавлении ребра $r$ в графе $G$ появился бы контур — см. рис. 10). Следовательно, при добавлении ребра $r$ в графе $G$ появляется одно новое ребро и одна новая вершина. Иначе говоря, в графе $G$ имеется $n + 2$ вершин и $n + 1$ ребер, и потому соотношение (1) для него справедливо. Проведенная индукция доказывает равенство (1) для любого дерева.

Разность $B - P$ называется эйлеровой характеристикой графа $G$ и обозначается через $\chi(G)$. Таким образом, равенство (1) означает, что эйлерова характеристика любого дерева равна 1.

Задание

15. Граф, не содержащий контуров, называется лесом. Ясно, что если граф $G$ представляется собой лес, то каждая его компонента является деревом. Докажите, что если $G$ — лес, то число деревьев, которые «растут» в лесу (то есть число компонент графа $G$), равно $\chi(G)$.

16. Докажите, что если граф $G$ является деревом, то каждые две его вершины могут быть соединены только одной простой цепкой. Верно ли обратное?

Максимальное дерево и системы токов

Пусть теперь $G$ — связный граф, не являющийся деревом. Тогда в $G$ имеется контур; пусть $r_1$ — какое-либо ребро, входящие в этот контур (рис. 11, а). Удалив из $G$ ребро $r_1$, мы получим связный граф $G'$ (поскольку концы выброшенного