назад

3.6 Эйлеровы графы.
Цикломатическое число

1. Здесь мы будем рассматривать подграфы, может быть, несвязные, содержащие все вершины графа. Пусть G - граф, содержащий р занумерованных ребер е12,.....,еp. Каждому подграфу Н G поставим в соответствие р-мерный вектор (а1, а2,..., ар) из нулей и единиц: аi = 1, если еi Н; аi = 0, если еi Н (характеристический вектор подграфа Н). Это соответствие, очевидно, взаимнооднозначное. Более того, сумме по модулю 2 подграфов Н, и Н2 - Н1 Н2 - соответствует (поразрядная) сумма по модулю 2 их характеристических векторов. Над множеством коэффициентов {0, 1} множество всех подграфов образует линейное пространство: умножение любого подграфа Н на 1 дает Н, умножение на 0- пустой подграф, т.е. подграф, не содержащий ребер и состоящий из одних изолированных вершин графа G. Нетрудно видеть, что пространство подграфов графа G и пространство характеристических векторов его подграфов изоморфны и имеют размерность р. Базисом может служить множество всех однореберных подграфов. Характеристический вектор каждого такого подграфа содержит ровно одну единицу, причем для разных подграфов - на разных местах.

2. Назовем граф четным, если степени всех его вершин - четные числа. Любую элементарную цепь (кроме цикла) в четном графе можно продлить ребром, не принадлежащим цепи, так как конец цепи имеет степень 1 в цепи и степень не меньше 2 в графе. Если граф конечен, то, продолжая цепь, мы через конечное число шагов вторично придем в уже пройденную вершину, т.е. часть полученной (уже не элементарной) цепи образует элементарный цикл, после удаления которого остается четный граф, так как все степени изменяются на четное число (2 - для вершин цикла и 0 - для вершин, не принадлежащих циклу). В этом графе можно снова выделить некоторый элементарный цикл и т.д., пока в графе не останется ни одного ребра. Таким образом, каждый конечный четный граф можно представить в виде суммы попарно не пересекающихся (по ребрам) элементарных циклов, откуда, в частности, следует, что каждое его ребро циклическое.

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

Теорема Эйлера. Для того чтобы конечный связный граф был эйлеровым, необходимо и достаточно, чтобы он был четным.

В конечном несвязном четном графе все компоненты связности - эйлеровы графы.

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

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

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

Из теоремы Эйлера можно вывести интересное следствие. В произвольном связном графе G раздвоим каждое ребро е = (V1,V2), т.е. заменим его парой кратных ребер е', е" с теми же вершинами. Степень каждой вершины удвоится и станет четной. В полученном четном графе G1 существует эйлеров цикл (а если ребра е', е" ориентировать в противоположных направлениях, то каждая вершина будет равновесной и существует эйлеров контур). Если рассмотреть его как обход графа G1, снова склеить пары е', е" в одно ребро, то в первоначальном графе G эта траектория будет (уже не простым) циклом, проходящим через каждое свое ребро ровно два раза (причем в противоположных направлениях). Итак, в каждом связном графе существует цикл, содержащий ровно 2 раза каждое ребро графа, что можно трактовать как соответствующий обход лабиринта с возвращением в начало обхода.

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

Известная задача о коммивояжере формулируется так: имеется n городов, попарные расстояния между которыми заданы. Коммивояжер желает посетить все города так, чтобы суммарная длина пути была минимальной. Это означает, что нужно найти гамильтонов путь минимальной длины в полном графе Кn, ребрам которого приписаны положительные числа - длины ребер (для варианта задачи - обхода с возвращением в начало пути - ищется минимальный гамильтонов цикл).

Последовательность перестановок, описанная ранее, может быть интерпретирована следующим образом. Рассмотрим граф Gn, вершины которого соответствуют всем (n!) перестановкам множества {1, 2,..., n},-а ребра связывают пары вершин, отличающиеся транспозицией соседних элементов (таким образом, каждая вершина соединена с (n - 1) другими вершинами). Тогда указанная последовательность соответствует гамильтонову пути в графе Gn. На рисунке 10 а,б - соответствующие иллюстрации для n = 3 и n = 4.


Рисунок 10

4. Сумма двух четных подграфов любого графа есть также четный подграф. Если s1 и s2- степени некоторой вершины в подграфах H1 и H2 соответственно, a s12- ее степень в пересечении Н1 Н2, то степень s() вершины в подграфе Н1 Н2 равна (s1 - s12) + (s2 - s12) = s1 + s2 - 2S12 (кстати, это пример применения комбинаторной формулы включения- исключения). Если s1 и s2 - четные, то s() также четное. Поэтому четные подграфы образуют подпространство в пространстве всех подграфов, которое совпадает с подпространством, натянутым на множество всех элементарных

Перейдем к выяснению размерности v этого подпространства. Пусть G - связный граф с р ребрами и b вершинами., D - некоторый его остов. Число хорд равно (р - b + 1). Каждая хорда (, β) вместе c единственной элементарной цепью [, β] D образует элементарный цикл, причем векторы всех таких циклов (для разных хорд) образуют независимую систему , так как каждый из циклов содержит ребро (свою хорду), не принадлежащее ни одному из остальных циклов системы. Отсюда v > р - b + 1.

С другой стороны, каждый четный подграф, в частности любой простой цикл выражается через циклы системы . Действительно, прибавим к четному подграфу Н те циклы из Z, которые содержат хорды графа, принадлежащие Н. Полученная сумма не будет содержать ни одной хорды (каждая хорда входит в сумму дважды: в подграф Н и в один из циклов системы ), т.е. будет некоторым подграфом дерева D, откуда следует, что это пустой подграф, так как в противном случае четный подграф (сумма Н и циклов), имеющий элементарные циклы, содержался бы в дереве D. Таким образом, v = р - b + 1.

Для несвязного графа с k компонентами связности базис пространства четных подграфов получается объединением базисов его связных компонент, а число ребер и вершин суммируется. Поэтому, если i-я компонента содержит рi ребер и bi вершин, то v = р - b + k, где , . Число v называется цикломатическим числом графа. Ввиду того, что v 0, для любого графа справедливо неравенство k b - р. Деревья - это связные графы с цикломатическим числом, равным 0

Примеры

1) Для полного графа К5 (5 вершин, C52=10 ребер)

2) Для графа на рисунке 7 имеем р=18, b = 11, k = 1, откуда v= 18 - 11 + 1 =8.

3) Рассмотрим соотнесенный неориентированный граф для графа на рисунке 106. Число его вершин равно числу перестановок из 4 элементов: 4! = 24. Степени всех вершин равны 3. Поэтому число ребер графа р = 24 ∙ 3 / 2 = 36. Граф связен, т.е. k = 1. Цикломатическое число равно v = 36 -24+ 1 = 13.

 

Вопросы для самоконтроля

  1. Дайте определение четного графа, эйлерового графа.
  2. Сформулируйте теорему Эйлера.
  3. Дайте определение гамильтонову пути.
  4. Чему равно цикломатическое число и для чего оно служит?

Практические задания

Tест для самоконтроля