Цикломатическое число

1. Будем рассматривать подграфы, которые могут быть несвязными, но содержащие все вершины графа. Пусть G - граф, содержащий p занумерованных ребер (e₁,e₂,..,e_p) Каждому подграфу поставим в соответствие p-мерный вектор из нулей и единиц:

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

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

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

Из теоремы Эйлера можно вывести следствие:

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

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

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

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

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

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

4. Сумма двух четных подграфов любого графа есть также четный подграф. Если и - степени некоторой вершины в подграфах и соответственно, а – ее степень в пересечении , то степень s(α)

вершины в подграфе равна

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

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

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

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

.

Число v называется цикломатическим числом графа.