Редактирование: Подсчёт числа остовных деревьев с помощью матрицы Кирхгофа

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пусть <tex>H</tex> {{---}} обыкновенный <tex>(n, n - 1)</tex> {{---}} [[Основные определения теории графов|граф]], <tex>n \geqslant 2 </tex>, <tex>I</tex> {{---}} [[Матрица инцидентности графа|матрица инцидентности]] некоторой его ориентации, <tex>M</tex> {{---}} произвольный минор порядка <tex>n - 1</tex> матрицы <tex>I</tex>. Тогда
+
Пусть <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>M = 0</tex>;
 
# если <tex>H</tex> не является [[Дерево, эквивалентные определения|деревом]], то <tex>M = 0</tex>;
 
# если <tex>H</tex> {{---}} дерево, то <tex>M = \pm 1</tex>.
 
# если <tex>H</tex> {{---}} дерево, то <tex>M = \pm 1</tex>.
Строка 10: Строка 10:
 
## Если <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>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>\geqslant 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>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 \leqslant  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>(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>''', если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Формула Бине-Коши<ref>[https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%91%D0%B8%D0%BD%D0%B5_%E2%80%94_%D0%9A%D0%BE%D1%88%D0%B8 Формула Бине-Коши] </ref>
+
[https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%91%D0%B8%D0%BD%D0%B5_%E2%80%94_%D0%9A%D0%BE%D1%88%D0%B8 Формула Бине-Коши]
 
|statement=
 
|statement=
 
Определитель матрицы <tex>C</tex> равен сумме всевозможных попарных произведений миноров порядка <tex>s</tex> матрицы <tex>P</tex> на соответствующие миноры матрицы <tex>Q</tex>.
 
Определитель матрицы <tex>C</tex> равен сумме всевозможных попарных произведений миноров порядка <tex>s</tex> матрицы <tex>P</tex> на соответствующие миноры матрицы <tex>Q</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 \geqslant 2</tex> и <tex>I</tex> {{---}} матрица инцидентности какой-либо ориентации графа <tex>G</tex>. Заметим, что <tex>m \geqslant 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>(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>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.
 
}}
 
}}
  
Строка 39: Строка 39:
 
*[[Коды Прюфера]]
 
*[[Коды Прюфера]]
  
== Примечания ==
+
==Источники информации==
<references />
 
  
==Источники информации==
 
 
*Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
 
*Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)