- •Глава 3. Графы
- •§ 3.1. Основные понятия
- •3.1.1. Определения, элементы, способы задания
- •3.1.2. Прямое произведение графов
- •3.1.3. Подграф. Связный граф. Компоненты связности графа
- •3.1.4. Матрица смежности и матрица инцидентности графа
- •§ 3.2. Деревья и леса
- •§ 3.3. Циклы на графе
- •3.3.1. Цикломатическое число графа. Пространство циклов
- •3.3.2. Эйлеровы и гамильтоновы пути и циклы
- •§ 3.4. Планарные графы
- •§ 3.5. Раскрашивание графов
- •Упражнения для самостоятельного решения
§ 3.3. Циклы на графе
3.3.1. Цикломатическое число графа. Пространство циклов
Цикломатическим числом графа называется число
(6)
Это число обладает следующими свойствами:
для любого графа
если – разложение графа на компоненты связности, то
– лес.
Упражнение 3.18. Найти количество компонент связности леса, имеющего 18 вершин и 10 рёбер.
Решение. Пусть – данный граф. Так как – лес, то По формуле (6) получаем: Отсюда Таким образом, имеет 8 компонент связности.
Упражнение 3.19. Сколько рёбер может быть у графа, имеющего 12 вершин и состоящего из 3 компонент связности?
Решение. Наименьшее количество рёбер можно получить из неравенства Имеем: Отсюда Ровно 9 рёбер будет у графа, все компоненты связности которого являются деревьями: например, если одна из компонент – цепь из 9 вершин, а две другие – изолированные точки.
Найдём наибольшее значение Р. Начнём с общего рассуждения. Пусть, к примеру, граф с вершинами состоит из двух не соединяющихся между собой подграфов и Если и то наибольшее число рёбер графа равно (это соответствует случаю, когда и – полные графы. Так как то наибольшее количество рёбер в равно Это выражение является квадратичной функцией от с положительным коэффициентом перед поэтому наибольшее значение эта функция будет принимать при крайних значениях т.е. когда или Аналогичный результат получится и в случае, когда граф разбивается на 3 или большее число частей. В нашем случае наибольшее число рёбер у графа будет, когда одна компонента связности – полный граф с 10 вершинами, а две другие – изолированные точки. В этом случае число рёбер равно Таким образом, мы имеем: Покажем, что любое число из этого диапазона будет числом рёбер некоторого графа. Действительно, если одна компонента связности – цепь с 10 вершинами, а две другие – изолированные точки, то Возьмём эту цепь и будем добавлять к ней по одному ребру, пока не получится полный граф. Тогда количество рёбер будет принимать все значения 9, 10, …, 45.
В этом разделе мы будем называть циклами как обычные циклы, так и объединения обычных циклов (иногда их называют “циклами” (в кавычках) или обобщёнными циклами). Сложение циклов осуществляется следующим образом: берём все рёбра, входящие в эти циклы, и удаляем общие рёбра (см. рис. 3.24).
Пусть дан граф Тогда все циклы (в широком смысле) этого графа будут образовывать линейное пространство над полем если рассматривать операцию сложения циклов и умножение на элементы поля
Определим теперь двоичную запись циклов графа. Пусть – граф и – все его рёбра. Тогда каждый цикл представляется в виде строчки из 0 и 1 длины где
Нетрудно видеть, что сложение циклов при таком кодировании будет соответствовать покомпонентному сложению строк по модулю 2. Приведём пример. Пусть дан граф, изображённый на рисунке 3.25.
Р ассмотрим его циклы Так как в графе 7 рёбер, то циклы будут записываться в виде двоичных последовательностей длины 7. Так как состоит из рёбер то в 1-й, 2-й и 3-й позициях будут стоять 1, а в остальных нули. Таким образом, Аналогично получаем: Сложим и
что соответствует правилу сложения циклов.
Рассмотрим теперь линейное пространство циклов графа Так как граф конечный, то пространство имеет конечный базис, т.е. совокупность циклов которые обладают свойствами:
1) линейно независимы;
2) любой цикл данного графа является линейной комбинацией циклов с коэффициентами 0 или 1:
где Число элементов базиса называется размерностью пространства и обозначается Оказывается, что число совпадает с цикломатическим числом графа.
Теорема. Пусть – граф и – его цикломатическое число. Тогда:
в графе существуют рёбер таких, удаление которых превращает в лес, имеющий те же компоненты связности (по вершинам), что и граф
Для связного графа справедливо следующее утверждение.
Следствие. Если – связный граф и то в графе найдутся рёбер таких, что – дерево.
Дерево называется остовным деревом графа Остовное дерево выбирается неоднозначно. Например, в графе на рисунке 25 – остовные деревья.
Приведём алгоритм построения базиса пространства циклов графа Пусть
Если то – лес, и искомый базис – пустое множество. Пусть Тогда в есть хотя бы один непустой цикл. Обозначим его через Возьмём любое ребро из этого цикла: Удалим это ребро из графа Получим граф У него Если то – базис пространства Если то находим в графе цикл его ребро и т.д. В конце концов мы получим циклы образующие базис пространства и рёбра удовлетворяющие требуемым условиям.
Упражнение 3.20. Построить базис пространства циклов графа
Решение. Граф изображён на рисунке 5. Сделаем другой, более удобный рисунок 3.26.
У этого графа поэтому Следовательно, нам надо найти 4 базисных цикла. Проверим, что это будут циклы В двоичной записи Составим из координат этих векторов матрицу
Минор этой матрицы, составленный из элементов первых 4 столбцов, равен
поэтому строки матрицы линейно независимы. Это означает, что векторы пространства линейно независимы над полем а так как размерность пространства равна 4, то – его базис. Любой цикл является линейной комбинацией базисных. Например, если то
Упражнение 3.21. Сколько всего циклов имеет граф у которого
Решение. Пусть – пространство циклов. Тогда Таким образом, у графа имеется 5 базисных циклов Все остальные циклы – линейные комбинации базисных с коэффициентами 0 или 1. Например, Общий вид циклов такой: где Значит, всего циклов Среди них могут быть “ненастоящие” циклы, т.е. циклы, являющиеся объединениями простых циклов, и обязательно будет пустой цикл – цикл, у которого нет ни одного ребра.