Матричная теорема о деревьях

Матричная теорема о деревьях (Matrix tree theorem), также известная как Теорема Кирхгофа — теорема теории конечных графов.

Содержание

1 Теорема Кирхгофа-Трента
2 Доказательство
3 Пример
4 Ссылки

Теорема Кирхгофа-Трента

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

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

Пример

граф G	каркасы (3 шт)
$\begin{matrix} 1 & & 4\\ \mid & \smallsetminus & \mid \\ 2 & - & 3 \end{matrix}$	$\begin{matrix} 1 & & 4\\ \mid & & \mid \\ 2 & - & 3 \end{matrix}$	$\begin{matrix} 1 & & 4\\ \mid & \smallsetminus & \mid \\ 2 & & 3 \end{matrix}$	$\begin{matrix} 1 & & 4\\ & \smallsetminus & \mid \\ 2 & - & 3 \end{matrix}$

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

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

Ссылки

Графы и их применение
Теорема Кирхгофа

Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её.

Gulchatai-krd.ru

Узбекская кухня