Определение

Остовным деревом связного графа G = (V, U) называется такой подграф G^* = (V, U^*) графа G , который является деревом.

Иными словами, остовное дерево графа G  это такой подграф, который получается из G удалением максимального числа ребер, не приводящим к несвязности получаемого графа.

Нетрудно видеть, что если неориентированный и не содержащий петель связный граф G имеет m вершин и n ребер, то количество удаляемых из G ребер равно n  m + 1.

Из того следует, что после размыкания всех циклов графа G, имеющего n ребер, в полученном остовном дереве содержится m 1 ребро.

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

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

5.8.1. Циклы эйлера и гамильтона

Среди циклов в графах особое место занимают циклы, содержащие либо все вершины, либо все ребра графа.

ОПРЕДЕЛЕНИЕ

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

Например, для графа G, изображенного на рис. 5.17., имеется цикл Эйлера, а граф G₁ такого цикла не имеет.

G G₁

Рис. 5.17

Для тривиального графа, состоящего из единственной вершины, цикл Эйлера  это цикл длины 0 или цикл, состоящий из единственной вершины.

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

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

А A

B C

B C

D D

Рис. 5.18.

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

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

Большое число перестановок даже для графов с небольшим количеством ребер делает предложенный метод практически неприменимым.

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