Таблица 6.3

Матрица базисных циклов

		Хорды
	3,8	2,8	7,8	5,8
БЦ1	1
БЦ2		1
БЦ3			1
БЦ4				1

Ребра остова

2,3	1,2	1,7	1,8	8,4	7,6	6,5
1	1		1
	1		1
		1	1
		1	1		1	1

6.4.3. Базисные разрезы и ранг

Удобно также определить коциклический ранг или ранг разреза графа G как число ребер в его остовном лесе. Коциклический ранг обозначается через χ(G) и равен (n – k).

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

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

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

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

Чтобы не ошибиться в построении базисного разреза, можно отдельно нарисовать остов графа и именно на его основе определять,

164

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

Задача 6.4. Построим матрицу базисных разрезов для графа на рис. 6.20, при условии, что остов выбран в соответствии с вариантом 1.

	2	3	2		3
1	8	4	1	8	4
	7	5	7		5
	6			6
	Исходный граф			Остов
			Рис. 6.21

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

Например, возьмем ребро остова (2,3) (рис. 6.21, справа). При его удалении из остова собирается «отколоться» от остального графа вершина 3. В исходном графе вершина 3 будет удерживаться еще и хордой (3,8) (рис. 6.21, слева).

При удалении ребра (1,2) из остова собирается «отколоться» от остального графа пара вершин (3 и 2), вместе с соединяющим их ребром (2.3) (рис. 6.21, справа). В исходном графе эта группа вер-

165

шин будет удерживаться еще и хордами (3,8) и (2,8) (рис. 6.21, слева).

Аналогично находим остальные разрезы (табл. 6.4).

Таблица 6.4

Матрица базисных разрезов

	Хорды
	3,8	2,8	7,8	5,8
БР1	1
БР2	1	1
БР3			1	1
БР4	1	1	1	1
БР5
БР6				1
БР7				1

Ребра остова

2,3 1,2 1,7 1,8 8,4 7,6 6,5

1

1

1

1

1

1

1

6.4.4. Эйлеровы графы

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

Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.

Эйлеров граф	Граф, в котором есть не-
	замкнутая эйлеровая цепь

Неэйлеров граф

Рис. 6.22

166

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

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

Теорема 6.6. Граф G обладает эйлеровым циклом тогда и только тогда, когда он является связным, а все его вершины – четными.

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

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

Задача 6.5. Определить, является ли граф (рис. 6.23) эйлеровым, и, если нет, указать с достаточным обоснованием, удаление какого минимального числа ребер делает граф эйлеровым. Указать, какие это ребра. Указать эйлеров цикл.

Решение. Первое, что необходимо сделать, это проверить критерий эйлеровости, а именно четность вершин графа. Как видно из рис. 6.23, б, в графе из n=10 вершин 8 имеют нечетную степень.

Удобно при решении задач на рисунке заштриховать вершины, которые имеют нечетную степень. Поскольку удаление одного ребра может исправить степень двух вершин, то если удалять попарно несмежные ребра, соединяющие только нечетные вершины, минимально возможное количество таких кандидатов на увольнение будет 8/2=4. Теперь нужно попробовать найти попарно несмежные ребра, соединяющие именно нечетные вершины. В данном случае это возможно: решением могут быть, например, ребра

(1,2), (4,5), (7,8), (6,10) (рис. 6.23, в)

167