Цикломатика графов

аранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 10. Цикломатика графов

Лекция 10. ЦИКЛОМАТИКА ГРАФОВ

План лекции:

1. Эйлеровы циклы и цепи.
2. Цикломатическое число графа.
3. Понятие о гамильтоновых циклах.

1. Эйлеровы циклы и цепи

Началом математической теории графов послужила задача о Кёнигсбергских мостах, поставленная Леонардом Эйлером (1707 – 1783).

Кёнигсберг (теперь Калининград) расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами, как показано на рис.1. Эйлер в 1736 г. поставил вопрос: можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Если каждый берег и острова считать вершинами графа, а каждый мост – ребром, то карту города можно представить в виде мультиграфа (рис. 1).

B

с d g g

e c d D

C

a b h a b h

A

а б

Рис. 1. Карта города (а) и эквивалентный ей граф (б)

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

Эйлер установил, что задача кёнигсбергских мостов неразрешима, и этот результат ознаменовал возникновение теории графов.

Теорема. Мультиграф обладает эйлеровым циклом тогда и только тогда, когда он связный и все его локальные степени четны.

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

Достаточность докажем индукцией по числу ребер мультиграфа. При теорема справедлива. Пусть утверждение теоремы верно для всех мультиграфов с числом ребер, не превосходящем . Для мультиграфа с числом ребер рассмотрим произвольный простой цикл. Хотя бы один такой цикл обязательно существует для графов с четными степенями вершин. Обозначим его . Далее удалим из все пройденные ребра. Получим мультиграф , в котором все вершины по-прежнему имеют четные степени, но он будет несвязным. Пусть – компоненты связности . Каждая из этих компонент представляет собой связный мультиграф с четными степенями и с числом ребер, меньшим, чем , поэтому по предположению индукции она обладает эйлеровым циклом. Обозначим эйлеровы циклы компонент . Присоединяя к циклу эйлеровы циклы , получаем эйлеров цикл мультиграфа .

Следствия.

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

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

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

Обоснование этого утверждения аналогично предыдущему.

Ребро графа , через которое проходит хотя бы один цикл, называется цикловым. Ребро, которое не входит ни в один цикл, называется перешейком или мостом. Например, в графе, изображенном на рис. 2, ребра и – перешейки, а остальные ребра цикловые.

Рис. 2. Пример разбиения ребер графа на цикловые и перешейки

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

1. Цикломатическое число графа

Рассмотрим -граф , имеющий компонентов связности. Величина

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

.

Теорема.

Доказательство. Будем удалять из графа по одному ребру и следить за изменением величины . Параметры исходного графа обозначим , а после удаления ребра – . В процессе удаления ребер возможны две ситуации:

1. Удаляемое ребро цикловое. Тогда

, , ; .

2. Удаляемое ребро – перешеек. В этом случае

, , ; .

Итак, при удалении ребра величина либо не изменяется, либо уменьшается на единицу. После удаления всех ребер получим пустой граф, для которого , , , то есть . Следовательно, в исходном графе .

Из теоремы следует, что при в графе имеется, по крайней мере, один цикл.

1. Понятие о гамильтоновых циклах

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

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

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

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

,

,

,

,

.

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

e g

c i

b k

d

j

f h

Рис. 3. Гамильтоновы циклы в задаче Киркмана

В применениях графов к играм вершины соответствуют различным позициям. Таким образом, существование гамильтонова цикла равносильно существованию циклической последовательности ходов, содержащей каждую позицию по одному разу. Примером является известная задача о шахматном коне: можно ли, начиная из произвольного поля на доске, ходить конем в такой последовательности, чтобы пройти через каждое из 64 полей и вернуться в исходное? Эта задача имеет несколько вариантов решений.

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

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

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

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

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

минимальна. Так как обычно речь идет только о конечном числе вершин, задача может быть решена перебором. Однако, никакого эффективного алгоритма решения этой задачи до сих пор не известно. Имеются некоторые частные схемы для отдельных случаев. Например, частную задачу определения кратчайшей воздушной линии, соединяющей все столицы штатов в США, просчитали до конца Данциг, Фалкерсон и Джонсон.

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

Цикломатика графов