2020-05-21
169
Лекция: свойства графов
Маршруты, цепи, циклы.
Определение 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 называется базой соответствующего векторного пространства, причем его размерность совпадает с цикломатическим числом .
