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

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

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

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

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

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

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

Например, схема

характеризует перестановку степени 6, в которой первый элемент становится третьим, второй остается вторым, третий становится пятым и т. д.

Рис. 6.10.

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

Тип данной перестановки степени определяется в зависимости от числа контуров длины которое она содержит, для Если обозначает число контуров длины то тип перестановки удобно описывать вектором Очевидно, тип должен удовлетворять условию (почему?). Тип предыдущей перестановки есть (1, 1, 1, 0, 0, 0), а перестановка «тепени 12, циклическое представление которой

имеет тип

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

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

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

Рис. 6.11.

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

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

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

четыре вершины, неупорядоченные пары;

четыре вершины, упорядоченные пары:

пять вершин, неупорядоченные пары:

Введем еще несколько вспомогательных понятий. Рассмотрим множество абстрактных объемов, называемых фигурами, и предположим, что с каждой фигурой связано одно из нескольких неотрицательных чисел (мы будем использовать столько числа 0, 1 и 2), которое будем называть ее объемом (в более общей форме, теорема Поня позволяет связывать с каждой фигурой

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

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

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

Если обозначает число неэквивалентных конфигураций (длины имеющих объем то формальный ряд

называется рядом подсчета, перечисляющим конфигурации (относительно

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

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

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

Рассмотрим затем конфигурации длины 10,

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

Подставляя вместо каждого в циклический индекс определенный ранее, и упрощая полученное выражение, получим

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

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

Рис. 6.12.

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

Наличие члена например, позволяет сделать вывод, что имеется 5 различных графов с двумя дугами. Эти графы показаны на рис. 6.13.

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

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

Рис. 6.13.

Поэтому ряд, перечисляющий фигуры, имеет вид

Подставляя вместо каждого в соответствующий циклический индекс (определенный ранее), получим

Так, имеется, например, 8 различных графов рассматриваемого типа с четырьмя ребрами. Они показаны на рис. 6.14.

Изменяя определения фигур, объемов и мы можем решить другие графотеоретпческпе задачи перечисления (см., например, [44]).

Рис. 6.14.

Дальнейшее развитие проблемы и доказательство теоремы Поия в более общей форме имеется, например, в [24] (библ. к гл. 1). Интересный обзор решенных и нерешенных задач перечисления можно найти в [43].