Задачи для самостоятельного решения.

1. По заданной матрице весов графа G найти величину минимального пути и сам путь от вершины s = x₁ до вершины

t = x₆ по алгоритму Дейкстры.

2. Для графа G из задачи 1 найти величину максимального пути и сам путь между теми же вершинами.

3. По заданной матрице весов графа G найти минимальный путь по алгоритму Беллмана-Мура между вершиной s = x₁ и конечной вершиной t = x₆.

Глава 3. Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и клики

1. Деревья (основные определения)

Деревом называется связной граф, не содержащий циклов.

Любой граф без циклов называется лесом. Таким образом, деревья являются компонентами леса.

Теорема о дереве.

Пусть G = (S,U) и Card S = n, Card U = m. Тогда справедлива эквивалентность следующих утверждений.

1. G – дерево.

2. G – связной граф и m = n – 1.

3. G – ациклический граф и m = n – 1.

4. Любые две несовпадающие вершины графа соединяет единственная простая цепь.

5. G – ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

Рис. 38

Ориентированный граф называется ориентированным деревом (ордеревом), если:

1. существует ровно одна вершина , называемая корнем, которая не имеет предшествующих вершин, т.е. ;

2. любой вершине в графе G непосредственно предшествует ровно одна вершина, т.е. .

Неориентированное дерево можно превратить в ориентированное, выбрав в качестве корня произвольную вершину.

Рис. 39

Корень графа G – вершина х₆.

Подграф графа называется остовным подграфом, если

Подграф графа G называется остовным поддеревом, если и G – дерево.

Теорема Кэли.

Число различных деревьев, которые можно построить на n различных вершинах равно .

Теорема Кирхгофа.

Число остовных деревьев в связном графе G порядка равно алгебраическому дополнению любого элемента матрицы Кирхгофа В(G).

Пример.

Рис. 40

Найдём число всех остовов графа G по теореме Кирхгофа.

Матрица Кирхгофа

Таким образом, у этого графа существует 11 различных остовов.

Рис. 41

Число где m – число рёбер, n – число вершин, к – число компонент связности. Связного графа называется циклическим числом или циклическим рангом графа G, число - коциклическим рангом или корангом.

равно числу рёбер, входящих в любой остов графа G.

Теорема. Число рёбер произвольного связного неориентированного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно циклическому рангу графа G.

Следствие 1. Неориентированный граф является лесом тогда и только тогда, когда .

Следствие 2. Неориентированный граф имеет единственный цикл тогда и только тогда, когда .