КОМБИНАТОРНЫЕ ЗАДАЧИ

6.5. Примеры комбинаторных задач в теории графов

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

При решении задач перечисления следует различать помеченный и непомеченный или свободный (топологический) граф.

Два графа, вершины которых помечены, считаются тождественными (неразличимыми) в том и только в том случае, когда любые две вершины, помеченные одинаково в обоих графах, имеют одинаковое число инцидентных им ребер. Так, два графа могут считаться различными, даже если они изоморфны.

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

определения числа графов, обладающих определенным свойством, например, содержащих циклы длины 3.

Число помеченных графов (не обязательно связных) с помеченными вершинами и непомеченными ребрами, в которых каждая пара вершин связана не более чем одним ребром, равно Для того чтобы получить это число, последовательно выбираем по различных ребер из ребер полного -вершин-ного графа. Если взять 4 вершины и 4 ребра, то существует 15 возможных пометок на двух топологически различных графах.

Рис. 6.8.

Рис. 6.9.

На рис. 6.8 показано число пометок для двух топологически неэквивалентных графов с четырьмя вершинами и тремя, четырьмя, пятью и шестью ребрами [48].

Многие задачи перечисления в теории графов являются абстракциями физических задач (например, задач статистической механики). Графическая формулировка таких задач облегчает вычислительный процесс. Некоторые из используемых при этом понятий связаны с деревьями специального типа. Граф без точек сочленения называется звездой, и следовательно, связный граф можно представить как объединение звезд, связанных в точках сочленения. Из обычного определения дерева следует, что дерево есть граф с точками сочленения, составляющие звезды которого состоят из единственного ребра. Если составляющие звезды являются многоугольниками, то граф называется деревом Хусими. Граф, показанный на рис. 6.9, становится деревом сими, если две его точки сочленения соединить второй цепью.

Если звезды, составляющие граф, более сложны, то граф называется звездчатым деревом (деревом звезд). Если все звезды изоморфны, то имеем чистое звездчатое дерево, в противном случае граф называется смешанным звездчатым деревом. Когда типы звезд не оговариваются, мы имеем просто связный граф. Дерево, ребра которого помечены значками плюс или минус, называется знаковым деревом.

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

В процессе этих выкладок можно определить число деревьев полного графа с помеченными вершинами. Кэли впервые доказал, что это число равно Приведем интересное доказательство этого факта по индукции [72].

Теорема 6.4. Число деревьев полного графа с помеченными вершинами равно

Доказательство. Для того чтобы избежать лишних выкладок, укажем сразу следующее известное в анализе тождество:

Теорема, очевидно, справедлива для одновершинного графа, так как Предположим, что теорема справедлива для полного графа с числом вершин, меньшим и докажем, что она справедлива для -вершин-ного полного графа. Обозначим через число деревьев полного графа с вершинами. Разделим вершин на два множества, одно из элементов и второе из элементов, где может быть любым из чисел По индуктивному предположению, число деревьев первого подграфа равно а второго — Исследуем все способы связи дерева первого

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

Однако вершин можно выбрать среди вершин

способами, и следовательно, если мы умножим полученное выше число деревьев для одного разбиения на число всевозможных разбиений при данном и просуммируем по I, то получим

Остается рассмотреть вопрос дублирования. Некоторые деревья исходного графа могут входить в последнюю сумму более одного раза. Действительно, так как существует способ выбора подграфа с вершинами, то по мере увеличения и приближения величина уменьшается до 1. Таким образом, роли подграфов с вершинами взаимно меняются. В результате оказывается, что существует пар подграфов с (

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

(см. скан)

(см. скан)

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

Пусть - вторая матрица порядка элементы которой даются выражениями

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

Так как то Теорема доказана.

В качестве еще одной иллюстрации возможных задач определим максимальное число контуров длины 3 (т. е. состоящих из трех дуг), которое может иметь полный антисимметрический граф с вершинами [5, гл. 1]. Рассмотрим матрицу вершин этого графа, строка

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

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

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

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

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

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

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

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

(см. скан)

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

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

кратные ребра, т. е. графами, в которых между каждой парой вершин может быть до ребер.

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

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

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

Процесс рождения или стационарный ветвящийся процесс, (называемый также процессом размножения) можно представить деревом, растущим из некоторого корня (корневым деревом), и рассмотреть ряд задач для этого прадерева. Пусть имеется частица (соответствующая корню дерева), которая порождает до частиц где с вероятностью Каждая из появившихся новых частиц в свою очередь рождает и так далее. Рождение частиц происходит взаимно независимо, и все частицы имеют одно и то же распределение вероятностей для числа рождаемых частиц. Вероятность того, что дерево состоит из вершин, можно представить для больших асимптотическим выражением где А — постоянная величина, является наибольшим общим делителем для всех таких, что Для других значений Можно получить также асимптотические

выражения для вероятности того, что и для распределения числа вершин с исходящими дугами в деревьях, имеющих вершин.