2 4 E3

e₁₁

e₁₃

e₁₄

e₄

e₁₂

e₁₅

e₁₆

1

5

e₉

e₅

e₈

e₁₀

6

e₆

8

e₇

7

3

e₂

e₁

2

4

e₃

e₁₁

e₁₃

e₁₄

e₁

e₄

e₁₂

e₁₅

e₁₆

1

5

e₉

e₅

e₈

6

e₆

8

e₇

7

3

e₁

e₂

2

4

e₁₁

e₁₃

e₁₄

e₁

e₄

e₁₂

e₁₅

e₁₆

1

5

e₉

e₅

e₈

e₁₀

6

e₆

8

e₇

7

3

e₁

e₂

2

4

e₃

e₁₁

e₁₃

e₁₄

e₁

e₄

e₁₂

e₁₆

1

5

e₉

e₅

e₈

e₁₀

6

e₆

8

e₇

7

3

e₁

e₂

2

4

e₃

e₁₁

e₁₃

e₁₄

e₁

e₄

e₁₂

e₁₅

e₁₆

1

5

e₉

e₅

e₁₀

6

e₆

8

e₇

7

3

e₁

e₂

2

4

e₃

e₁₁

e₁₃

e₁₄

e₁

e₄

e₁₂

e₁₅

e₁₆

1

5

e₉

e₅

e₈

e₁₀

6

8

e₇

7

3

e₁

e₂

2

4

e₃

e₁₁

e₁₄

e₁

e₄

e₁₂

e₁₅

e₁₆

1

5

e₉

e₅

e₈

e₁₀

6

e₆

8

e₇

7

3

e₁

e₂

2

4

e₃

e₁₁

e₁₃

e₁₄

e₁

e₄

e₁₂

e₁₅

e₁₆

1

5

e₅

e₈

e₁₀

6

e₆

8

e₇

7

Матричная теорема о деревьях (Кирхгоф).

Пусть граф G = (V, E) имеет множество вершин V = {v₁,…,v_p} и ребер Е. Пусть А есть матрица смежности (соседства вершин) графа G, M есть матрица, полученная из матрицы −А заменой элемента i главной диагонали на степень вершины v_i, то есть на число ребер, принадлежащих вершине v_i.

Стягивающее дерево графа G есть наименьшее по числу ребер подграф-дерево графа G, соединяющее все вершины в G.

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

Для графа G вычисления дают следующее:

Матрица смежностей: M = − A:

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

┌ ┐ ┌ ┐

1 0 1 0 1 1 1 0 1 1 4 -1 0 -1 -1 -1 0 1

2 1 0 1 1 0 0 1 0 2 -1 4 -1 -1 0 0 -1 4

3 0 1 0 1 1 0 1 1 3 0 -1 4 -1 -1 0 -1 0

А = 4 1 1 1 0 1 1 1 0 , M = 4 -1 -1 -1 6 -1 -1 -1 1,

5 1 0 1 1 0 1 0 0 5 -1 0 -1 -1 4 -1 0 0

6 1 0 0 1 1 0 1 1 6 -1 0 0 -1 -1 4 -1 1

7 0 1 1 1 0 1 0 1 7 0 -1 -1 -1 0 -1 4 1

8└ 1 1 1 0 1 1 1 0 ┘ 8 └ -1 0 -1 -1 4 -1 0 1 ┘

┌ ┐

4 -1 0 -1 -1 0

-1 4 -1 0 0 -1

A₄₄ = (−1)⁴⁺⁴ 0 -1 4 -1 0 -1 = 1543.

-1 0 -1 4 -1 0

-1 0 0 -1 4 -1

0 -1 -1 0 -1 4

└ ┘

Ответ: Фундаментальная система циклов: {С₁, С₂, С₃, С₄, С₅, С₆, С₇, С₈, С₉};

Множество хорд: H = {е₁, е₁₀, е₃, е₁₅, е₈, е₆, е₁₃, е₉, е₄};

Все фундаментальные сечения (разрезы): H{(2, 3)}, H{(5, 6)}, H{(2, 7)}, H {(1, 5)}, H {(4, 6)}, H {(4, 7)};

Число каркасов данного графа det[M] = 1543.

Задание 5.21

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

G=(V,E)=(V={1,2,3,4,5,6,7,8,9}, E={(1,8),(1,9),(2,5),(2,9),(3,5),(3,6),(3,7),(3,9), (4,5),(4,9),(5,6),(7,9),(8,9)}

Решение:

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

Исходим из ребра (4,9). Последовательное его расширение ребрами приводит нас к каркасу (стягивающему дереву).

T={(4,9),(1,9),(8,9),(2,9),(7,9),(3,7),(3,5),(5,6)}

Множество хорд

H=E-T={(1,8),(2,5),(3,6),(3,9), (4,5)}

Последовательно возвращаем в каркас по одной хорде и получаем фундаментальную систему из шести циклов:

С₁=1981, С₂=2917352, С₃=3563, С₄=39253, С₅=54925.

Всякий фундаментальный разрез составят хорды плюс одно произвольное ребро каркаса. Все фундаментальные разрезы:

H{(4,9)}, H{(1,9)}, H{(8,9)}, H{(2,9)}, H{(7,9)}, H{(3,7)}, H{(3,5)}, H{(5,6)}.

Задание 6.21

В нагруженном графе G из задачи 1 найти кратчайший (наименьший по весу) каркас и соответствующее множество хорд, фундаментальную систему циклов, все фундаментальные сечения (разрезы). Вес w_ij неориентированного ребра (v_i,v_j) с i<j равен N(i²+j²)+ i²+j² +i+j по модулю 10 (остаток от деления w_ij на 10). N есть номер варианта (N=21).

G=(V,E)=(V={1,2,3,4,5,6,7,8,9}, E={(1,8,9),(1,9,6),(2,5,2),(2,9,1),(3,5,0),(3,6,9),(3,7,4),(3,9,2), (4,5,7),(4,9,9),(5,6,9),(7,9,6),(8,9,7)}

Решение:

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

Исходим и ребра (3,5,0). Последовательное его расширение ребрами с наименьшим весом приводит нас к каркасу:

T={(3,5,0), (5,6,9), (4,5,7), (3,7,4), (3,9,2), (1,9,6), (2,9,1), (8,9,7)} c наименьшим весом 35.

Множество хорд H=E-T={(1,8,9),(2,5,2),(3,6,9), (4,9,9),(7,9,6)}

Последовательно возвращаем в каркас по одной хорде и получаем фундаментальную систему из шести циклов:

С₁=1891, С₂=25392, С₃=3563, С₄=45294, С₅=7397

Всякий фундаментальный разрез составят хорды плюс одно произвольное ребро каркаса. Все фундаментальные разрезы:

H{(3,5,0)}, H{(5,6,9)}, H{(4,5,7)}, H{(3,7,4)}, H{(3,9,2)}, H{(1,9,6)}, H{(2,9,1)}, H{(8,9,7)}.

Задача 7.21

В данном двудольном графе G = (V₁ , V₂ , E), V₁ = { x₁ , x₂ , x₃ , x₄ , x₅ },

V₂ = { y₁ , y₂ , y₃ , y₄ , y₅ , y₆ }, найти совершенное сочетание паросочетаний. Если его нет, то указать получившееся максимальное паросочетание.

E = {(x₁ , y₆), (x₁ , y₄), (x₁ , y₁), (x₂ , y₅), (x₂ , y₆), (x₃ , y₄), (x₃ , y₂), (x₃ , y₆), (x₄ , y₃), (x₄ , y₂), (x₄ , y₅), (x₅ , y₂), (x₅ , y₁), (x₅ , y₅)}.