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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пусть <tex>H</tex> - обыкновенный <tex>(n, n - 1)</tex>-[[Основные определения теории графов|граф]], <tex>n \ge 2 </tex>, <tex>I</tex> - [[Матрица инцидентности графа|матрица инцидентности]] некоторой его ориентации, <tex>M</tex> - произвольный минор порядка <tex>n - 1</tex> матрицы <tex>I</tex>. Тогда
+
Пусть <tex>H</tex> <tex>-</tex> обыкновенный <tex>(n, n - 1)</tex>-[[Основные определения теории графов|граф]], <tex>n \ge 2 </tex>, <tex>I</tex> <tex>-</tex> [[Матрица инцидентности графа|матрица инцидентности]] некоторой его ориентации, <tex>M</tex> - произвольный минор порядка <tex>n - 1</tex> матрицы <tex>I</tex>. Тогда
 
# если <tex>H</tex> не является [[Дерево, эквивалентные определения|деревом]], то <tex>M = 0</tex>;
 
# если <tex>H</tex> не является [[Дерево, эквивалентные определения|деревом]], то <tex>M = 0</tex>;
# если <tex>H</tex> - дерево, то <tex>M = \pm 1</tex>.
+
# если <tex>H</tex> <tex>-</tex> дерево, то <tex>M = \pm 1</tex>.
 
|proof=
 
|proof=
 
Заметим, что смена нумерации вершин и нумерации ребер графа <tex>H</tex> приводит к перестановке строк и перестановке столбцов матрицы <tex>I</tex>. Рассматриваемый минор при этом может сменить лишь знак.<br/>
 
Заметим, что смена нумерации вершин и нумерации ребер графа <tex>H</tex> приводит к перестановке строк и перестановке столбцов матрицы <tex>I</tex>. Рассматриваемый минор при этом может сменить лишь знак.<br/>
Пусть <tex>v</tex> - вершина, соответствующая строке матрицы <tex>I</tex>, не вошедшей в матрицу минора <tex>M</tex>.
+
Пусть <tex>v</tex> <tex>-</tex> вершина, соответствующая строке матрицы <tex>I</tex>, не вошедшей в матрицу минора <tex>M</tex>.
 
# Пусть <tex>H</tex> не является деревом. Тогда граф <tex>H</tex> несвязен. Пусть <tex>v_1, ..., v_t</tex> - множество вершин некоторой [[Отношение связности, компоненты связности|компоненты связности]] <tex>H_1</tex> графа <tex>H</tex>, не содержащей <tex>v</tex>.
 
# Пусть <tex>H</tex> не является деревом. Тогда граф <tex>H</tex> несвязен. Пусть <tex>v_1, ..., v_t</tex> - множество вершин некоторой [[Отношение связности, компоненты связности|компоненты связности]] <tex>H_1</tex> графа <tex>H</tex>, не содержащей <tex>v</tex>.
 
## Если <tex>t = 1</tex>, то <tex>v_1</tex> - изолированная вершина и в матрице минора <tex>M</tex> имеется нулевая строка, поэтому <tex>M = 0</tex>.
 
## Если <tex>t = 1</tex>, то <tex>v_1</tex> - изолированная вершина и в матрице минора <tex>M</tex> имеется нулевая строка, поэтому <tex>M = 0</tex>.
## Пусть <tex>t > 1</tex>. С помощью подходящей перенумерации вершин и ребер из <tex>H</tex> матрицу <tex>I</tex> приведем к клеточному виду <br/> <center><tex>\begin{pmatrix} I_1 & 0\\0 & I_2 \end{pmatrix}</tex>, </center><br/>где <tex>I_1</tex> - матрица инцидентности ориентации компоненты <tex>H_1</tex>, а вершине <tex>v</tex> отвечает строка, проходящая через <tex>I_2</tex>. Каждый столбец, проходящий через <tex>I_1</tex>, содержит точно одну единицу и точно одну <tex>-1</tex> (остальные элементы равны нулю). Следовательно, сумма первых <tex>t</tex> строк равна <tex>0</tex>. Так как первые <tex>t</tex> строк входят в матрицу минора <tex>M</tex>, имеем <tex>M = 0</tex>.
+
## Пусть <tex>t > 1</tex>. С помощью подходящей перенумерации вершин и ребер из <tex>H</tex> матрицу <tex>I</tex> приведем к клеточному виду <br/> <center><tex>\begin{pmatrix} I_1 & 0\\0 & I_2 \end{pmatrix}</tex>, </center><br/>где <tex>I_1</tex> <tex>-</tex> матрица инцидентности ориентации компоненты <tex>H_1</tex>, а вершине <tex>v</tex> отвечает строка, проходящая через <tex>I_2</tex>. Каждый столбец, проходящий через <tex>I_1</tex>, содержит точно одну единицу и точно одну <tex>-1</tex> (остальные элементы равны нулю). Следовательно, сумма первых <tex>t</tex> строк равна <tex>0</tex>. Так как первые <tex>t</tex> строк входят в матрицу минора <tex>M</tex>, имеем <tex>M = 0</tex>.
# Пусть <tex>H</tex> является деревом. Заново перенумеруем вершины и ребра графа <tex>H</tex> с помощью следующей процедуры. В качестве <tex>v_1</tex> возьмем одну из висячих вершин дерева <tex>H</tex>, отличную от <tex>v</tex>. Через <tex>e_1</tex> обозначим инцидентное ей висячее ребро. Рассмотрим дерево <tex>H_1 = H - v_1</tex>. Если его порядок <tex>\ge 2</tex>, то через <tex>v_2</tex> обозначим одну из висячих вершин, отличных от <tex>v</tex>, а через <tex>e_2</tex> - инцидентное ей висячее ребро. Положим <tex>H_2 = H_1 - e_2</tex>. Продолжаем этот процесс до тех пор, пока не получим одноэлементное дерево <tex>H_{n-1}</tex>, единственной вершиной которого обязательно будет вершина <tex>v</tex>. Получим нумерацию вершин <tex>v_1, ..., v_n = v</tex> и нумерацию ребер <tex>e_1, ..., e_{n-1}</tex>. В новой нумерации матрица <tex>I</tex> приведется к виду<br/><center><tex>\begin{pmatrix} \pm 1 & 0 &\cdots &0\\* & \pm 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ * & * & \cdots & \pm 1\\ * & * & \cdots & * \end{pmatrix}</tex>,</center><br/> причем вершине <tex>v</tex> отвечает последняя строка (здесь каждый диагональный элемент равен <tex>1</tex> или <tex>-1</tex>, а через <tex>*</tex> обозначены элементы матрицы, значения которых не вписаны в явном виде). Таким образом, матрица минора имеет треугольный вид и <tex>M = \pm1</tex>.
+
# Пусть <tex>H</tex> является деревом. Заново перенумеруем вершины и ребра графа <tex>H</tex> с помощью следующей процедуры. В качестве <tex>v_1</tex> возьмем одну из висячих вершин дерева <tex>H</tex>, отличную от <tex>v</tex>. Через <tex>e_1</tex> обозначим инцидентное ей висячее ребро. Рассмотрим дерево <tex>H_1 = H - v_1</tex>. Если его порядок <tex>\ge 2</tex>, то через <tex>v_2</tex> обозначим одну из висячих вершин, отличных от <tex>v</tex>, а через <tex>e_2</tex> <tex>-</tex> инцидентное ей висячее ребро. Положим <tex>H_2 = H_1 - e_2</tex>. Продолжаем этот процесс до тех пор, пока не получим одноэлементное дерево <tex>H_{n-1}</tex>, единственной вершиной которого обязательно будет вершина <tex>v</tex>. Получим нумерацию вершин <tex>v_1, ..., v_n = v</tex> и нумерацию ребер <tex>e_1, ..., e_{n-1}</tex>. В новой нумерации матрица <tex>I</tex> приведется к виду<br/><center><tex>\begin{pmatrix} \pm 1 & 0 &\cdots &0\\* & \pm 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ * & * & \cdots & \pm 1\\ * & * & \cdots & * \end{pmatrix}</tex>,</center><br/> причем вершине <tex>v</tex> отвечает последняя строка (здесь каждый диагональный элемент равен <tex>1</tex> или <tex>-1</tex>, а через <tex>*</tex> обозначены элементы матрицы, значения которых не вписаны в явном виде). Таким образом, матрица минора имеет треугольный вид и <tex>M = \pm1</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex>P</tex> и <tex>Q</tex> - соответственно <tex>(s \times t)</tex>-матрица и <tex>(t \times s)</tex>-матрица, где <tex>s \le t</tex>. Положим <tex>C = PQ</tex>. Минор порядка <tex>s</tex> матрицы <tex>Q</tex> называется '''соответствующим минором минору порядка <tex>s</tex> матрицы <tex>P</tex>''', если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.
+
Пусть <tex>P</tex> и <tex>Q</tex> <tex>-</tex> соответственно <tex>(s \times t)</tex><tex>-</tex>матрица и <tex>(t \times s)</tex><tex>-</tex>матрица, где <tex>s \le t</tex>. Положим <tex>C = PQ</tex>. Минор порядка <tex>s</tex> матрицы <tex>Q</tex> называется '''соответствующим минором минору порядка <tex>s</tex> матрицы <tex>P</tex>''', если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
Строка 30: Строка 30:
 
Число остовов в связном неодноэлементном обыкновенном графе <tex>G</tex> равно алгебраическому дополнению любого элемента [[Матрица Кирхгофа|матрицы Кирхгофа]] <tex>B(G)</tex>.
 
Число остовов в связном неодноэлементном обыкновенном графе <tex>G</tex> равно алгебраическому дополнению любого элемента [[Матрица Кирхгофа|матрицы Кирхгофа]] <tex>B(G)</tex>.
 
|proof=
 
|proof=
Пусть <tex>G</tex> - произвольный связный обыкновенный <tex>(n, m)</tex>-граф, <tex>n \ge 2</tex> и <tex>I</tex> - матрица инцидентности какой-либо ориентации графа <tex>G</tex>. Заметим, что <tex>m \ge n - 1</tex> в силу связности графа <tex>G</tex>. По [[Связь матрицы Кирхгофа и матрицы инцидентности|лемме]] выполняется <tex>B = B(G) = I \cdot I^T</tex>. Пусть <tex>B'</tex> - подматрица матрицы <tex>B</tex>, полученная удалением последней строки. Тогда имеем <tex>B' = JJ^T</tex>, где <tex>J</tex> - это <tex>((n - 1) \times m)</tex> - матрица. Очевидно, <tex>B_{nn} = det B'</tex> есть алгебраическое дополнение элемента <tex>\beta_{nn}</tex> в матрице Кирхгофа <tex>B</tex>. В силу формулы Бине-Коши <tex>B_{nn}</tex> равно сумме квадратов всех миноров порядка <tex>(n - 1)</tex> матрицы <tex>J</tex>. Согласно лемме, доказанной выше, каждый такой минор <tex>M</tex> равен <tex>\pm 1</tex>, если остовный подграф графа <tex>G</tex>, ребра которого соответствуют столбцам, вошедшим в матрицу минора <tex>M</tex>, является деревом, и равен <tex>0</tex> в другом случае. Следовательно, <tex>B_{nn}</tex> равно числу остовов графа <tex>G</tex>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.
+
Пусть <tex>G</tex> <tex>-</tex> произвольный связный обыкновенный <tex>(n, m)</tex><tex>-</tex>граф, <tex>n \ge 2</tex> и <tex>I</tex> <tex>-</tex> матрица инцидентности какой-либо ориентации графа <tex>G</tex>. Заметим, что <tex>m \ge n - 1</tex> в силу связности графа <tex>G</tex>. По [[Связь матрицы Кирхгофа и матрицы инцидентности|лемме]] выполняется <tex>B = B(G) = I \cdot I^T</tex>. Пусть <tex>B'</tex> <tex>-</tex> подматрица матрицы <tex>B</tex>, полученная удалением последней строки. Тогда имеем <tex>B' = JJ^T</tex>, где <tex>J</tex> <tex>-</tex> это <tex>((n - 1) \times m)</tex> <tex>-</tex> матрица. Очевидно, <tex>B_{nn} = det B'</tex> есть алгебраическое дополнение элемента <tex>\beta_{nn}</tex> в матрице Кирхгофа <tex>B</tex>. В силу формулы Бине-Коши <tex>B_{nn}</tex> равно сумме квадратов всех миноров порядка <tex>(n - 1)</tex> матрицы <tex>J</tex>. Согласно лемме, доказанной выше, каждый такой минор <tex>M</tex> равен <tex>\pm 1</tex>, если остовный подграф графа <tex>G</tex>, ребра которого соответствуют столбцам, вошедшим в матрицу минора <tex>M</tex>, является деревом, и равен <tex>0</tex> в другом случае. Следовательно, <tex>B_{nn}</tex> равно числу остовов графа <tex>G</tex>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.
 
}}
 
}}
 
==Источники==
 
==Источники==
  
 
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
 
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Остовные деревья ]]

Версия 09:00, 10 декабря 2011

Лемма:
Пусть [math]H[/math] [math]-[/math] обыкновенный [math](n, n - 1)[/math]-граф, [math]n \ge 2 [/math], [math]I[/math] [math]-[/math] матрица инцидентности некоторой его ориентации, [math]M[/math] - произвольный минор порядка [math]n - 1[/math] матрицы [math]I[/math]. Тогда
  1. если [math]H[/math] не является деревом, то [math]M = 0[/math];
  2. если [math]H[/math] [math]-[/math] дерево, то [math]M = \pm 1[/math].
Доказательство:
[math]\triangleright[/math]

Заметим, что смена нумерации вершин и нумерации ребер графа [math]H[/math] приводит к перестановке строк и перестановке столбцов матрицы [math]I[/math]. Рассматриваемый минор при этом может сменить лишь знак.
Пусть [math]v[/math] [math]-[/math] вершина, соответствующая строке матрицы [math]I[/math], не вошедшей в матрицу минора [math]M[/math].

  1. Пусть [math]H[/math] не является деревом. Тогда граф [math]H[/math] несвязен. Пусть [math]v_1, ..., v_t[/math] - множество вершин некоторой компоненты связности [math]H_1[/math] графа [math]H[/math], не содержащей [math]v[/math].
    1. Если [math]t = 1[/math], то [math]v_1[/math] - изолированная вершина и в матрице минора [math]M[/math] имеется нулевая строка, поэтому [math]M = 0[/math].
    2. Пусть [math]t \gt 1[/math]. С помощью подходящей перенумерации вершин и ребер из [math]H[/math] матрицу [math]I[/math] приведем к клеточному виду
      [math]\begin{pmatrix} I_1 & 0\\0 & I_2 \end{pmatrix}[/math],

      где [math]I_1[/math] [math]-[/math] матрица инцидентности ориентации компоненты [math]H_1[/math], а вершине [math]v[/math] отвечает строка, проходящая через [math]I_2[/math]. Каждый столбец, проходящий через [math]I_1[/math], содержит точно одну единицу и точно одну [math]-1[/math] (остальные элементы равны нулю). Следовательно, сумма первых [math]t[/math] строк равна [math]0[/math]. Так как первые [math]t[/math] строк входят в матрицу минора [math]M[/math], имеем [math]M = 0[/math].
  2. Пусть [math]H[/math] является деревом. Заново перенумеруем вершины и ребра графа [math]H[/math] с помощью следующей процедуры. В качестве [math]v_1[/math] возьмем одну из висячих вершин дерева [math]H[/math], отличную от [math]v[/math]. Через [math]e_1[/math] обозначим инцидентное ей висячее ребро. Рассмотрим дерево [math]H_1 = H - v_1[/math]. Если его порядок [math]\ge 2[/math], то через [math]v_2[/math] обозначим одну из висячих вершин, отличных от [math]v[/math], а через [math]e_2[/math] [math]-[/math] инцидентное ей висячее ребро. Положим [math]H_2 = H_1 - e_2[/math]. Продолжаем этот процесс до тех пор, пока не получим одноэлементное дерево [math]H_{n-1}[/math], единственной вершиной которого обязательно будет вершина [math]v[/math]. Получим нумерацию вершин [math]v_1, ..., v_n = v[/math] и нумерацию ребер [math]e_1, ..., e_{n-1}[/math]. В новой нумерации матрица [math]I[/math] приведется к виду
    [math]\begin{pmatrix} \pm 1 & 0 &\cdots &0\\* & \pm 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ * & * & \cdots & \pm 1\\ * & * & \cdots & * \end{pmatrix}[/math],

    причем вершине [math]v[/math] отвечает последняя строка (здесь каждый диагональный элемент равен [math]1[/math] или [math]-1[/math], а через [math]*[/math] обозначены элементы матрицы, значения которых не вписаны в явном виде). Таким образом, матрица минора имеет треугольный вид и [math]M = \pm1[/math].
[math]\triangleleft[/math]
Определение:
Пусть [math]P[/math] и [math]Q[/math] [math]-[/math] соответственно [math](s \times t)[/math][math]-[/math]матрица и [math](t \times s)[/math][math]-[/math]матрица, где [math]s \le t[/math]. Положим [math]C = PQ[/math]. Минор порядка [math]s[/math] матрицы [math]Q[/math] называется соответствующим минором минору порядка [math]s[/math] матрицы [math]P[/math], если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.
Теорема (Формула Бине-Коши):
Определитель матрицы [math]C[/math] равен сумме всевозможных попарных произведений миноров порядка [math]s[/math] матрицы [math]P[/math] на соответствующие миноры матрицы [math]Q[/math].

Следствие
При [math]s = t[/math] определитель произведения двух квадратных матриц порядка [math]s[/math] равен произведению определителей этих матриц

Теорема (Кирхгоф, 1847):
Число остовов в связном неодноэлементном обыкновенном графе [math]G[/math] равно алгебраическому дополнению любого элемента матрицы Кирхгофа [math]B(G)[/math].
Доказательство:
[math]\triangleright[/math]
Пусть [math]G[/math] [math]-[/math] произвольный связный обыкновенный [math](n, m)[/math][math]-[/math]граф, [math]n \ge 2[/math] и [math]I[/math] [math]-[/math] матрица инцидентности какой-либо ориентации графа [math]G[/math]. Заметим, что [math]m \ge n - 1[/math] в силу связности графа [math]G[/math]. По лемме выполняется [math]B = B(G) = I \cdot I^T[/math]. Пусть [math]B'[/math] [math]-[/math] подматрица матрицы [math]B[/math], полученная удалением последней строки. Тогда имеем [math]B' = JJ^T[/math], где [math]J[/math] [math]-[/math] это [math]((n - 1) \times m)[/math] [math]-[/math] матрица. Очевидно, [math]B_{nn} = det B'[/math] есть алгебраическое дополнение элемента [math]\beta_{nn}[/math] в матрице Кирхгофа [math]B[/math]. В силу формулы Бине-Коши [math]B_{nn}[/math] равно сумме квадратов всех миноров порядка [math](n - 1)[/math] матрицы [math]J[/math]. Согласно лемме, доказанной выше, каждый такой минор [math]M[/math] равен [math]\pm 1[/math], если остовный подграф графа [math]G[/math], ребра которого соответствуют столбцам, вошедшим в матрицу минора [math]M[/math], является деревом, и равен [math]0[/math] в другом случае. Следовательно, [math]B_{nn}[/math] равно числу остовов графа [math]G[/math]. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.
[math]\triangleleft[/math]

Источники

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