Как найти число остовных деревьев - Сайт, где вы сможете решить свои вопросы

В этой части лекции мы рассмотрим так
называемые остовные деревья и их
применение для решения некоторого
класса прикладных задач. Сначала дадим
определение остовного дерева.

Определение 8.3.ДеревоTназываетсяостовным деревомграфаG,
еслиT– подграф графаGи каждая вершинаGявляется вершиной вT.

Теперь сформулируем теорему, которую
примем без доказательства.

Теорема 8.5.У
каждого связного графа существует
подграф, который является остовным
деревом.

Для построения остовных деревьев
существуют разные методы. Самыми
распространенными являются два метода:
метод поиска в ширину и метод поиска в
глубину.

Согласно методу поиска остовного дерева
в ширину произвольную вершину v₀графаG выбираем
в качестве корня дереваT.
Для каждой вершиныvграфаG, смежной с
вершинойv₀, в
деревоTдобавляется
вершинаvи ребро (v₀,v). Это вершины уровня
1. Затем берем каждую вершинуv_iуровня 1 и для каждой вершиныv_jграфаG, смежной с
вершинойv_iиз тех, что еще не выбраны, добавляем в
деревоTвершинуv_jи ребро (v_i,v_j).
Вершины, добавленные на этом этапе, –
это вершины уровня 2. Продолжаем процесс,
пока в графеGне
останется вершин, которые можно было
бы добавить в дерево. По построениюTявляется деревом. Если расстояние отv₀до вершиныvграфаGравноn,
то эта вершина будет добавлена в дерево
на уровнеn. Следовательно,Tнесомненно, является
остовным деревом.

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

При поиске в глубину усилия направлены
на построение для дерева как можно более
длинного пути.

Метод поиска в глубину начинается с
задания вершины графа, которую будем
считать корнем. Выбираем вершину v_i,
смежную с корнем, и формируем ребро
дерева. Затем выбираем вершинуv_j,
смежную с ранее выбранной вершинойv_i,
и формируем новое ребро. По ходу необходимо
помечать использованные вершины, с тем,
чтобы каждая вершина использовалась
один раз. Если, находясь в вершинеv,
мы выбираем другую вершинуwи обнаруживаем, что вершинаwуже была добавлена в дерево, то ребро
(v,w)
между этими вершинами не может быть
добавлено в дерево.

Когда имеем исходный граф, то само собой
возникает вопрос: сколько можно построить
остовных деревьев для помеченного графа
с nвершинами? Ответ
на этот вопрос дает теорема Кэли, которая
рассматривает число остовных деревьев
дляK_n.

Теорема 8.6.(Теорема Кэли)Число остовных деревьев дляK_n,
у которого вершины помечены, равно.

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

Определение 8.4.Матрицей Кирхгофасвязного графаGс
помеченными вершинами называется
матрицаK_v__v=K(G),,
которую можно определить следующим
образом:

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

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

Решение.Сначала составляем для
данного графа матрицу Кирхгофа.

Теперь находим алгебраическое дополнение,
например, для элемента k₁₁матрицы Кирхгофа.

Проверим, например, для элемента k₂₃.

Итак, получаем, что данный граф имеет 8
остовных деревьев.



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

Источник

Матричная теорема о деревьях или теорема Кирхгофа — даёт выражение на число остовных деревьев графа через определитель определённой матрицы.

Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей.^[1]^{[нет в источнике]}

Содержание

1 Формулировка
2 Пример
3 Следствия
4 Обобщения
5 Примечания
6 Ссылки
7 Литература

Формулировка[править | править код]

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

Пример[править | править код]

граф	3 его остовных дерева
${displaystyle {begin{matrix}1&&4\mid &smallsetminus &mid \2&-&3end{matrix}}}$	${displaystyle {begin{matrix}1&&4\mid &&mid \2&-&3end{matrix}}}$	${displaystyle {begin{matrix}1&&4\mid &smallsetminus &mid \2&&3end{matrix}}}$	${displaystyle {begin{matrix}1&&4\&smallsetminus &mid \2&-&3end{matrix}}}$

Для графа G с матрицей смежности
${displaystyle A={begin{bmatrix}0&1&1&0\1&0&1&0\1&1&0&1\0&0&1&0end{bmatrix}}}$
получаем:
${displaystyle M={begin{bmatrix}2&-1&-1&0\-1&2&-1&0\-1&-1&3&-1\0&0&-1&1end{bmatrix}}}$ .

Алгебраическое дополнение, например, элемента M_{1, 2} есть ${displaystyle (-1)^{(1+2)}{begin{vmatrix}-1&-1&0\-1&3&-1\0&-1&1end{vmatrix}}=3}$ , что совпадает с количеством остовых деревьев.

Следствия[править | править код]

Из матричной теоремы выводится

Формула Кэли — число остовных деревьев полного графа равно $n^{{n-2}}$ .
Число остовных деревьев полного двудольнoгo графа $K_{{m,n}}$ равно $m^{{n-1}}cdot n^{{m-1}}$ .

Обобщения[править | править код]

Теорема обобщается на случай мультиграфов и взвешенных графов.
Для взвешенного графа алгебраические дополнения элементов матрицы Кирхгофа равны сумме по всем остовным деревьям произведений весов всех их рёбер.
Частный случай получается, если взять веса равными 1: сумма произведений весов остовов будет равна количеству остовов.

Примечания[править | править код]

↑ Kirchhoff, Gustav. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird (нем.) // Annalen der Physik. — 1847. — Bd. 148, Nr. 12. — S. 497—508.

Ссылки[править | править код]

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

Литература[править | править код]

Это статья-заготовка по математике. Помогите Википедии, дополнив эту статью, как и любую другую.

Источник

Лемма:

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

если не является деревом, то ;
если — дерево, то .

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

↑ Формула Бине-Коши

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

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

Источник

Public user contributions licensed under
cc-wiki license with attribution required

Источник

Общее количество остовных деревьев на графике

31.12.2019Графы

Если граф представляет собой полный граф с n вершинами, то общее количество остовных деревьев равно n ^(n-2), где n — количество узлов в графе. В полном графе задача равна подсчету размеченных деревьев с n узлами, для которых есть формула Кэли .

Что делать, если график не является полным?
Следуйте данной процедуре: —
ШАГ 1: Создать матрицу смежности для данного графика.
ШАГ 2: Заменить все диагональные элементы со степенью узлов. Например, элемент в (1,1) позиции матрицы смежности будет заменен степенью узла 1, элемент в (2,2) позиции матрицы смежности будет заменен степенью узла 2 и так далее.
ШАГ 3: Заменить все недиагональные 1 на -1.
ШАГ 4: Рассчитать коэффициент для любого элемента.
ШАГ 5: Полученный вами кофактор — это общее количество связующего дерева для этого графа.

Рассмотрим следующий график:

Матрица смежности для приведенного выше графика будет выглядеть следующим образом:

После применения ШАГА 2 и ШАГА 3 матрица смежности будет выглядеть

Коэффициент для (1, 1) равен 8. Следовательно, всего нет. связующего дерева, которое может быть сформировано, составляет 8.
ПРИМЕЧАНИЕ. Коэффициент для всех элементов будет одинаковым. Следовательно, мы можем вычислить кофактор для любого элемента матрицы.

Этот метод также известен как теорема Кирхгофа . Это может быть применено и для полных графиков.

Пожалуйста, обратитесь к ссылке ниже для доказательства вышеупомянутой процедуры.
https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem#Proof_outline

Эта статья предоставлена Kapil Khandelwal . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Общее количество связующих деревьев в графе цикла
Программа для поиска общего числа ребер в полном графике
Максимально возможный край непересекающегося остовного дерева из полного графика
Решение проблем для минимальных остовных деревьев (Крускала и Прима)
Количество треугольников в неориентированном графе
Количество узлов стока в графе
Преобразовать неориентированный граф в ориентированный граф так, чтобы не было пути длиной больше 1
Подсчитать количество ребер в неориентированном графе
Количество групп, сформированных в графе друзей
Число простых графов с N вершинами и M ребрами
Максимальное количество ребер в двудольном графе
Минимальное количество ребер между двумя вершинами графа
Минимальное количество ребер между двумя вершинами графа с использованием DFS
Подсчитайте количество деревьев в лесу
Количество деревьев, у которых сумма степеней всех вершин равна L

Общее количество остовных деревьев на графике

0.00 (0%) 0 votes

Источник

Содержание

Формулировка[править | править код]

Пример[править | править код]

Следствия[править | править код]

Обобщения[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

Литература[править | править код]

См. также

Примечания

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

Общее количество остовных деревьев на графике

Вам также может понравиться

Как найти налима в январе

Как найти длину биссектрисы в четырехугольнике

Сухая свинина как исправить после тушения

Добавить комментарий Отменить ответ