Первая страница / Теория / Графы. Основные алгоритмы /

Формула Кэли

Голосование: 20, 6

Введение

В статье будет рассмотрена формула Кэли и представлены несколько её доказательств. Формула Кэли устанавливает количество помеченных деревьев заданного порядка.

Теорема (A. Cayley, 1897)

Число помеченных деревьев порядка n равно nn-2.

Коды Прюфера

Кодирование Прюфера (H. Prufer, 1918) переводит помеченные деревья порядка n в последовательности чисел по следующему алгоритму:

  1. Выбирается лист с минимальным номером.
  2. Лист и инцидентное ребро удаляются из дерева, в последовательность Прюфера добавляется номер смежной вершины.
  3. Если в дереве больше двух вершин, то п. 1, иначе — выход.

Распаковка дерева осуществляется по следующему алгоритму:
Обозначим A = [a1, a2, ..., an-2] — последовательность Прюфера, N = [1, 2, ..., n].

  1. Выберем минимальное число v из N, не содержащееся в A.
  2. Соединяем ребром вершину с номером v и вершину, соответствующую первому числу из A.
  3. Удаляем v из N, удаляем первое число из A.
  4. Если в A осталось два числа — соединяем ребром соответствующие вершины, иначе — п. 1.

Очевидно, кодирование Прюфера задаёт взаимно-однозначное соответствие между множеством помеченных деревьев порядка n и множеством числовых последовательностей, состоящих из n - 2 натуральных чисел из отрезка [1 .. n].

Рассмотрим доказательство формулы, основанное на последовательностях Прюфера.

Доказательство формулы Кэли

Мощность множества последовательностей Прюфера для помеченных деревьев порядка n равна nn-2. Вследствие биективности кодирования Прюфера получаем нужное.

Теорема Кирхгофа

Определим матрицу Кирхгофа B = B(G), полагая

матрица Кирхгофа

где A(G) — матрица смежности графа G.

Лемма

Алгебраические дополнения всех элементов матрицы Кир­хгофа равны между собой.

Доказательство. Обозначим столбец (1, 1, ..., 1)T длины n, состо­ящий из единиц, через 1.

Для матрицы Кирхгофа B(G) = (βij)nxn выполняется

Σj=1..n βij = 0 (i = 1, 2, ..., n), т.е. B * 1 = 0,
Σi=1..n βij = 0 (j = 1, 2, ..., n), т.е. 1T * B = 0.

Отсюда следует, что det B = 0 и rank Bn - 1.

Если rank В < n - 1, то все алгебраические дополнения элементов матрицы В равны 0. Пусть rank В = n - 1 и C — присоединённая к В матрица, составленная из алгебраических дополнений Вij элементов βij, т.е.

присоединённая матрица

В силу свойств C получаем

BC = CB = (det B)E = 0.

Так как ВC = 0, любой столбец X матрицы C удовлетворяет системе ВХ = 0. Эта система линейных уравнений имеет ранг n - 1. Так как B * 1 = 0, этой системе удовлетворяет столбец 1. Следовательно, столбцы матрицы C пропорциональны столбцу 1, откуда следует

Bi1 = Bi2 = ... = Bin (i = 1, 2, ..., n).

Аналогично получаем

B1j = B2j = ... = Bnj (j = 1, 2, ..., n).

Следовательно, все элементы матрицы C одинаковы. Лемма доказана.

Лемма

Пусть В = B(G) — матрица Кирхгофа обыкновенного гра­фа G и I = I(Н) — соответствующая матрица инцидентности неко­торой его ориентации H. Тогда B = I * IT.

Доказательство. Если умножить i-ю строку матрицы I на i-й стол­бец матрицы IT, то получим сумму квадратов элементов i-й строки мат­рицы I, которая равна, очевидно, deg vi. Пусть теперь i-я строка матри­цы I умножается на j-й столбец матрицы IT. Если имеется дуга, соединяющая vi и vj, то получим -1. Если такой дуги нет, то получим 0. Лемма доказана.

Лемма

Пусть Н — обыкновенный (n, n - 1)-граф, n > 2, I — матрица инцидентности некоторой его ориентации, М — произвольный минор порядка n - 1 матрицы I. Тогда

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

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

Пусть v — вершина, соответствующая строке матрицы I, не вошедшей в матрицу минора М.

Пусть Н не является деревом. Тогда граф Н несвязен. Пусть v1, ..., vt — множество вершин некоторой компоненты связности H1 графа H, не содержащей v.

Если t = 1, то v1 — изолированная вершина и в матрице минора М имеется нулевая строка, поэтому М = 0.

Пусть t > 1. С помощью подходящей перенумерации вершин и ребер матрицу I приведем к клеточному виду

клеточный вид

где I1 — матрица инцидентности ориентации компоненты H1, а вершине v отвечает строка, проходящая через I2. Каждый столбец, проходящий через I1, содержит точно одну единицу и точно одну -1 (остальные элементы равны нулю). Следовательно, сумма первых t строк равна 0. Так как первые t строк входят в матрицу минора М, имеем М = 0.

Пусть Н является деревом. Заново перенумеруем вершины и ребра графа Н с помощью следующей процедуры. В качестве v1 возьмем одну из висячих вершин дерева Н, отличную от v. Через е1 обозначим инцидентное ей висячее ребро. Рассмотрим дерево Н1 = Н - v1. Если его порядок ≥ 2, то через v2 обозначим одну из висячих вершин, отличных от v, а через е2 — инцидентное ей висячее ребро. Положим Н2 = Н1 - v2. Продолжаем этот процесс до тех пор, пока не получим одноэлементное дерево Hn-1, единственной вершиной которого обязательно будет вершина v. Получим нумерацию вершин v1, ..., vn = v и нумерацию ребер e1, ..., еn-1. В новой нумерации матрица I приведется к виду

треугольный вид

причем вершине v отвечает последняя строка. Теперь ясно, что матрица минора имеет треугольный вид и М = ±1. Лемма доказана.

Лемма (формула Бине-Коши (Binet-Cauchy))

Пусть P — (s x t)-матрица, Q — (t x s)-матрица и s < t. Положим C = PQ. Минор порядка s матрицы Q называется соответствующим минором минору порядка s матрицы Р, если множество номеров строк, состав­ляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.

Формула Бине-Коши: определитель матрицы C равен сумме всевозможных попарных произведений миноров порядка s матрицы P на соответствующие миноры матрицы Q.

Теорема (G. Kirchhoff, 1847)

Число остовов в связном неодноэле­ментном обыкновенном графе G равно алгебраическому дополнению любо­го элемента матрицы Кирхгофа B(G).

Доказательство. Пусть G — произвольный связный обыкновенный (n, m)-граф, n ≥ 2 и I — матрица инцидентности какой-либо ориентации графа G. Заметим, что mn - 1 в силу связности графа G. По лемме выполняется

B = B(G) = I * IT.

Пусть В' — подматрица матрицы В, полученная удалением последней строки и последнего столбца, a J — подматрица матрицы I, полученная удалением последней строки. Тогда имеем

B' = J * JT,

где J — это ((n-1) x m)-матрица. Очевидно, Вnn = det В' есть алгебра­ическое дополнение элемента βnn в матрице Кирхгофа В. В силу форму­лы Бине-Коши Вnn равно сумме квадратов всех миноров порядка n - 1 матрицы J. Согласно лемме каждый такой минор М равен ±1, если остовный подграф графа G, ребра которого соответствуют столбцам, во­шедшим в матрицу минора М, является деревом, и равен 0 в другом случае. Следовательно, Вnn равно числу остовов графа G. Осталось от­метить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

Следствие

Число остовов в полном графе Kn равно nn-2.

Доказательство. Утверждение очевидно для n = 1 и n = 2. Пусть n > 2. Рассмотрим матрицу Кирхгофа полного графа Kn:

матрица Кирхгофа полного графа
Bnn = nn-2.

По теореме Кирхгофа получаем нужное.

Рассмотрим доказательство формулы, основанное на теореме Кирхгофа.

Доказательство формулы Кэли

Число помеченных деревьев порядка n, очевидно, равно числу остовов в полном графе Kn, которое есть nn-2 по следствию теоремы Кирхгофа.

Лемма о количестве деревьев

Лемма

Пусть d1, d2, ..., dn — натуральные числа, удовлетворяющие равенству

Σi=1..ndi = 2n - 2.

Пусть A — множество деревьев с n вершинами, такими что i-ая вершина имеет степень di. Тогда

|A| = (n - 2)! / [ (d1 - 1)! ... (dn - 1)! ].

Доказательство. Утверждение верно для n = 1 и n = 2. Пусть n > 2 и утверждение верно для n - 1. Так как все di положительны, то их сумма меньше 2n. Значит существует такое k, что dk = 1. Без потери общности будем считать, что dn = 1.

Для каждого i = 1, 2, ..., n - 1 определим Bi — множество деревьев с вершинами v1, ...,vn-1, такими что deg vj = dj, если ji, и deg vj = dj - 1, если j = i.

Деревья из Bi соответствуют деревьям из A, у которых есть ребро {vi, vn}. Если di = 1, то Bi — пустое множество. Так как вершина vn должна быть соединена с какой-либо вершиной в каждом дереве из A, получаем

|A| = Σi=1..n-1|Bi|.

Из индукционного предположения:

|Bi| = (n - 3)! / [ (d1 - 1)!... (di - 2)! ... (dn-1 - 1)! ], если di ≠ 1 (и равно 0 иначе).

Тогда

|Bi| = (n - 3)!(di - 1) / [ (d1 - 1)! ... (dn-1 - 1)! ]

Значит для мощности A можем написать

|A| = Σi=1..n-1|Bi| = [(n - 3)! / [(d1 - 1)! ... (dn-1 - 1)!] ] * Σi=1..n-1(di - 1).

Так как dn = 1 и Σi=1..ndi = 2n - 2, получаем:

|A| = (n - 3)!(n - 2) / [ (d1 - 1)! ... (dn - 1)! ] = (n - 2)! / [ (d1 - 1)! ... (dn - 1)! ].

Лемма доказана.

Теорема

мультиномиальная теорема

Коэффициенты в этом разложении называются мультиномиальными коэффициентами и вычисляются по формуле:

мультиномиальные коэффициенты

(n, k1, ...,km — целые и неотрицательные и k1 + k2 + ... + km = n)

Следствие

свойство мультиномиальных коэффициентов

Рассмотрим доказательство, основанное на лемме и свойстве мультиномиальных коэффициентов.

Доказательство формулы Кэли

Обозначим Tn — множество помеченных деревьев порядка n. В любом дереве порядка n сумма степеней вершин есть 2n - 2, поэтому

|Tn| = Σd1+d2+...+dn=2n-2 (n - 2)! / [ (d1 - 1)! ... (dn - 1)! ].

Сделаем переобозначение: ki = di - 1, тогда

|Tn| = Σk1+k2+...+kn=n-2 (n - 2)! / [ k1! ... kn! ].

По свойству мультиномиальных коэффициентов получаем нужное:

|Tn| = nn-2.

Литература

  1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.
  2. Wikipedia Cayley's formula, Prufer sequence.

Илья Чернявский


Мария / 2009-06-21 17:34:08

Материал хороший и хорошая структуризация информации..ждём продолжения..(остальной курс).

спасибо

Рады стараться.

SharpC / 2010-02-09 13:39:13

> Если в A осталось два числа — соединяем ребром соответствующие вершины, иначе — п. 1.

Опечатка, должно быть "Если в N осталось...".

Владимир / 2010-12-19 22:55:50

Спасибо за информацию!

У Вас хороший сайт.

Стараемся ;)

Анастасия / 2015-01-15 00:51:30

Подскажите, пожалуйста.

В последнем доказательстве - что означают d1, d2 и т. д.?

Эти обозначения введены в тексте статьи выше.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий