Обсуждение участницы:Анна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Гуйя-Ури)
(Лемма о длине цикла в ориентированном графе)
Строка 76: Строка 76:
 
{{Лемма
 
{{Лемма
 
|about=о длине цикла в ориентированном графе
 
|about=о длине цикла в ориентированном графе
|statement= Пусть <tex>G</tex> {{---}} произвольный [[Основные определения теории графов#def_undirected_graph_1|ориентированный граф]] и для каждой вершины <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>.
+
|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=
 
|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> вершины.
 
Рассмотрим путь максимальной длины <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> вершины.

Версия 12:29, 31 декабря 2015

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

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

Определение:
Помеченный граф с [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]\triangleleft[/math]