|
|
| Строка 1: |
Строка 1: |
| − | = Перечисления графов = | + | = 1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex> = |
| − | | |
| − | == Помеченные графы ==
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | '''Помеченный граф''' с <tex>n</tex> вершинами {{---}} граф, у которого каждая вершина помечена целым числом от <tex>1</tex> до <tex>n</tex>.
| |
| − | }}
| |
| − | | |
| − | Более формально определить это понятие можно так: назовем распределением <tex>f</tex> меток в графе <tex>G</tex> с <tex>n</tex> вершинами биекцию между множеством вершин графа и множеством <tex>\{1 \cdots n\}</tex>. Тогда помеченным графом называется пара <tex>(G, f)</tex>.
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | Два помеченных графа <tex>(G_{1}, f_{1})</tex> и <tex>(G_{2}, f_{2})</tex> '''изоморфны''', если существует изоморфизм между <tex>G_{1}</tex> и <tex>G_{2}</tex>, сохраняющий распределение меток.
| |
| − | }}
| |
| − | | |
| − | Все помеченные графы с тремя вершинами показаны на рисунке 1. <tex>4</tex> различных графа с <tex>3</tex> вершинами приводят к <tex>8</tex> различным помеченным графам.
| |
| − | | |
| − | {| cellpadding="2"
| |
| − | | || [[Файл:Перечисл1.jpg|thumb|left|420px|Рис. 1. Помеченные графы с тремя вершинами.]]
| |
| − | |}
| |
| − | | |
| − | Для нахождения числа помеченных графов с <tex>p</tex> вершинами нужно заметить, что каждое из <tex dpi = "165"> p\choose 2</tex> возможных ребер либо принадлежит графу, либо нет.
| |
| − | | |
| − | {{Теорема
| |
| − | |about=1
| |
| − | |statement=
| |
| − | Число помеченных графов с <tex>p</tex> вершинами равно <tex dpi = "165"> 2^{p\choose 2}</tex>.}}
| |
| − | | |
| − | Следовательно, число помеченных графов с <tex>q</tex> ребрами равно <tex dpi = "165"> {p\choose 2}\choose q</tex>.
| |
| − | | |
| − | {{Теорема
| |
| − | |author=Кэли
| |
| − | |statement=
| |
| − | Число помеченных деревьев с <tex>p</tex> вершинами равно <tex> p^{p - 2}</tex>.}}
| |
| − | | |
| − | {{Теорема
| |
| − | |about=2
| |
| − | |statement=
| |
| − | Данный граф <tex>G</tex> можно пометить <tex dpi = "160">\frac{p!}{|\Gamma(G)|}</tex> способами.
| |
| − | |proof=
| |
| − | Приведем набросок доказательства.
| |
| − | | |
| − | Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex>. Для всякого элемента <tex>x \in X</tex> '''орбитой''' <tex>\Theta(x)</tex> элемента <tex>x</tex> называется подмножество множества <tex>X</tex>, состоящее из всех элементов <tex>y \in X</tex> таких, что <tex>\alpha \cdot x = y</tex> для некоторой подстановки <tex>\alpha</tex> из <tex>A</tex>. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>A</tex>, состоящая из всех подстановок из <tex>A</tex>, оставляющих элемент <tex>x</tex> неподвижным. Теорема является следствием соотношения <tex>|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контексте.}}
| |
| − | | |
| − | {| cellpadding="2"
| |
| − | | || [[Файл:Перечисл2.jpg|thumb|left|720px|Рис. 2. Помеченные деревья с четырьмя вершинами.]]
| |
| − | |} | |
| − | | |
| − | Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их <tex>16</tex>. Среди них <tex>12</tex> изоморфны цепи <tex>P_{4}</tex> и <tex>4</tex> {{---}} графу <tex>K_{1, 3}</tex>. Порядок группы <tex>\Gamma(P_{4})</tex> равен <tex>2</tex>. Порядок группы <tex>K_{1, 3} = 6</tex>. Так как <tex>p = 4</tex>, то имеем <tex dpi = "160">\frac{4!}{|\Gamma(P_{4})|} = 12</tex> и <tex dpi = "160">\frac{4!}{|\Gamma(K_{1, 3})|} = 4</tex>.
| |
| − | | |
| − | == Теорема перечисления Пойа ==
| |
| − | | |
| − | Пойа показал, как получить формулу, перечисляющую орбиты в соответствии с весами и зависящую от циклической структуры подстановок данной группы.
| |
| − | | |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex> с орбитами <tex>\Theta_{1}, \Theta_{2} \cdots \Theta_{n}</tex> и <tex>\omega</tex> {{---}} функция, приписывающая веса каждой орбите (весовая функция). Более того, <tex>\omega</tex> определяется на <tex>X</tex> так, что <tex>\omega(x) = \omega(\Theta_{i})</tex>, если <tex>x \in \Theta_{i}</tex>. Тогда сумма весов орбит равна <tex>|A| \sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x} \omega(x)</tex>.
| |
| − | |proof=
| |
| − | Уже упоминалось о том, что порядок <tex>|A|</tex> группы <tex>A</tex> равен <tex>|A(x)| \cdot |\Theta(x)|</tex> для любого <tex>x \in X</tex>, где <tex>A(x)</tex> {{---}} стабилизатор элемента <tex>x</tex>. Так как весовая функция постоянна на элементах данной орбиты, то справедливо равенство <tex>|\Theta_{i}| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}\omega(x)</tex> для каждой орбиты <tex>\Theta_{i}</tex>. Домножив второе равенство на первое и сократив, получаем <tex>|A| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>. Суммируя по всем орбитам, находим <tex>|A|\sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{i=1}^n \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>, откуда непосредственно следует доказываемое соотношение.
| |
| − | }}
| |
| − | | |
| − | Как следствие из этой теоремы выведем традиционную формулу Бернсайда. Для подстановки <tex>\alpha</tex> через <tex>j_{k}(\alpha)</tex> обозначим число циклов длины <tex>k</tex> в её разложении в произведение непересекающихся циклов.
| |
| − | | |
| − | {{Лемма
| |
| − | |author=Бернсайд
| |
| − | |statement=
| |
| − | Число <tex>N(A)</tex> орбит группы подстановок <tex>A</tex> равно <tex>N(A) = \frac{1}{|A|}\sum\limits_{\alpha \in A}j_{1}(\alpha)</tex>.
| |
| − | |proof=
| |
| − | Так как в доказательстве этой леммы мы не учитываем значения весовой функции, то <tex>|A|N(A) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x}1</tex>, но <tex>\sum\limits_{x = \alpha x}1</tex> и есть <tex>j_{1}(\alpha)</tex>, то есть для получения исходной формулы нужно поделить обе части равенства на <tex>|A|</tex>.
| |
| − | }}
| |
| − | | |
| − | = Теорема Гуйя-Ури =
| |
| − | | |
| − | {{Определение
| |
| − | |definition=
| |
| − | Ориентированный сильно связный граф называется '''орсвязаными'''.}}
| |
| − | == Лемма о длине цикла в ориентированном графе ==
| |
| − | {{Лемма
| |
| − | |about=о длине цикла в ориентированном графе
| |
| − | |statement= Пусть <tex>G</tex> {{---}} произвольный ориентированный граф и для каждой вершины <tex>v \in V(G)</tex> выполняется <tex>deg^{out}(v) \geqslant \delta</tex>. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует простой цикл <tex>C</tex> длины хотя бы <tex>\delta + 1</tex>.
| |
| − | |proof=
| |
| − | Рассмотрим путь максимальной длины <tex>P = v_0 v_1 \dots v_s</tex>. Из последней вершины <tex>v_s</tex> выходит хотя бы <tex>\delta - 1</tex> ребро в вершины, отличные от <tex>v_{s - 1}</tex>. Так как путь <tex>P</tex> максимальный, то продлить его нельзя, а значит, что из <tex>v_s</tex> выходят ребра только в вершины, содержащиеся в пути <tex>P</tex>. Пусть <tex>v_m \in P</tex> {{---}} вершина с наименьшим номером, в которую входит ребро из <tex>v_s</tex>. Тогда во множество <tex>\{v_m \dots v_{s - 1}\}</tex> входят не менее <tex>\delta</tex> ребер, выходящих из <tex>v_s</tex>. То есть в это множестве хотя бы <tex>\delta</tex> вершин. Значит, в цикле <tex>v_m \dots v_{s - 1} v_s</tex> не менее <tex>\delta + 1</tex> вершины.
| |
| − | }}
| |
| − | | |
| − | == Теорема Гуйя-Ури ==
| |
| − | {{Теорема
| |
| − | |author=Гуйя-Ури, Ghouila-Houri
| |
| − | |statement=
| |
| − | Если <tex>G</tex> {{---}} сильно связный ориентированный граф c <tex>n</tex> вершинами и для каждой <tex>v \in V(G)</tex> выполняется <br>
| |
| − | <tex>
| |
| − | \Bigg\{
| |
| − | \begin{matrix}
| |
| − | deg^{in}(v) \geqslant n/2 \\
| |
| − | deg^{out}(v) \geqslant n/2 \\
| |
| − | | |
| − | \end{matrix}
| |
| − | </tex>, <br>
| |
| − | тогда <tex>G</tex> {{---}} гамильтонов.
| |
| − | |proof=
| |
| − | Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <tex>n = 2</tex> и <tex>n = 3</tex>. Тогда существует орсвязный граф <tex>G</tex> с <tex>n \geqslant 4</tex>, который удовлетворяет условию и при этом не является гамильтоновым. Пусть <tex>C</tex> {{---}} максимальный цикл в <tex>G</tex> длины <tex>k</tex>. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение <tex>1 + n/2 \leqslant k < n</tex>. Теперь рассмотрим <tex>P = v_0 \dots v_l</tex> {{---}} путь максимальной длины <tex>l \geqslant 0</tex> в <tex>G</tex> такой, что никакая вершина этого пути не принадлежит циклу <tex>C</tex>. Тогда <tex>k + l + 1 \leqslant n</tex>. Следовательно, <tex>l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2</tex>. Таким образом, <tex>l \leqslant n/2 - 2</tex>. Это значит, что в вершину <tex>v_0</tex> входят как минимум два ребра, выходящие из вершин, лежащих на <tex>C</tex>, а из вершины <tex>v_l</tex> выходят как минимум два ребра, которые входят в вершины, принадлежащие <tex>C</tex> (так как если бы эти вершины не лежали на данном цикле, путь <tex>P</tex> можно было бы продлить). <br>
| |
| − | Пусть <tex>A</tex> {{---}} множество вершин, принадлежащих <tex>C</tex>, ребра из которых приходят в вершину <tex>v_0</tex>, а <tex>a</tex> {{---}} их количество. Тогда <tex>a \geqslant 2</tex>. Для каждой такой вершины следующая за ней в цикле <tex>C</tex> <tex>l + 1</tex> вершина не содержит входящих ребер, начало которых принадлежит <tex>v_l</tex>, иначе граф <tex>G</tex> содержал бы цикл длины <tex>> k</tex>. Заметим, что среди вершин множества <tex>A</tex> должна существовать такая вершина <tex>y</tex>, что следующая за ней <tex>l + 1</tex> вершина в цикле <tex>C</tex> не является ни отцом <tex>v_0</tex>, ни сыном <tex>v_l</tex>. <br>
| |
| − | Рассмотрим оставшуюся <tex>a - 1</tex> вершину множества <tex>A</tex>, отличную от <tex>y</tex>. В следующую за каждой из них, очевидно, не может приходить ребро из <tex>v_l</tex>. Следовательно, как минимум <tex>(a - 1) + (l + 1) = a + l</tex> вершин <tex>C</tex> не являются сыновьями <tex>v_l</tex>, в противном случае, опять же, граф содержал бы цикл длины <tex>> k</tex>. <br>
| |
| − | Так как <tex>P</tex> {{---}} самый длинный путь в <tex>G</tex>, ни одна вершина которого не принадлежит <tex>C</tex>, каждая вершина, ребро из которой приходит в <tex>v_0</tex>, лежит либо на <tex>P</tex>, либо на <tex>C</tex>. Так как <tex>deg^{in}(v_0) \geqslant n/2</tex>, то <tex>a + l \geqslant n/2</tex>, следовательно <tex>deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1</tex>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
| |
| − | }}
| |
