Как найти количество остовов графа

Вариант №39.

Задание.
Найти число остовов графа, нарисовать
их и найти остов минимального веса.

Решение:

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

Матрицей
Кирхгофа графа G называется матрица:

Алгебраические
дополнения всех элементов матрицы
Кир­хгофа равны между собой.

Составим матрицу
Кирхгофа для данного графа:

Отсюда алгебраическое
дополнение, например, элемента

равно 21.

Значит, и число
остовов данного графа равно 21.

Изобразим их:

Найдем остов
минимального веса с помощью алгоритма
Краскала.

Шаг 1.
Установка начальных значений.

Введем матрицу
длин ребер C:

Шаг 2.
Выберем ребро минимальной длины.

Минимальная длина
ребра равна 390. Это ребро (2,3). Построим
граф G₂,
состоящий из данного ребра и инцидентных
ему вершин 2 и 3. Положим i = 2.

Шаг 3.
Так как n
= 6, то i ≠ n,
поэтому переходим к шагу 4.

Шаг 4.
Строим граф G₃,
добавляя к графу G₂
новое ребро минимальной длины, выбранное
среди всех ребер графа G, каждое из
которых инцидентно одной из вершин 2,
3 и одновременно инцидентно какой-нибудь
вершине графа G, не содержащейся в G₂,
т.е. одной из вершин 1, 4, 5, 6. Таким образом,
нужно выбрать ребро минимальной длины
из ребер (2,4), (2,6), (3,6). Такое ребро имеет
длину 468 и оно одно: (2,4). Вместе с этим
ребром включаем в G₃
вершину 4, не содержащуюся в G₂.
Полагаем i = 3 и переходим к шагу 3.

Шаг 3.
Так как i ≠ n,
поэтому переходим к шагу 4.

Шаг 4.
Строим граф G₄,
добавляя к графу G₃
новое ребро минимальной длины из ребер
(3,6), (2,6), (4,5), (4,6). Такое ребро имеет длину
624 и оно одно: (2,6). Вместе с этим ребром
включаем в G₄
вершину 6, не содержащуюся в G₃.
Полагаем i = 4 и переходим к шагу 3.

Шаг 3.
Так как i ≠ n, поэтому переходим к шагу
4.

Шаг 4.
Строим граф G₅,
добавляя к графу G₄
новое ребро минимальной длины из ребер
(4,5), (6,5). Такое ребро имеет длину 702 и оно
одно: (4,5). Вместе с этим ребром включаем
в G₅
вершину 5, не содержащуюся в G₄.
Полагаем i = 5 и переходим к шагу 3.

Шаг 3.
Так как i ≠ n, поэтому переходим к шагу
4.

Шаг 4.
Строим граф G₆.
Осталась только одна вершина в графе
G,
не включенная в G₆
– это вершина 1. Так как инцидентное ей
ребро только одно, то добавим его в граф
G₆
вместе в вершиной 1. Полагаем i = 6 и
переходим к шагу 3.

Шаг 3.
Так как i = n, то граф G₆
– искомое минимальное остовное дерево.

Суммарная длина
ребер равна 390 + 468 + 624 + 702 + 468 = 2652.

Процесс построения
минимального остовного дерева:

5)
Задание.
Найти нижнюю и верхнюю оценки числа
внутренней устойчивости неориентированного
графа, заданного своей матрицей смежности
m:

Решение:

Для
всех единиц выписываются парные
дизъюнкции:

Приведем
выражение к ДНФ:

Число
внутренней устойчивости равно 2.

Задание.
Построить матрицу смежности, найти её
3-ю степень и число ориентированных
маршрутов длины 3 из вершины 1 в вершину
4.

Решение:

Матрица смежности
A = (a_ij)
– это квадратная матрица порядка n, где
n – число вершин, у которой:

Матрица смежности
данного графа:

Найдем её третью
степень:

Длиной маршрута
называется количество ребер в нем.

Для определения
маршрутов, состоящих из k ребер (дуг),
необходимо возвести в k-ю степень матрицу
смежности вершин A.
Тогда элемент матрицы

даст количество маршрутов длины k
(состоящих из k ребер) из вершины

в вершину
.

Таким образом,
число ориентированных маршрутов длины
3 из вершины 1 в вершину 4 равно элементу

= 4.

Задание.
Построить
матрицу инциденций и найти число остовов.

Матрицей
инцидентности B = (b_ij)
ориентированного графа называется
прямоугольная матрица (n×m), где n – число
вершин, m – число ребер, у которой:

Матрица
инциденций данного графа:

Составим
матрицу Кирхгофа для данного графа:

Отсюда
алгебраическое дополнение, например,
элемента

равно 0.

Значит,
у данного графа остовов нет.

Соседние файлы в папке Diskretka

• #
• #
• #

  08.12.201732.77 Кб9DM_MP-2ab_pr_1_2013.xls

• #
• #
• #

Лемма:

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

Доказательство:

Заметим, что смена нумерации вершин и нумерации ребер графа приводит к перестановке строк и перестановке столбцов матрицы . Рассматриваемый минор при этом может сменить лишь знак. Пусть — вершина, соответствующая строке матрицы , не вошедшей в матрицу минора . Пусть не является деревом. Тогда граф несвязен. Пусть — множество вершин некоторой компоненты связности графа , не содержащей . Если , то — изолированная вершина и в матрице минора имеется нулевая строка, поэтому . Пусть . С помощью подходящей перенумерации вершин и ребер из матрицу приведем к клеточному виду , где — матрица инцидентности ориентации компоненты , а вершине отвечает строка, проходящая через . Каждый столбец, проходящий через , содержит точно одну единицу и точно одну (остальные элементы равны нулю). Следовательно, сумма первых строк равна . Так как первые строк входят в матрицу минора , имеем . Пусть является деревом. Заново перенумеруем вершины и ребра графа с помощью следующей процедуры. В качестве возьмем одну из висячих вершин дерева , отличную от . Через обозначим инцидентное ей висячее ребро. Рассмотрим дерево . Если его порядок , то через обозначим одну из висячих вершин, отличных от , а через — инцидентное ей висячее ребро. Положим . Продолжаем этот процесс до тех пор, пока не получим одноэлементное дерево , единственной вершиной которого обязательно будет вершина . Получим нумерацию вершин и нумерацию ребер . В новой нумерации матрица приведется к виду , причем вершине отвечает последняя строка (здесь каждый диагональный элемент равен или , а через обозначены элементы матрицы, значения которых не вписаны в явном виде). Таким образом, матрица минора имеет треугольный вид и .

Определение:

Пусть и — соответственно — матрица и — матрица, где . Положим . Минор порядка матрицы называется соответствующим минором минору порядка матрицы , если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.

Теорема (Формула Бине-Коши[1]):

Определитель матрицы равен сумме всевозможных попарных произведений миноров порядка матрицы на соответствующие миноры матрицы .

Следствие
При определитель произведения двух квадратных матриц порядка равен произведению определителей этих матриц

Теорема (Кирхгоф, 1847):

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

Доказательство:

Пусть — произвольный связный обыкновенный — граф, и — матрица инцидентности какой-либо ориентации графа . Заметим, что в силу связности графа . По лемме выполняется . Пусть — подматрица матрицы , полученная удалением последней строки. Тогда имеем , где — это — матрица. Очевидно, есть алгебраическое дополнение элемента в матрице Кирхгофа . В силу формулы Бине-Коши равно сумме квадратов всех миноров порядка матрицы . Согласно лемме, доказанной выше, каждый такой минор равен , если остовный подграф графа , ребра которого соответствуют столбцам, вошедшим в матрицу минора , является деревом, и равен в другом случае. Следовательно, равно числу остовов графа . Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

См. также

• Связь матрицы Кирхгофа и матрицы инцидентности
• Матрица Кирхгофа
• Количество помеченных деревьев
• Коды Прюфера

Примечания

Источники информации

• Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ «Регулярная и хаотическая динамика», 2001, 288 стр.

	Нахождение числа остовов графа 10.12.2016, 06:50
30/11/16 13	Попалось мне на зачете такое задание — найти число остовов у данного графа. Вроде бы, все ясно — составить матрицу Кирхгофа, а затем найти алгебраическое дополнение произвольного элемента. Но вот как вычислить это дополнение для матрицы размерности 8х8 — я просто не представляю. Раскладывать по строке — дело долгое и муторное, да и моих серых клеток не хватит для такого. быть может, есть какие-то альтернативные пути решения ?

whitefox	Re: Нахождение числа остовов графа 10.12.2016, 16:41
Заслуженный участник 19/12/10 1546	Есть. Перечисление остовных деревьев. Эффективные алгоритмы можно найти, например, у Д. Кнута в «Искусство программирования» Т. 4, параграф 7.2.1.6 Остовные деревья.

Markiyan Hirnyk	Re: Нахождение числа остовов графа 10.12.2016, 16:48
11/07/16 791

Voenstal	Re: Нахождение числа остовов графа 11.12.2016, 03:31
30/11/16 13	И еще такой вопрос — есть ли разница между остовом и остовным деревом ? Просто много где описываются эти понятия как синонимы.

whitefox	Re: Нахождение числа остовов графа 11.12.2016, 09:55
Заслуженный участник 19/12/10 1546

Voenstal	Re: Нахождение числа остовов графа 11.12.2016, 11:24
30/11/16 13	Имхо, «остов» это слово из студенческого жаргона для обозначение «остовного дерева». Для меня немного странное ИМХО, ибо в задании это — разные понятия, как мне кажется

whitefox	Re: Нахождение числа остовов графа 11.12.2016, 11:39
Заслуженный участник 19/12/10 1546	А мне кажется, что это разные задания: Подсчитать общее число остовных деревьев. Построить одно из них (любое). Но если «остов» не синоним «остовного дерева», то что он может обозначать?

Voenstal	Re: Нахождение числа остовов графа 11.12.2016, 11:48
30/11/16 13	А мне кажется, что это разные задания: Но если «остов» не синоним «остовного дерева», то что он может обозначать? Честно — не знаю. Но судя по всему — оно так и есть. Спасибо за помощь)

Brukvalub	Re: Нахождение числа остовов графа 11.12.2016, 14:18
Заслуженный участник 01/03/06 13626 Москва	Честно — не знаю. Но судя по всему — оно так и есть. Для меня непререкаемым авторитетом в маркизах графах является монография Дистеля. Так вот, в ней никаких «остовов» у графа не определяется, а определяется «остовное дерево» и кое-где считается число «остовных деревьев».

Модераторы: Модераторы Математики, Супермодераторы