Цикломатическое число и его свойства

Лекция: свойства графов

Маршруты, цепи, циклы.

Определение 1. а) Чередующаяся последовательность вершин и ребер графа G (неориентированного), начинающаяся и завершающаяся вершинами, называется маршрутом, который называется циклическим, если его начальная и конечная вершины совпадают. Длина маршрута – число встречающихся в нем ребер.

б) Маршрут называется цепью, а циклический маршрут – циклом, если каждое его ребро встречается в нем не более одного раза (вершины в цепи и цикле могут повторяться и несколько раз).

г) Цепи и циклы называются простыми, если в них никакие вершины не повторяются.

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

Компонентой графа называется его подграф, каждые две вершина которого можно соединить цепью.

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

. .

Определение 3. Если , то граф G называется связным, если же , то G называется несвязным графом.

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

Цикломатическое число и его свойства.

Определение 1. Цикломатическое число  графа G определяется формулой

.

Оно является второй структурной характеристикой графа G и также называется числом Бетти размерности 1, а число – рангом графа G. Цикломатическое число , так как справедлива простая

Теорема 1. Пусть мультиграф  получен из мультиграфа G добавлением нового ребра между . Если  или  и  могут быть соединены цепью в G, то  и , иначе,  и .

Отождествим каждый цикл m мультиграфа G с вектором . Для этого придадим каждому ребру G произвольную ориентацию и положим, что при прохождении цикла m через ребро  в направлении его ориентации координата вектора , а в противоположном направлении .

Полученный таким образом вектор  размерности  называется вектором-циклом, соответствующим циклу m. Циклы называются независимыми, если соответствующие им векторы линейно независимы (это свойство не зависит от выбора ориентации ребер).

Справедлива

Теорема 2. Цикломатическое число  мультиграфа G равно наибольшему числу независимых циклов.

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