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

Перечисление графов

Голосование: 16, 3

Введение

Определение числа различных графов данного класса — это один из основных вопросов, возникающих о классе графов. Изучая теорию перечисления графов и отвечая на этот вопрос, приходится решать проблемы изоморфизмов для многих классов графов. Теорема перечисления Пойа (George Pólya), когда она впервые стала широко цениться в начале 1960-х, служила основным инструментом для решения проблем изоморфизмов. Данная статья посвящена описанию этого инструмента и приложения его для отыскания числа деревьев и корневых деревьев. Для осознания проблемы рассмотрим перечисление помеченных графов, это наиболее простая задача из теории перечисления. Затем рассмотрим производящие функции, группы подстановок, цикловые индексы, лемму Бернсайда (William Burnside) и, наконец, докажем теорему Пойа.

Перечисление помеченных графов

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

В помеченном графе порядка p вершинам приписываются целые числа от 1 до p. Например, граф, изображённый на рисунке слева, может быть помечен шестью различными способами, которые указаны справа.

Таким образом, два помеченных графа G1 и G2 считаются изоморфными тогда и только тогда, когда существует взаимнооднозначное отображение множества V(G1) на множество V(G2), сохраняющее не только смежность, но и распределение пометок. Возникает естественный вопрос: «Сколько существует помеченных графов порядка p

Ответим на вопрос, незначительно обобщив задачу следующим образом: найти число помеченных графов с данным числом вершин и рёбер. Пусть Gp(x) — многочлен, у которого коэффициент при xk равен числу помеченных графов порядка p, имеющих ровно k рёбер. Такой многочлен обычно называется производящей функцией для помеченных графов с данным числом вершин и рёбер. Если V — множество из p вершин, то существует различных неупорядоченных пар этих вершин. В каждом помеченном графе с множеством вершин V любая пара вершин является либо смежной, либо нет. Следовательно, число помеченных графов с k рёбрами равно .

Теорема

Производящая функция Gp(x) для помеченных графов порядка p задаётся соотношением

Так как Gp(x) = (1 + x)m и число Gp помеченных графов порядка p равно Gp(1), то

Для p = 3 эта формула ярко иллюстрируется на рисунке снизу. Таким образом, существуют восемь помеченных графов порядка 3 и только четыре (непомеченных) графа порядка 3. Существуют 64 помеченных графа порядка 4, но только 11 графов порядка 4.

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

Теорема

Производящая функция Dp(x) для помеченных орграфов порядка p задаётся соотношением

Производящие функции

При решении задач перечисления используются производящие функции, и мы с ними уже знакомы. Теперь рассмотрим их формальнее. Пусть a0, a1,a2, … — последовательность. Производящей функцией этой последовательности называется ряд вида

В задачах перечисления ai представляют собой число объектов с заданными свойствами. Производящую функцию называют перечисляющим рядом.

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

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

Теорема

Если

(1)

то для m > 0

(2)

Доказательство. Выражение (1) запишем следующим образом: A(x) = ea(x), где .

Дифференцируя обе части равенства получаем A′(x) = ea(x) a′(x) = A(x)a′(x) или что тоже самое более подробно

Тогда коэффициент при xm−1 соответственно в левой и правой части выражения будет равен

откуда вытекает утверждение теоремы. ♦

Группы подстановок

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

Множество Γ называется группой, если на нем задана бинарная операция (·), не выводящая за пределы множества и удовлетворяющая следующим трем условиям:

  1. Для любых x, y и z из Γ справедливо (x·yz = x·(y·z);
  2. В Γ существует единичный элемент e, такой что для любого x из Γ e·x = x·e = x;
  3. Для любого элемента x из Γ существует обратный элемент x−1 также из множества Γ, такой что x·x−1 = x−1·x = e.

Непустое подмножество A множества Γ называют подгруппой группы Γ, если оно удовлетворяет следующим двум условиям:

  1. Бинарная операция не выводит за пределы подмножества A;
  2. Для любого элемента x из A обратный к нему элемент x−1 также лежит в A.

Пусть A — некоторая подгруппа группы Γ. Правым классом смежности группы Γ по подгруппе A называется множество вида Ax = {y·x | y из A}, где x — произвольный элемент из Γ (аналогично определяются левые классы смежности). Известно также утверждение о том, что если A — подгруппа группы Γ, то группу Γ можно разложить в объединение правых (левых) классов смежности по подгруппе A.

Рассмотрим теперь множество X = {1, 2, …, n}. Подстановкой называется взаимно однозначное отображение aX → X. Умножением подстановок будем называть их композицию. Пусть A — некоторая совокупность подстановок множества X, замкнутая относительно операции умножения. Тогда A является группой подстановок на множестве объектов X. Порядок группы A, обозначаемый |A|, есть число подстановок A, а степень группы — это число n элементов в множестве объектов X.

Наиболее важными для нас примерами группы подстановок являются симметрическая группа Sn — группа всех подстановок на множестве из n объектов, и знакопеременная группа An — группа всех четных подстановок. Чтобы определить понятие четной подстановки введем понятие транспозиции.

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

Пусть A — группа подстановок с множеством объектов X = {1, 2, …, n}. Циклом длины k называется подстановка, обозначаемая (i1, i2, …, ik), которая переводит i1 в i2, i2 в i3, …, ik в i1. Известно, что каждая подстановка a может быть представлена в виде произведения непересекающихся циклов. Например, S3 = {(1)(2)(3), (12)(3), (13)(2), (23)(1), (123), (132)} или A3 = {(1)(2)(3), (123), (132)}.

Существует естественная связь между группами подстановок и графами.

Рассмотрим два графа G1 и G2. Взаимно однозначное отбражение a множества вершин графа G1 на множество вершин графа G2, сохраняющее смежность, называют изоморфизмом. Если G1 = G2, то a называется автоморфизмом графа. Совокупность всех автоморфизмов графа G, обозначаемая Γ(G), образует группу, называемую группой графа G, или группой автоморфизмов графа G. Таким образом, элементы группы Γ(G) являются подстановками, действующими на множестве вершин графа.

Рассмотрим граф G, изображенный на рисунке.

Его четыре вершины составляют множество X целых чисел 1, 2, 3, 4. Заметим, что следующий список подстановок

  • a1 = (1)(2)(3)(4)
  • a2 = (1)(3)(24)
  • a3 = (13)(2)(4)
  • a4 = (13)(24)

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

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

Цикловые индексы группы подстановок

Пусть A — группа подстановок с множеством объектов X = {1, 2, …, n} и a — некоторая подстановка из этой группы. Для каждого k = 1, 2, …, n через jk(a) обозначим число циклов длины k в разложении подстановки a в произведение непересекающихся циклов.

Тогда цикловой индекс группы A, обозначаемый Z(A) или Z(A, s1, s2, …, sn), представляет собой многочлен от переменных s1, s2, …, sn, определяемый формулой

(3)

Рассмотрим для примера симметрическую группу S3. Заметим, что тождественная подстановка (1)(2)(3) имеет три единичных цикла дающих слагаемое s13. Три подстановки (1)(23), (2)(13) и (3)(12) имеют каждая по единичному циклу и по одному циклу длины 2, так что получается одно слагаемое 3s1s2. Наконец, подстановки (123) и (132) вносят 2s3. Таким образом, имеем Z(S3) = (1/3!)(s13 + 3s1s2 + 2s3)

Для вычисления циклового индекса симметрической группы Sn введем понятие разбиения числа и рассмотрим несколько утверждений.

Назовем разбиением натурального числа n его представление в виде суммы некоторых натуральных чисел. Заметим, что каждая подстановка a на n объектах может быть связана с определенным разбиением числа n, имеющим для каждого k = 1, 2, …, n точно jk(a) частей, равных числу k. Будем задавать разбиение числа n посредством вектора (j) = (j1, j2, …, jn), где jk — число частей разбиения, равных k. Итак,

Пример

4 = 1 + 1 + 1 + 1 (4, 0, 0, 0)
4 = 1 + 1 + 2 (2, 1, 0, 0)
4 = 2 + 2 (0, 2, 0, 0)
4 = 1 + 3 (1, 0, 1, 0)
4 = 4 (0, 0, 0, 1)

Пусть h(j) — число подстановок в группе Sn, разложение которых на непересекающиеся циклы соответствует разбиению (j), в том смысле, что для каждого k выполняется jk = jk(a). Тогда имеет место следующая лемма.

Лемма

(4)

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

Теорема

Цикловой индекс симметрической группы дается формулой

(5)

где сумма берется по всем разбиениям (j) числа n, а h(j) задается выражением (4).

Пример

3 = 1 + 1 + 1 (3, 0, 0) h = 3! / 3! = 1
3 = 1 + 2 (1, 1, 0) h = 3! / 1·1!·2·1! = 3
3 = 3 (0, 0, 1) h = 3! / 3·1!

Z(S3) = 1/3! (s13 + 3s1s2 + 2s3)

Иногда удобно расматривать производящую функцию цикловых индексов и пользоваться следующим свойством.

Теорема

(6)

где Z(S0) = 1 по определению.

Часто бывает удобным выразить Z(Sn) через Z(Sk), где k < n. Рекуррентная формула, следующая из (6), может быть представлена следующим образом.

Теорема

Цикловой индекс симметрической группы удовлетворяет рекуррентному соотношению

(7)

Пример

  • Z(S0) = 1
  • Z(S1) = s1
  • Z(S2) = 1/2 (s1s1 + s2)
  • Z(S3) = 1/3 (s1 1/2 (s12 + s2) + s2s1 + s3) = 1/6 (s13 + 3s1s2 + 2s3)

Лемма Бернсайда

Пусть A — группа подстановок с множеством объектов X = {1, 2, …, n}. Элементы x и y из X называются A-эквивалентными, если существует подстановка a из A, такая, что ax = y. Нетрудно показать, что введенное нами отношение есть отношение эквивалентности. Множество X разбивается на классы эквивалентности. Эти классы называются орбитами.

Для каждого x из X положим

(8)

Так определенное множество A(x) называется стабилизатором элемента x. Нетрудно видеть, что стабилизатор является подгруппой группы A. Заметим, что всякий раз, когда элементы x и y принадлежат одной и той же орбите, множества A(x) и A(y) являются сопряженными подгруппами группы A (то есть существует такая подстановка a из A, что A(y) = aA(x)a−1) и, следовательно, |A(x)| = |A(y)|.

Теорема

Для любого элемента y из орбиты Y группы A выполнятся следующее соотношение

|A| = |A(y)| · |Y| (9)

Доказательство. Разложим группу A в объединение правых классов смежности по подгруппе A(y):

Теперь остается только указать естественноe взаимно однозначное соответствие между этими классами смежности и элементами орбиты Y. Для каждого i = 1, …, m сопоставляем классу смежности ai A(y) элемент ai y из Y. Если i не равно j, то ai y не равно aj y, так как иначе бы подстановка aj−1ai принадлежала подгруппе A(y) и, следовательно, подстановка ai являлась бы элементом множества aj A(y), что противоречит соотношению ai A(y) ∩ aj A(y) = Ø. Значит, указанное соответствие является взаимно однозначным. Для всякого объекта y′ из Y при некоторой подстановке a из A выполняется равенство ay = y′. Из разложения группы A на классы смежности следует, что a = aib, если b принадлежит A(y). Следовательно, y′ = ai y и, таким образом, каждый элемент орбиты Y соответствует некоторому классу смежности. Значит, m есть число элементов в орбите Y и формула (9) доказана. ♦

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

Лемма Бернсайда

(1911, Burnside's Lemma or the Pólya-Burnside Lemma or the Cauchy-Frobenius Lemma)

Число N(A) орбит группы A дается формулой

(10)

Доказательство. Пусть X1, X2, …, Xm — орбиты группы A, и для каждого i = 1, …, m пусть xi — элемент i-й орбиты Xi. Тогда из формулы (9) имеем

(11)

Мы видели, что если x и xi принадлежат одной и той же орбите, то |A(x)| = |A(xi)|. Следовательно, соотношение (11) можно записать так:

(12)

или, в других обозначениях,

(13)

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

(14)

Но есть в точности j1(a). Таким образом, для завершения доказательства надо обе части разделить на |A|. ♦

Также нам нужно будет ограничивать действие группы A на некоторое подмножество Y множества X, где Y   объединение каких-либо орбит группы A. Поэтому обозначим через A|Y множество подстановок, действующих на Y и получающихся с помощью ограничения на подмножество Y соответствующих подстановок группы A. Для каждой подстановки a из группы A число элементов в Y, неподвижных относительно подстановки a, обозначим через j1(a|Y). Теперь можно сформулировать следствие леммы Бернсайда.

Ограниченная форма леммы Бернсайда

(15)

Теорема Пойа

Пусть A — группа подстановок с множеством объектов X = {1, 2, …, n}, и пусть B — конечная группа подстановок со счетным множеством объектов Y, содержащим не менее двух элементов. Тогда степенная группа, обозначаемая BA, имеет в качестве множества объектов совокупность YX всех функций, действующих из X в Y. Подстановками группы BA являются все упорядоченные пары подстановок a из A и b из B, записываемые в виде (ab). Образ произвольной функции f из YX при действии на нее подстановки (ab) дается формулой

(ab)f(x) = bf(ax) (16)

при всех x из X.

Для того, чтобы привести классическую формулу перечисления Пойа, мы возьмем B = E — единичной группе на множестве Y. Рассмотрим теперь степенную группу EA, действующую на множестве YX. Пусть wY → {0, 1, 2, …} — функция, область значений которой является множеством неотрицательных целых чисел и для которой |w−1(k)| < ∞ при всех k. В терминах теории перечисления ck = |w−1(k)| для каждого k = 0, 1, 2, … называют числом «фигур» веса k.

Об элементе y из Y, для которого w(y) = k, говорят, что он имеет вес k, а функцию w называют весовой функцией. Далее, ряд

(17)

относительно переменной x, который перечисляет элементы множества Y в соответствии с их весами, называют «перечисляющим рядом для фигур».

Вес функции f из YX определяется формулой

(18)

и тогда нетрудно показать, что функции, принадлежащие одной и той же орбите степенной группы EA, имеют одинаковые веса. Весом w(F) орбиты F группы EA назовем вес любой функции f из орбиты F. Так как |w−1(k)| < ∞ для всякого k = 0, 1, 2, …, то существует только конечное число орбит каждого веса. Обозначим через Ck число орбит веса k. Ряд

(19)

относительно переменной x назовем «перечисляющим рядом для функций» или «перечисляющим рядом для конфигураций».

Теперь мы можем сформулировать основную теорему, выражающую ряд C(x) в терминах циклового индекса Z(A) и ряда c(x). В приводимой ниже формуле Z(Ac(x)) является сокращением для Z(A, c(x), c(x2), c(x3), …).

Теорема (теорема перечисления Пойа, 1927)

Ряд C(x), перечисляющий функции, получается с помощью подстановки в цикловой индекс Z(A) на место каждой переменной sk ряда c(xk), перечисляющего фигуры. Символически:

(20)

Доказательство. Пусть e — тождественная подстановка на Y. Для всякой подстановки a из A и любого k = 0, 1, 2, … обозначим через φ(ak) число функций веса k, неподвижных относительно подстановки (ae). Ограничивая для каждого k действие степенной группы EA на множество функций веса k и применяя ограниченную форму леммы Бернсайда (15), имеем

(21)

Следовательно,

(22)

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

(23)

Ряд ∑ φ(akxk перечисляет все функции, неподвижные относительно подстановки (ae), и мы постараемся найти другую форму для этого ряда.

Предположим, что функция f из YX непожвижна относительно подстановки (ae). Тогда ((aef)(x) = f(x) для всех x из X и в силу формулы (16), имеем ((aef)(x) = ef(ax). Таким образом, для всех x должно выполняться равенство f(ax) = f(x), то есть функция f должна быть постоянной на непересекающихся циклах подстановки a. Обратно, все функции, постоянные на циклах подстановки a, неподвижны относительно подстановки (ae).

Пусть zr — цикл длины r в подстановке a. Если функция f отображает элементы цикла zr в один из ck элементов множества Y, имеющих вес k, то цикл zr вносит в вес функции f значение r·k. Тогда легко видеть, что для каждого k коэффициент при xrk в ряду

(24)

равен числу способов, которыми можно определить функцию f на элементах цикла zr так, чтобы она была неподвижна относительно подстановки (ae) и чтобы вклад в вес w(f) составлял r·k. Отсюда следует, что ряд [c(xr)]jr(a) перечисляет в соответствии с их весами различные способы определения функций, постоянных на всех циклах длины r подстановки a.

Рассматривая все циклы подстановки a, мы можем выразить ряд для функций, постоянных на циклах, в виде произведения

(25)

Теперь утверждение теоремы Пойа (20) следует из (23), (25) и определения циклового индекса Z(A). ♦

Перечисление корневых деревьев

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

Пусть теперь

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

Поэтому четыре первых слагаемых производящей функции T(x) даются соотношением

T(x) = x + x2 + 2x3 + 4x4 + … (26)

Теорема

Перечисляющий ряд T(x) для корневых деревьев удовлетворяет соотношению

(27)

Доказательство. Сначала найдем производящую функцию, перечисляющую такие корневые деревья, корень которых имеет степень n. Замечаем, что каждое из таких деревьев естественным образом соответствует некоторому «сочетанию с повторениями» из n корневых деревьев. Это соответствие для n = 4 проиллюстрировано на рисунке.

Более подробно: пусть дана совокупность из n корневых деревьев; новое корневое дерево строится путем добавления одной новой вершины и установления смежности этой вершины с каждым из корней n первоначальных корневых деревьев. Ясно, что все деревья, у которых корни имеют степень n, могут быть построены указанным способом. Чтобы найти число таких деревьев, рассмотрим степенную группу ESn множеством объектов YX, где E — единичная группа, X = {1, …, n} и Y — множество всех корневых деревьев. Тогда каждая функция из YX соответствует некоторому упорядоченному набору, состоящему из n корневых деревьев. Определим вес произвольного корневого дерева из Y как число вершин в этом дереве. Тогда T(x) перечисляет элементы Y в соответствии с их весами и называется «рядом, перечисляющим фигуры», для множества Y. Таким образом, вес каждой функции из YX, (определенной в в соответствии с формулой), представляет собой общее число вершин в n корневых деревьях из того набора длины n, которому соответствует взятая функция.

Четыре корневых дерева и соответствующее им дерево, корень которого имеет степень 4.

Так как группа Sn состоит из всех подстановок множества X, то орбиты степенной группы ESn соответствуют в точности корневым деревьям, у которых корни имеют степень n. Заметим, что вес каждой орбиты, который является весом и любой функции, содержащейся в этой орбите, ровно на единицу меньше общего числа вершин в корневом дереве, сопоставленном орбите. Поэтому, взяв в теореме Пойа A = Sn и в качестве ряда, перечисляющего фигуры, производящую функцию T(x), получаем ряд, перечисляющий функции: Z(SnT(x)). Коэффициент при xp в Z(SnT(x)) представляет собой число корневых деревьев порядка p + 1, у которых корень имеет степень n. Умножение ряда Z(SnT(x)) на x «подправляет» веса так, что коэффициент при xp в xZ(SnT(x)) равен числу этих деревьев с p вершинами. Затем, суммируя по всем возможным значениям n, получаем само T(x):

(28)

Доказательство завершается применением тождества

к сумме цикловых индексов, стоящей в правой части соотношения (28). ♦

Из этой теоремы следует, что T(x) однозначно определяется функциональным уравнением, так как формула (27) дает способ определения коэффициентов T(x) по индукции. Чтобы увидеть это положим

Следовательно,

(29)

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

(30)

Комбинируя (29) и (30), выражаем Tp+1 через T1, …, Tp

(31)

Показать все результаты для p = 1, …, 100.

Перечисление деревьев

Реберно-корневым графом будем называть граф, который имеет выделенное ребро, называемое корневым ребром. Ребро (uv) графа G назовем симметричным, если существует f — автоморфизм графа G, такой что f(u) = v, f(v) = u.

Примеры несимметричного и симметричного ребра

Пусть теперь

производящая функция для реберно-корневых деревьев, так что Lp — число реберно-корневых деревьев порядка p.

Теорема

Ряд L(x) выражается через ряд для деревьев T(x) с помощью формулы

L(x) = Z(A2 − S2T(x)) (32)

Доказательство. Заметим, что любые два различных корневых дерева определяют реберно-корневое дерево с несимметричным корневым ребром. Это соответствие проиллюстрировано на рисунке.

Два корневых дерева и соответствующее им реберно-корневое дерево

Таким образом, деревья перечисляемые рядом L(x), могут быть интерпретированы как 2-подмножества, состоящие из графов, перечисляемых рядом T(x). Значит мы можем применить формулу (26) и получить соотношение (32). ♦

Рассмотрим произвольный граф G = (VE). Вершину v из V называют точкой сочленения, если при ее удалении вместе с инцидентными ребрами, число компонент связности графа увеличивается. Связный граф без точек сочленения называется двусвязным графом. Если U — некоторое подмножество множества V, то граф G′ = (UE′), где E′ — множество всех ребер, таких что оба конца ребра принадлежат множеству U, называется порожденным подграфом. Максимальные по включению двусвязные порожденные подграфы графа G называются двусвязными компонентами или блоками.

Пусть Γ(G) — группа автоморфизмов этого графа G. Две вершины будем считать Γ(G)-эквивалентными, если существует автоморфизм, переводящий одну вершину в другую.

Две вершины будем называть неподобными, если принадлежат разным орбитам группы подстановки Γ(G). Числом неподобных вершин p* будем называть число орбит группы Γ(G). Группа графа G определяет также классы подобных блоков. Два блока назовем неподобными, если они принадлежат разным классам эквивалентности. Пусть pi* — число неподобных вершин в i-м классе блоков среди b* неподобных блоков. Тогда p* и pi* связываются формулой, приводимой в следующей теореме.

Теорема (о характеристике неподобия для графов)

Для всякого графа G

(33)

Доказательство. Доказательство теоремы проведем индукцией по числу классов блоков. Пусть G — произвольный граф. Если существует точно один класс блоков, т. е. b* = 1, то p* = p1* и формула (33) очевидно, справедлива. В ином случае рассмотрим произвольный блок графа G, имеющий в точности одну точку сочленения и предположим, что этот блок принадлежит классу, номер которого равен единице. Удалим из графа G вершины всех блоков, входящих в этот класс, оставив только точки сочленения. Граф G′, полученный в результате такой операции, имеет b*−1 классов блоков и p*−(p1*−1) классов вершин. Применяя индуктивное предположение к графу G′, имеем формулу (33) для графа G. ♦

Чтобы применить эту теорему к деревьям, обозначим числа неподобных вершин и ребер произвольного дерева T соответственно через p* и q*. Пусть s — число симметричных ребер.

Следствие (теорема о характеристике неподобия для деревьев)

Число s симметричных ребер произвольного дерева равно 0 или 1 и

p* − (q* − s) = 1. (34)

Доказательство. Не трудно видеть, что число симметричных ребер дерева не превосходит двух. Затем обращаем внимание на то, что q* есть число неподобных блоков, так что b* = q*. Далее, pi* = 2 для каждого класса блоков (ребер), кроме класса с симметричным ребром. Для последнего класса pi* = 1 в силу определения. Итак, правая часть формулы (33) равна q*s и доказательство следствия завершено. ♦

Пусть

производящая функция для деревьев, так что tp есть число деревьев порядка p.

Теорема

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

(35)

Доказательство. На первом шаге доказательства просуммируем формулу 1 = p* − (q* −s) по всем деревьям, имеющим ровно p вершин. Получим tp = Tp − Lp. Суммируя по всем p имеем t(x) = T(x) − L(x) = T(x) − Z(A2 − S2T(x)) = T(x) − (Z(A2T(x)) − Z(S2T(x))).
Z(A2) = s12
Z(S2) = 1/2 (s12 + s2)
Z(A2) − Z(S2) = 1/2 (s12 − s2)

Далее, положив s1 = T(x), s2 = T(x2), получаем утверждение теоремы. ♦

Первые члены ряда t(x) выглядят следующим образом:

t(x) = x + x2 + x3 + 2x4 + 3x5 + 6x6 + …

Легко видеть, что если p четно, то

А если p нечетно, то

Показать все результаты для p = 1, …, 100.

Заключение

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

Литература

  1. Зелянин Р.В. Некоторые задачи перечисления графов — Сыктывкарский ГУ (сайт)
  2. Липский В. Комбинаторика для программистов: Пер. с польск. — М.: Мир, 1988. — 213 с., ил.
  3. Харари Ф., Палмер Э. Перечисление графов: Пер. с. англ. — М.: Мир, 1977.

Денис Захаров


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