Рубрики

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

Если граф представляет собой полный граф с 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, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes