Элементы теории графов

Квант 1973, №8 с. 55-59 Тег OOGN

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

Что такое «граф»?

Прежде чем дать определение этого понятия, рассмотрим несколько примеров.

Пример 1. В волейбольных соревнованиях принимали участие 6 команда: $M_1$ , $M_2$ , $M_3$ , $M_4$ , $M_5$ , $M_6$ . Каждый из них встречался с каждой другой, исходы матчей приведены в таблице.

| $M_i$ | Выиграла у команда | Проиграла команда |
| :— | :— | :— |
| $M_1$ | $M_2$ , $M_3$ , $M_4$ | $M_5$ , $M_6$ |
| $M_2$ | $M_3$ , $M_4$ , $M_5$ , $M_6$ | $M_1$ |
| $M_3$ | $M_4$ , $M_5$ , $M_6$ | $M_1$ , $M_2$ |
| $M_4$ | — | $M_1$ , $M_2$ , $M_3$ , $M_5$ , $M_6$ |
| $M_5$ | $M_1$ , $M_4$ , $M_6$ | $M_2$ , $M_3$ |
| $M_6$ | $M_1$ , $M_4$ | $M_2$ , $M_3$ , $M_5$ |

На рисунке 1 каждой команда $M_i$ обозначена соответствующей мощ-

W. Voß. «Ац der Graphentheorie». «Альфа» № 6, 1972 и № 1, 1973. Перевод и обработка А. .Я. Халамайзера.

*) В этом номере публикуется еще одна статья, посвященная графам (см. стр. 49).

мочики. Точно так же структурную формулу бензола (рис. 4a) можно представить схемой, состоящей из линей и мочек (рис. 46).

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

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

Определение 1. Мы говорим, что задан граф, если данные:

некоморое конецное множество X, элементы которого изображены точки; эти элементы могут обозначать лодей, предметы, события, состояния и т. д.;
некоморое множество U упорядоченных или неупорядоченных пар (a, b), причем a∈X, b∈X; каждый подобная пара соответствует на схеме линей (связи), соединяющей точки a и b (если пара упорядочена, то направление связи указывано стрелкой).

При этом точки a и b могут иметь и более одной связи. Если для данной пары (a, b) имеется r(r > 1) таких связей, то их различают с помощью индексов, например, (a, b)₁, (a, b)₂, …, (a, b)ₙ.

Множества X и U определяют граф G = [X, U]. Граф называется направленным, если элементы множества U являются упорядоченными парами точки (см. рис. 1), и неправленным — в противном случае (см. рис. 2, 3, 4).

Элементы множества X называются вершинами графа, элементы множества U — ребрами или дуеми графа G.

Точки a и b называются концами ребра (a, b) или ребер (a, b)ᵢ.

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

Друг). На рисунке 6 даны различные изображения одного и того же графа.

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

Определение 2. Две вершины называются связными, если они соединены ребром. Говорят, что вершина инцидентна ребру, если она служит концом этого ребра.

Определение 3. Если данная вершина инцидентна в Gровно r ребрам, то r называется связностью данной вершины в G.

Так, например, на рисунке 2 вершина A имеет связность 4, вершина D имеет связность 2, остальные вершины имеют связность 1.

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

Ребра вида (a, a) мы в дальнейшем не рассматриваем, то есть исключаем из рассмотрения петли (см. рис. 7a).

Иного в графах бывают вершины, не инцидентины ни одному ребру. Такие вершины называются изолированными.

Мы будем рассматривать лишь конечные графы, содержащие конец многожество вершин и конечное множество ребер.

Определение 4. Граф G называется простым, если он не содержит двулирующих ребер, то есть любые две вершины в G связны не более чем одним ребром (на рисунке 76 имеются двулирующие ребра).

Теперь попробуйте решить несколько задач.

Задание 1. На плоскости даны n окружностей, произверованных чисlami 1, 2, . . . , n. Граф G = [X, U] определяется следующим образом: X = {1, 2, . . . , n} и (i, j)∈U тогда и только тогда, когда i-я и j-я окружности имеют не менее одной общей точки. Построите граф G для девятых окружностей, изображенных на рисунке 8.

Задание 2. Граф G называется полным, если каждые две вершины соединены одним и только одним ребром (на рисунке 9 изображены полные n-графы для n=3, 4 и 5). Сколько ребер имеет полный n-граф?

Задание 3. Представляют ли один и тот же граф рисуки 10a и 106? Рисунки 10в и 10г?

Задание 4. Определите связность вершин каждого из графов, изображенных на рисунке 5.

Некоторые теоремы и их применения

Теорема 1. Пусть |X| = n — число вершин, |U| — число ребер u

$s_1, s_2, \dots, s_n$ — связности вершин графа $G = [X, U]$ . Тогда
$\sum_{i=1}^{n} s_i = 2 |U|,$
мо есть сумма связности всех вершин графа $G$ вдвое больше числа его ребер.

Доказательство. Заменим каждое ребро двумя половинками (рис. 11). Тогда каждой половинке ребра будет инцидента одна и только одна вершина. Если вершина $a_i \in X$ имеет связность $s_i$ , то она инцидентаровно $s_i$ половинкам ребер; значит, сумма $\sum_{i=1}^{n} s_i$ равна числу всех половинок или, что то же самое, удвоенному числу ребер.

Между графами, изображены на рисунке 2 и рисунке 36, можно усмотреть одно принципиальное различие. В графе на рисунке 36 каждая вершина связана (ребрами) с любой другой; в графе на рисунке 2 вершины $E$ и $F$ не связаны с вершинами $A$ , $B$ , $C$ , $D$ . Для уяснения этого разлиния

$\text{Pic. 12.}$

чия необходимо ввести определения 5—9.

Определение 5. $(a_1, a_2) \times (a_2, a_3)(a_3, a_4) \dots (a_{n-1}, a_n)$ называется последовательностью ребер. Здесь через $a_i$ обозначает вершины, через $(a_i, a_j)$ — ребра. Последовательность ребер называется замкнутой, если $a_n = a_1$ , в противном случае она называется открытой.

Определение 6. Последовательность ребер, в котором каждое ребро графа $G$ встречается не более одного раза, называется целочкой *).

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

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

Определение 8. Замкнутая целочка, в котором каждая вершина встречается не более одного раза, называется колчом **).

Так, например, в графе на рисунке 12
$(a_1, a_2)(a_2, a_3)(a_3, a_8)(a_8, a_9) \times (a_9, a_3)(a_3, a_7)(a_7, a_4)(a_4, a_6) \times (a_6, a_5)(a_5, a_4)(a_4, a_7)(a_7, a_3) \times (a_3, a_9)(a_9, a_8)(a_8, a_3)(a_3, a_2)$
— последовательность ребер, не являющаяся пустем;
$(a_1, a_2)(a_2, a_3)(a_3, a_8)(a_8, a_9) \times (a_9, a_3)(a_3, a_7)$ — последовательность ребер;
$(a_3, a_7)(a_7, a_4)(a_4, a_3)$ — колчо;
$(a_1, a_2)(a_2, a_3)(a_3, a_7)(a_7, a_4) \times (a_4, a_5)$ — путь, связывающий вершину $a_1$ с вершиной $a_5$ .

Определение 9. Граф $G$ , в котором каждые две вершины $a_i$ и $a_j$ связны не менее чем одним путем, называется связным.

*) По определению 5 целочка может быть открытой или замкнутой.

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

Несвязный граф состоит по меньшей мере из двух связных компонент.

Так, например, графы на рисунках 13 в, г, д, е — несвязные и состоят соответственно из 2, 2, 4, 3 компонент.

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

Не показется ли вам странным следующее высказание:

Число людей, какный из которых имеет нечетное число друзей, является четным?

С помощью теоремы, к рассмотрению которой мы переходим, нетрудно доказать это высказание.

Теорема 2. В каждом связи графе G число вершин нечетной связности четно.

Доказательство. Обозначим сумму связности «нечетных» вершин (то есть сумму нечетных x слагаемых в формуле ()) через Σ₁, а сумму связности «четных» вершин (то есть сумму четных слагаемых в ()) через Σ₂. Тогда по теореме 1

$\Sigma_1 + \Sigma_2 = \sum_{i=1}^{|X|} s_i = 2 |U|,$

откуда

$\Sigma_1 = 2 |U| - \Sigma_2. \quad (*)$

Числа 2 |U| и Σ₂, а следовательно, и их разность, стоящая в правой части равенства (**), четны, а потом и левая часть (сумма нечетных слагаемых — Σ₁) — число четное. Далее легко доказать (от противного), что количество (нечетных!) слагаемых в этой сумме — четное. Теорема доказана.

Предоставляем читателю решить следующие задачи.

Задание 5. Семеро друзей, разbezжаясь в отпуск, условиясь, что каждый из них пошлет открытки троим из остальных.

Может ли служиться, что каждый из них получит открытки именно от тех друзей, которые напишет сам?

Задание 6. Существует ли граф с шестю вершинами, связность которых 2, 3, 3, 4, 4, 4?

Задание 7. Существует ли простой граф (содержащий более одной вершины), никакие два узла которого не имеют одинаковой связности?

Задание 8. Пусть G — (конечный) простой граф, каждая вершина которого имеет связность g. Докажите, что 2 |U| = g |X|.

В «Кванте» № 3, 1973 на с. 4 была допущена опечатка. Последнее предложение в левой колонке должно выглядеть так: Это не что иное как умноженная на M

$M = \lg e = 0,43429$

относительная скорость изменения y при изменении t:

$\frac{1}{y} \lim_{\Delta t \to 0} \frac{\Delta y}{\Delta t} = \frac{y'}{y} = \ln \frac{\lg a}{M}.$