Обсуждение участницы:Анна

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

Помеченные графы

Определение:

Помеченный граф с [math]n[/math] вершинами — граф, у которого каждая вершина помечена целым числом от [math]1[/math] до [math]n[/math].

Более формально определить это понятие можно так: назовем распределением [math]f[/math] меток в графе [math]G[/math] с [math]n[/math] вершинами биекцию между множеством вершин графа и множеством [math]\{1 \cdots n\}[/math]. Тогда помеченным графом называется пара [math](G, f)[/math].

Определение:

Два помеченных графа [math](G_{1}, f_{1})[/math] и [math](G_{2}, f_{2})[/math] изоморфны, если существует изоморфизм между [math]G_{1}[/math] и [math]G_{2}[/math], сохраняющий распределение меток.

Все помеченные графы с тремя вершинами показаны на рисунке 1. [math]4[/math] различных графа с [math]3[/math] вершинами приводят к [math]8[/math] различным помеченным графам.

Рис. 1. Помеченные графы с тремя вершинами.

Для нахождения числа помеченных графов с [math]p[/math] вершинами нужно заметить, что каждое из [math] p\choose 2[/math] возможных ребер либо принадлежит графу, либо нет.

Теорема (1):

Число помеченных графов с [math]p[/math] вершинами равно [math] 2^{p\choose 2}[/math].

Следовательно, число помеченных графов с [math]q[/math] ребрами равно [math] {p\choose 2}\choose q[/math].

Теорема (Кэли):

Число помеченных деревьев с [math]p[/math] вершинами равно [math] p^{p - 2}[/math].

Теорема (2):

Данный граф [math]G[/math] можно пометить [math]\frac{p!}{|\Gamma(G)|}[/math] способами.

Доказательство:

[math]\triangleright[/math]

Приведем набросок доказательства. Пусть [math]A[/math] — группа подстановок, действующая на множестве [math]X[/math]. Для всякого элемента [math]x \in X[/math] орбитой [math]\Theta(x)[/math] элемента [math]x[/math] называется подмножество множества [math]X[/math], состоящее из всех элементов [math]y \in X[/math] таких, что [math]\alpha \cdot x = y[/math] для некоторой подстановки [math]\alpha[/math] из [math]A[/math]. Стабилизатором [math]A(x)[/math] элемента [math]x[/math] называется подгруппа группы [math]A[/math], состоящая из всех подстановок из [math]A[/math], оставляющих элемент [math]x[/math] неподвижным. Теорема является следствием соотношения [math]|A| = |\Theta(x)|\cdot|A(x)|[/math] и его интерпретации в настоящем контексте.

[math]\triangleleft[/math]

Рис. 2. Помеченные деревья с четырьмя вершинами.

Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их [math]16[/math]. Среди них [math]12[/math] изоморфны цепи [math]P_{4}[/math] и [math]4[/math] — графу [math]K_{1, 3}[/math]. Порядок группы [math]\Gamma(P_{4})[/math] равен [math]2[/math]. Порядок группы [math]K_{1, 3} = 6[/math]. Так как [math]p = 4[/math], то имеем [math]\frac{4!}{|\Gamma(P_{4})|} = 12[/math] и [math]\frac{4!}{|\Gamma(K_{1, 3})|} = 4[/math].

Теорема перечисления Пойа

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

Теорема:

Пусть [math]A[/math] — группа подстановок, действующая на множестве [math]X[/math] с орбитами [math]\Theta_{1}, \Theta_{2} \cdots \Theta_{n}[/math] и [math]\omega[/math] — функция, приписывающая веса каждой орбите (весовая функция). Более того, [math]\omega[/math] определяется на [math]X[/math] так, что [math]\omega(x) = \omega(\Theta_{i})[/math], если [math]x \in \Theta_{i}[/math]. Тогда сумма весов орбит равна [math]|A| \sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x} \omega(x)[/math].

Доказательство:

[math]\triangleright[/math]

Уже упоминалось о том, что порядок [math]|A|[/math] группы [math]A[/math] равен [math]|A(x)| \cdot |\Theta(x)|[/math] для любого [math]x \in X[/math], где [math]A(x)[/math] — стабилизатор элемента [math]x[/math]. Так как весовая функция постоянна на элементах данной орбиты, то справедливо равенство [math]|\Theta_{i}| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}\omega(x)[/math] для каждой орбиты [math]\Theta_{i}[/math]. Домножив второе равенство на первое и сократив, получаем [math]|A| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)[/math]. Суммируя по всем орбитам, находим [math]|A|\sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{i=1}^n \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)[/math], откуда непосредственно следует доказываемое соотношение.

[math]\triangleleft[/math]

Как следствие из этой теоремы выведем традиционную формулу Бернсайда. Для подстановки [math]\alpha[/math] через [math]j_{k}(\alpha)[/math] обозначим число циклов длины [math]k[/math] в её разложении в произведение непересекающихся циклов.

Лемма (Бернсайд):

Число [math]N(A)[/math] орбит группы подстановок [math]A[/math] равно [math]N(A) = \frac{1}{|A|}\sum\limits_{\alpha \in A}j_{1}(\alpha)[/math].

Доказательство:

[math]\triangleright[/math]

Так как в доказательстве этой леммы мы не учитываем значения весовой функции, то [math]|A|N(A) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x}1[/math], но [math]\sum\limits_{x = \alpha x}1[/math] и есть [math]j_{1}(\alpha)[/math], то есть для получения исходной формулы нужно поделить обе части равенства на [math]|A|[/math].

[math]\triangleleft[/math]

Теорема Гуйя-Ури

Определение:

Ориентированный сильно связный граф называется орсвязаными.

Лемма о длине цикла в ориентированном графе

Лемма (о длине цикла в ориентированном графе):

Пусть [math]G[/math] — произвольный ориентированный граф и для каждой вершины [math]v \in V(G)[/math] выполняется [math]deg^{out}(v) \geqslant \delta[/math]. Если [math]\delta \geqslant 2[/math], то в графе [math]G[/math] существует простой цикл [math]C[/math] длины хотя бы [math]\delta + 1[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим путь максимальной длины [math]P = v_0 v_1 \dots v_s[/math]. Из последней вершины [math]v_s[/math] выходит хотя бы [math]\delta - 1[/math] ребро в вершины, отличные от [math]v_{s - 1}[/math]. Так как путь [math]P[/math] максимальный, то продлить его нельзя, а значит, что из [math]v_s[/math] выходят ребра только в вершины, содержащиеся в пути [math]P[/math]. Пусть [math]v_m \in P[/math] — вершина с наименьшим номером, в которую входит ребро из [math]v_s[/math]. Тогда во множество [math]\{v_m \dots v_{s - 1}\}[/math] входят не менее [math]\delta[/math] ребер, выходящих из [math]v_s[/math]. То есть в это множестве хотя бы [math]\delta[/math] вершин. Значит, в цикле [math]v_m \dots v_{s - 1} v_s[/math] не менее [math]\delta + 1[/math] вершины.

[math]\triangleleft[/math]

Теорема Гуйя-Ури

Теорема (Гуйя-Ури, Ghouila-Houri):

Если [math]G[/math] — сильно связный ориентированный граф c [math]n[/math] вершинами и для каждой [math]v \in V(G)[/math] выполняется [math] \Bigg\{ \begin{matrix} deg^{in}(v) \geqslant n/2 \\ deg^{out}(v) \geqslant n/2 \\ \end{matrix} [/math], тогда [math]G[/math] — гамильтонов.

Доказательство:

[math]\triangleright[/math]

Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при [math]n = 2[/math] и [math]n = 3[/math]. Тогда существует орсвязный граф [math]G[/math] с [math]n \geqslant 4[/math], который удовлетворяет условию и при этом не является гамильтоновым. Пусть [math]C[/math] — максимальный цикл в [math]G[/math] длины [math]k[/math]. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение [math]1 + n/2 \leqslant k \lt n[/math]. Теперь рассмотрим [math]P = v_0 \dots v_l[/math] — путь максимальной длины [math]l \geqslant 0[/math] в [math]G[/math] такой, что никакая вершина этого пути не принадлежит циклу [math]C[/math]. Тогда [math]k + l + 1 \leqslant n[/math]. Следовательно, [math]l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2[/math]. Таким образом, [math]l \leqslant n/2 - 2[/math]. Это значит, что в вершину [math]v_0[/math] входят как минимум два ребра, выходящие из вершин, лежащих на [math]C[/math], а из вершины [math]v_l[/math] выходят как минимум два ребра, которые входят в вершины, принадлежащие [math]C[/math] (так как если бы эти вершины не лежали на данном цикле, путь [math]P[/math] можно было бы продлить). Пусть [math]A[/math] — множество вершин, принадлежащих [math]C[/math], ребра из которых приходят в вершину [math]v_0[/math], а [math]a[/math] — их количество. Тогда [math]a \geqslant 2[/math]. Для каждой такой вершины следующая за ней в цикле [math]C[/math] [math]l + 1[/math] вершина не содержит входящих ребер, начало которых принадлежит [math]v_l[/math], иначе граф [math]G[/math] содержал бы цикл длины [math]\gt k[/math]. Заметим, что среди вершин множества [math]A[/math] должна существовать такая вершина [math]y[/math], что следующая за ней [math]l + 1[/math] вершина в цикле [math]C[/math] не является ни отцом [math]v_0[/math], ни сыном [math]v_l[/math]. Рассмотрим оставшуюся [math]a - 1[/math] вершину множества [math]A[/math], отличную от [math]y[/math]. В следующую за каждой из них, очевидно, не может приходить ребро из [math]v_l[/math]. Следовательно, как минимум [math](a - 1) + (l + 1) = a + l[/math] вершин [math]C[/math] не являются сыновьями [math]v_l[/math], в противном случае, опять же, граф содержал бы цикл длины [math]\gt k[/math]. Так как [math]P[/math] — самый длинный путь в [math]G[/math], ни одна вершина которого не принадлежит [math]C[/math], каждая вершина, ребро из которой приходит в [math]v_0[/math], лежит либо на [math]P[/math], либо на [math]C[/math]. Так как [math]deg^{in}(v_0) \geqslant n/2[/math], то [math]a + l \geqslant n/2[/math], следовательно [math]deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1[/math]. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.

[math]\triangleleft[/math]