Дискретно-непрерывная математика (стр. 68 )

.... (п—1, 1) вершинами. Каждая из этих пар порож­дает два дерева в исходном графе, так как, например, пару (1, п—1) можно образовать двумя способами: (1, п—1) и (п—1, 1). Таким образом, чтобы получить общее число различных деревьев первоначального гра­фа, последнюю сумму следует разделить на 2(п— 1). Применяя названный выше результат из анализа, полу­чим, что число деревьев полного графа равно пп-2.

Упражнение 6. Проверить утверждение о том, что число дуб­лирований равно 2 (n— 1) на примере полного графа с четырьмя вер - шинами. Заметим, например, что дерево (а), показанное ниже, полу­чается шестью способами. Два способа заключаются в связывании подграфов, как показано в (b), причем в первом способе изолирован - ная вершина является первым подграфом разбиения, а (с) соответ­ствует второму, во втором способе (d) соответствует первому под­графу разбиения, а изолированная вершина — второму. Другие два способа получаются из (е) и два последних — из (f).

Рассмотрим доказательство этой теоремы, предло­женное Трентом. Пусть А — матрица инциденций (без одной строки) полного п вершинного графа с п—1 независимыми строками. Известно, что число различных деревьев в любом графе определяется детерминантом матрицы АА', который мы обозначим | АА'|. В нашем случае АА' имеет вид

Пусть T—вторая матрица порядка (n—1), элементы которой даются выражениями

Легко показать, что |T| = 1. Рассмотрим детерминант произведения

Так как |T| = 1, то | АА'|=пп-2. Теорема доказана.

В качестве еще одной иллюстрации возможных за­дач определим максимальное число контуров длины 3 (т. е. состоящих из трех дуг), которое может иметь пол­ный антисимметрический граф с п вершинами. Рассмотрим матрицу вершин этого графа, i-я строка матрицы дает отношения инцидентности для дуг, поло­жительно инцидентных i-й вершине (т. е. исходящих из нее), а i-й столбец дает инцидентности для дуг, отрица­тельно инцидентных этой вершине (входящих в нее). Если ri означает сумму элементов i-й строки, a ci — со­ответствующую сумму i-ro столбца, то ri +сi=п— 1, так как i-я вершина связана (п—1) ребрами с остальными (п— 1) вершинами.

Общее число циклов длины 3 равно

Однако это число не является числом контуров. В контуре все дуги ориентированы по направлению контура. Поэтому если две дуги положительно инцидентны одной верши­не, то они не могут обе входить в контур, потому что их ориентация противоположна.

Так как сумма ri элементов i-й строки дает число дуг, исходящих из i-й вершины, мы должны исключить из общего числа циклов

т. е. сумму по всем строкам числа сочетаний суммы элементов каждой стро­ки по два. Это дает для числа контуров

Так как граф полный, то число его ребер равно и должно выполняться равенство потому что общая сумма всех строк должна учитывать все реб­ра графа.

Теперь для числа контуров имеем

и задача заключается в определении ri при которых это количество максимально. Такой выбор ri соответствует специальной ориентации дуг графа, при которой число контуров максимально. При решении этой задачи достач точно определить ri так, чтобы была минимальной, потому что эта сумма вычитается из постоянного числа в написанном выше выражении, которое должно быть максимизировано. Предыдущие рассуждения будут также справедливыми, если мы возьмем сумму ci элементов столбцов и воспользуемся тем, что дуги, входя­щие в одну и ту же вершину, не могут быть сторонами одного контура. В этом случае наша задача сведется к определению ci, которые максимизируют

Таким образом, найдя ci, минимизирующие мы определим максимальное число контуров в графе. Заме­тим, что выражения для максимального числа контуров симметричны относительно ci и ri. Отсюда следует, что ci должно быть равно ri. Так как ri+ci=n—1, то в случае нечетных п получаем ri=(n—1)/2.

Упражнение 7. Подставить полученное значение ri - и получить точное выражение для максимального числа контуров. Определить также ri для случая четного п н найти максимальное число контуров для этого случая.

Замечание. Другая задача состоит в получении формулы для среднего числа висячих вершин дерева, задаваемого случайным образом. При решении этой задачи часто не удается получить удобную форму­лу для результата. Однако предполагая п достаточно большим, мы можем получить асимптотическую форму­лу, которая удобна для вычислений. Например, среднее число висячих вершин дерева, выбранного случайно среди всех деревьев, число которых было подсчитано выше, равно n/е, где е — основание натурального лога­рифма, т. е. е=2,718...

Были получены формулы для числа корневых графов, т. е. для графов, в которых выделена одна вершина, названная корнем, а также формулы для подсчета кор­невых звездчатых деревьев. Ряд результатов связан с ориентированными графами и с графами, имеющими кратные ребра, т. е. графами, в которых между каждой парой вершин может быть до k ребер.

В полном графе с п помеченными вершинами имеется ребер. Число графовс N ребрами равно

т. е. числу возможных сочетаний из ребер по N.

Предположим, что из ребер случайным образом выбраны N ребер. Какова вероятность того, что полу­ченный граф связен? Граф может состоять из несколь­ких компонент; чему равен размер самого большого де­рева, т. е. сколько ребер оно имеет? Заметим, что в этих задачах две вершины могут быть связаны только одним ребром. Однако такие же задачи можно поставить и для мультиграфов с кратными ребрами.

Можно показать, что для больших N общее число связных графов равнов случае помеченных вершин и в случае непомеченных вершин.

Процесс рождения или стационарный ветвящийся процесс, (называемый также процессом размножения) можно представить деревом, растущим из некоторого корня (корневым деревом), и рассмотреть ряд задач для этого прадерева. Пусть имеется частица и0 (соот­ветствующая корню дерева), которая порождает w ча­стиц u1, u2,…, где w=j с вероятностью рj. Каждая из появившихся новых частиц в свою очередь рождает uj1, uj2,…, и так далее. Рождение частиц происходит взаим­но независимо, и все частицы имеют одно и то же рас­пределение вероятностей для числа рождаемых частиц. Вероятность Рп того, что дерево состоит из п вершин, можно представить для больших п асимптотическим вы­ражением (n≡1 mod q), где А — постоян­ная величина, a q является наибольшим общим делителем для всех j таких, что рj≠0. Для других значений n Рn=0. Можно получить также асимптотические вы-. ражения для вероятности того, что w=j, и для распре­деления числа вершин с k исходящими дугами в де­ревьях, имеющих п вершин.

Применениетеоремы Пойя к задачам перечисления

Некоторые из основных задач перечисления в теории графов могут быть решены при помощи фундаменталь­ной комбинаторной теоремы Пойя. Сюда относят­ся задачи подсчета числа неизоморфных обыкновенных графов, имеющих р вершин и q ребер, или числа неизо­морфных обыкновенных ориентированных графов, име­ющих р вершин и q дуг, а также обобщения этих задач на случай, когда графы не обязательно обыкновенные (но когда максимальное число параллельных ребер или строго параллельных дуг ограничено).

Решение этих и близких к ним задач подсчета при помощи теоремы Пойя было предложено Харари. Для иллюстрации идей метода рассмотрим несколько примеров в виде следующих частных задач.

1. Для любых q определить число неизоморфных обыкновенных графов, имеющих 5 вершин и q ребер.

2. Для любых q определить число неизоморфных ре­гулярных обыкновенных ориентированных графов, име­ющих 4 вершины и q дуг.

3. Для любых q определить число неизоморфных графов, имеющих 4 вершины и q ребер, в которых лю­бая пара вершин соединяется не более чем двумя реб­рами и нет петель.