§ 14. Матричная теорема Кирхгофа

Как уже отмечалось, в каждом графе имеется остов. В общем случае остов определен неоднозначно. Естествен­но возникает вопрос: как много остовов в графе? Очевид­но, что при ответе на этот вопрос достаточно ограничить­ся случаем связного графа. В связном графе остовом служит любое остовное дерево, т. е. остовный подграф, являющийся деревом. Число остовов в связном графе определяется в неявной форме следующей теоремой.

Теорема Кирхгофа (1847 г.). Число остовных деревьев в связном графе G порядка

n 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа В (G].

Доказательство опирается на следующую лемму.

Лемма 14.1. Пусть H — (m+l, m)-граф, I — мат­рица инцидентности какой-либо его ориентации, М — про­извольный минор порядка m матрицы I. Тогда:

1. если Н — дерево, то М = ± 1;

2. если Н не является деревом, то М = 0.

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

Пусть а — вершина, соответствующая строке матрицы I, не вошедшей в минор М. Если граф Н не является деревом, то он несвязен. Пусть К = {1, 2, ..., k} — его область связности, не содержащая вершины а. С помощью подходящей перенумерации ребер графа Н матрицу I приведем к клеточно-диагональному виду I = diag [I1, I2], где I1 — матрица инцидентности компоненты Н(К). Ми­нор М содержит все первые k строк матрицы I, сумма которых равна нулевой строке. Следовательно, М = 0.

Пусть теперь Н — дерево. Заново перенумеруем вер­шины и ребра графа Н следующим образом. Одной из кон­цевых вершин v, отличных от вершины а, а также ребру, инцидентному вершине v, присвоим номер 1. Далее рас­смотрим дерево Т1 = Н — v. Если его порядок больше 1, то одной из его концевых вершин и, отличных от а также инцидентному ей ребру присвоим номер 2. Рассмотрим дерево Т2 = Т1 — и. Итерируя этот процесс, по лучим новые нумерации вершин и ребер дерева Н, при чем вершина а будет иметь номер т + 1. Матрица I npи этом примет вид

(Здесь и в дальнейшем символом * будут обозначаться элементы или блоки матрицы, значения которых не влияют на ход рассуждений.) Минор М, остающийся после удаления последней строки этой матрицы, равен ±1. Еще один факт, используемые при доказательстве теоремы Кирхгофа,— формула Бинэ — Коши, которую мы приведем без доказательства. Пусть А и В — n x m и m x n-матрицы соответственно, С = АВ и n т. Минор порядка n матрицы В назовем соответствующим минору порядка n матрицы А, если множества номеров строк первые 70 из них и номеров столбцов второго совпадают.

Формула Бинэ — Коши. Определитель матрицы С равен сумме произведений каждого минора порядка матрицы А на соответствующий минор матрицы В.

Доказательство теоремы Кирхгофа. Пусть I — матрица инцидентности какой-либо ориентации (n,т) -графа G. Согласно утверждению 6.4 верно равенство

B(G) = II^T. (1)

Поскольку G - связный граф, то т  n — 1. Если В — подматрица, остающаяся после удаления из B(G) последних строки и столбца, а С — подматрица, остающаяся после удаления из I последней строки, то в силу (1) В =CС^Т. Алгебраическое дополнение А_nn элемента, занимающего в матрице B(G) позицию (n,n), равно detB. Из формулы Бинэ — Коши теперь следует, что А_nn равно сумме квадратов всех миноров порядка n — 1 матрицы С. Согласно лемме 14.1 каждый такой минор М равен ±1, и остовный подграф графа G, ребра которого соответствуют столбцам, вошедшим в М, является деревом, и нет в противном случае. Следовательно, А_nn равно числу остовных деревьев в графе G. Поскольку алгебраические долнения всех элементов матрицы B(G) равны (ут-верждение 6.2), то теорема доказана.

Следствие 14.2. Для числа компонент n-вершинного графа G верно равенство

k(G)=n-rankB(G).

Если граф G связен, то в нем есть остовное дерево. Согласно предыдущей теореме rank B (G) n — 1. С дру­гой стороны, всегда det B(G)=0. Следовательно, rankB(G)=n-1.

Пусть теперь граф G имеет ровно k компонент. Тогда при подходящей нумерации вершин матрицей B(G) слу­жит клеточно-диагональная матрица diag[B1, B2, ..., Bk], диагональные клетки которой Вi являются матрицами Кирхгофа соответствующих компонент. Учитывая уже до­казанное, имеем rank В (G) = n — k.

.

Следствие14.3. При n > 1 число остовое в пол­ном графе К_n равно n^n-2.> Рассмотрим алгебраическое дополнение А11 эле­мента матрицы

з анимающего позицию(1, 1). Оно равно определителю порядка n-1.Далее имеем

Очевидно, что число остовов в К_n равно числу поме­ченных деревьев порядка n. Поэтому предыдущее след­ствие можно сформулировать в виде следующей теоремы, впервые полученной А. Кэли в 1897 году.

Теорема Кэли. Число помеченных деревьев по­рядка n равно n^n-2.