Викиконспекты - Вклад участника [ru]

Лемма Бёрнсайда и Теорема Пойа

2019-12-25T20:32:44Z

176.59.11.230: /* Задача о числе раскрасок граней куба */

Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести
с помощью Леммы Бернсайда.

{{Определение
|definition=
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>,
для которого <tex>gx=x</tex>.
}}

{{Определение
|definition=
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.
}}

{{Определение
|definition=
Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Будем называть два элемента <tex>x</tex> и <tex>y</tex> эквивалентными, если <tex>x = gy</tex> для некоторого <tex>g \in G</tex>. Классы эквивалентности данного отношения называются '''орбитами''', множество орбит обозначается как <tex>X/G</tex>.
}}

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

{{Лемма
|id=lemmaBerns.
|author=Бернсайд, '''англ.''' Burnside's lemma
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>. <math>|X/G| = \dfrac{1} {|G|}\sum\limits_{g \in G}|St(g)|</math>.
|proof=
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <math>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</math>.

Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:
<math>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</math>

Введем обозначение <tex>C=X/G</tex>.

Рассмотрим правую часть равенства:
<math>|\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| = \sum\limits_{x \in X}</math><math> \dfrac{|G|}{|Gx|} = |G| \sum\limits_{x \in X}\dfrac{1}{|Gx|} </math>
<math>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</math><math> \dfrac{1}{|P|}</math>

Заметим, что <math>\sum\limits_{x\in P} \dfrac{1}{|P|} \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.</math> Следовательно:

<math>|G|\sum\limits_{P\in C}\sum\limits_{x\in P} \dfrac{1}{|P|} = |G|\sum\limits_{P\in C} 1</math>.

Очевидно, что <math>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</math> Тогда получим:

<math>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</math>

Откуда следует, что

<math>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</math>

}}

== Теорема Пойа ==

Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.

{{Теорема
|id=teorPo.
|author=Пойа, '''англ.''' Pólya enumeration theorem
|statement= <math>C = \dfrac{1}{|G|}\sum\limits_{g \in G} l^{P(g)}</math> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.
|proof=Для доказательства этой теоремы достаточно установить следующее равенство
<math>|St(g)| = l^{P(g)}</math>

Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:
<math>|St(g)| = l^{P(g)}</math>
}}

==Задача о числе раскрасок прямоугольника==
{{Задача
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
}}
Решим данную задачу, воспользуясь леммой Бёрнсайда.

'''Решение'''

Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.

Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <tex>\alpha</tex> и <tex>\beta</tex> не были включены в <tex>G</tex>. Это объясняется довольно просто: очевидно то, что операции коммутативны, то есть <tex>\alpha \circ \beta = \beta \circ \alpha</tex>, а также то, что <tex>\alpha \circ \alpha = \beta \circ \beta = e</tex>, тогда любая комбинация данных функций может быть упрощена до вышеперечисленных (в <tex>G</tex>) путем совмещения одинаковых и замены их на <tex>e</tex>.

Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.
:3. С точностью до операции <tex>\alpha \circ \beta</tex> при нечетных <tex>n</tex> и <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n-1]</tex> в <tex>k</tex> цветов (а также частные случаи, когда <tex>n</tex> или <tex>m</tex> нечетные).
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.

Количество неподвижных точек в случае с действием <tex>e</tex> равно <tex>k^{nm}</tex>, так как ни одна раскрашенная клетка не повторилась при действии нулевого действия. Для действий <tex>\alpha</tex> и <tex>\beta</tex> количество раскрасок будет <tex>k^{\lceil \dfrac{m}{2} \rceil n}</tex> и <tex>k^{{\lceil {\dfrac{n}{2}} \rceil}m}</tex> соответственно, для их композиции количество раскрасок <tex>k^{{\lceil {\dfrac{nm}{2}} \rceil}}</tex>, так как верхняя левая четверть прямоугольника однозначно задаёт правую нижнюю, аналогично с правой верхней.

Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.

:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \dfrac{I_1 + I_2 + I_3 + I_4}{4} = \dfrac{k^{nm}+k^{\lceil \dfrac{m}{2} \rceil n} + k^{{\lceil {\dfrac{n}{2}} \rceil}m} + k^{{\lceil {\dfrac{nm}{2}} \rceil}}}{4}</tex>

==Задача о числе раскрасок граней куба==
{{Задача
|definition=Выведите формулу для числа раскрасок граней куба в <tex>k</tex> цветов с точностью до поворота.
}}
Как и в предыдущей задаче, будем использовать в решении лемму Бёрнсайда.

'''Решение'''

Рассмотрим группу вращений куба <tex>G</tex>:

''Последующие изображения с развертками будут подразумевать такое же соответствие вершин, как на рисунке ниже. На развертках будем показывать раскраски, а на самом кубе ребро, через которое мы будем вращать его. Цвета на развертке лишь показывают то, что грани с одинаковым цветом должны быть одинаково раскрашены.''
[[Файл:burnside-intro.png|top]]
* <tex>1</tex> Тождественное вращение. Поскольку ничего не происходит, мы можем покрасить каждую грань в любой цвет <tex>\Rightarrow k^6 </tex> раскрасок.
[[Файл:burnside-1.png|top]]
* <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> и <tex>4</tex> вращения на угол <tex>240^{\circ}</tex> вдоль главных диагоналей куба (вращений четыре, поскольку главных диагоналей <tex>4</tex> шт.). При вращении, если одна грань переходит в другую, мы должны покрасить их в один цвет. Такие раскраски будут являться стабилизатором данного вращения. Из рисунка видно, что мы можем покрасить наш куб в <tex>k^2</tex> цветов (в <tex>k</tex> цветов одни три грани и в <tex>k</tex> цветов другие три грани).
[[Файл:burnside-2.png|top]]
* <tex>6</tex> вращений на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих середины противоположных ребер <tex>\Rightarrow k^3 </tex> раскрасок.
[[Файл:burnside-3.png|top]]
* <tex>3</tex> вращения на угол <tex>90^{\circ}</tex> и <tex>3</tex> вращения на угол <tex>270^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней <tex>\Rightarrow k^3 </tex> раскрасок.
[[Файл:burnside-4.png|top]]
* <tex>3</tex> вращения на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней <tex>\Rightarrow k^4 </tex> раскрасок.
[[Файл:burnside-5.png|top]]

Итого <tex>1+(4+4)+6+(3+3)+3=24</tex> поворота, при которых куб переходит в себя. Других различных поворотов, которые переводят куб в себя, не существует, поскольку ''группа вращений'' [https://en.wikipedia.org/wiki/Octahedral_symmetry <tex>G</tex> изоморфна ''симметрической группе'' <tex>S_4</tex>], тогда из того, что <tex>|S_4|=24</tex> следует, что мы указали все преобразования, которые переводят куб в себя, причем различным образом.

Теперь с помощью Леммы Бёрнсайда найдем искомый ответ:

:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \dfrac{1} {24} (k^6 + 8k^2 + 6k^3 + 6k^3 + 3k^4) = \dfrac{1} {24} (k^6 + 3k^4 + 12k^3 + 8k^2)</tex>

==См. также==
* [[Теорема Кэли|Теорема Кэли]]
* [[Задача об ожерельях|Задача об ожерельях]]

==Источники информации==
*[http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%91%D1%91%D1%80%D0%BD%D1%81%D0%B0%D0%B9%D0%B4%D0%B0 Википедия {{---}} Лемма Бёрнсайда]
*[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0 Википедия {{---}} Теорема Пойа]
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Теория групп]]

Обсуждение:Лемма Бёрнсайда и Теорема Пойа

2019-12-25T20:31:26Z

176.59.11.230: /* Задача о числе раскрасок граней куба */

Теория графов

2019-12-25T20:28:36Z

176.59.11.230: /* Раскраски графов */

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]<tex>^\star</tex>
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
* [[Двудольные графы]]
* [[Дополнительный, самодополнительный граф]]
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
* [[Рёберное ядро]]
* [[Факторизация графов]]<tex>^\star</tex>
* [[Группы графов]]<tex>^\star</tex>
* [[Гиперграфы]]<tex>^\star</tex>
* [[Алгебра графов]]<tex>^\star</tex>
* [[Барицентр дерева]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
* [[Задача о динамической связности]]

== Остовные деревья ==
=== Построение остовных деревьев ===
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]
* [[Минимально узкое остовное дерево]]
* [[Остовное дерево в планарном графе]]
* [[Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами]]

=== Свойства остовных деревьев ===
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом]]
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие рёбер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Графы де Брюина]]
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>

=== Гамильтоновы графы ===
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Теорема Поша]]<tex>^\star</tex>
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
* [[Теорема Гринберга]]<tex>^\star</tex>
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Теорема Вагнера]]
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
* [[Двойственный граф планарного графа]]
* [[Теорема Фари]]<tex>^\star</tex>
* [[Гамма-алгоритм]]
* [[Разрез в планарных графах]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Хроматическое число планарного графа]]
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Проблема четырех красок]]<tex>^\star</tex>
* [[Многочлен Татта]]<tex>^\star</tex>
* [[Теория Рамсея]]<tex>^\star</tex>
* [[Рёберная раскраска двудольного графа]]
* [[Теорема Турана об экстремальном графе]]
* [[Гипотеза Хивуда]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Левита]]<tex>^\star</tex>
* [[Алгоритм A*]] <tex>^\star</tex>
* [[Алгоритм D*]] <tex>^\star</tex>
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>

== Задача о паросочетании ==
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Рёберное ядро]]<tex>^\star</tex>
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Теорема Татта о существовании полного паросочетания]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
* [[Лапы и минимальные по включению барьеры в графе]]
* [[Пересечение всех максимальных по включению барьеров]]
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Сложение и разность потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
* [[Примеры сведения к задачам поиска потока]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>

== Случайные графы ==
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория графов]]

Заглавная страница

2019-12-25T20:26:10Z

176.59.11.230: /* Теория графов */

Добро пожаловать на сайт [[Вики-конспекты|вики-конспектов]]!

= Проверяемые конспекты =

== [[Дискретная математика | Дискретная математика]]==
* [[Дискретная математика#Отношения| Отношения]]
* [[Дискретная математика#Булевы функции| Булевы функции]]
* [[Дискретная математика#Схемы из функциональных элементов| Схемы из функциональных элементов]]
* [[Дискретная математика#Представление информации| Представление информации]]
* [[Дискретная математика#Алгоритмы сжатия| Алгоритмы сжатия данных]]
* [[Дискретная математика#Комбинаторика| Комбинаторика]]
* [[Дискретная математика#Производящая функция|Производящая функция]]

==[[Теория вероятностей | Теория вероятностей]]==
* [[Теория вероятностей # Теория вероятностей| Базовые определения и формулы расчета вероятности]]
* [[Теория вероятностей #Марковские цепи| Марковские цепи]]

==[[Теория формальных языков|Теория формальных языков]]==
* [[Теория формальных языков#Автоматы и регулярные языки|Автоматы и регулярные языки]]
* [[Теория формальных языков#Контекстно-свободные грамматики|Контекстно-свободные грамматики]]

== [[Теория матроидов | Теория матроидов]]==

* [[Теория матроидов#Основные факты теории матроидов | Основные факты]]
* [[Теория матроидов#Пересечение матроидов | Пересечение матроидов]]
* [[Теория матроидов#Объединение матроидов | Объединение матроидов]]

== [[Теория расписаний | Теория расписаний]]==

*[[Теория расписаний#Задачи с одним станком | Задачи с одним станком]]
*[[Теория расписаний#Специальные случаи задач для двух станков | Специальные случаи задач для двух станков]]
*[[Теория расписаний#Задачи для произвольного числа станков | Задачи для произвольного числа станков]]

== [[Теория вычислимости | Теория вычислимости]]==
* [[Теория вычислимости#Разрешимые и перечислимые языки | Разрешимые и перечислимые языки]]
* [[Теория вычислимости#Вычислительные формализмы | Вычислительные формализмы]]
* [[Теория вычислимости#Примеры неразрешимых задач | Примеры неразрешимых задач]]

==[[Теория сложности | Теория сложности]]==
* [[Теория сложности#Детерминированные и недетерминированные вычисления, сложность по времени и по памяти | Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
* [[Теория сложности#Схемная сложность | Схемная сложность]]
* [[Теория сложности#Вероятностные сложностные классы | Вероятностные сложностные классы]]

== [[Алгоритмы и структуры данных | Алгоритмы и структуры данных]]==
* [[Алгоритмы и структуры данных#Амортизационный анализ | Амортизационный анализ]]
* [[Алгоритмы и структуры данных#Персистентные структуры данных | Персистентные структуры данных]]
* [[Алгоритмы и структуры данных#Приоритетные очереди | Приоритетные очереди]]
* [[Алгоритмы и структуры данных#Система непересекающихся множеств | Система непересекающихся множеств]]
* [[Алгоритмы и структуры данных#Поисковые структуры данных | Поисковые структуры данных]]
* [[Алгоритмы и структуры данных#Запросы на отрезках | Запросы на отрезках]]
* [[Алгоритмы и структуры данных#Дерево Фенвика | Дерево Фенвика]]
* [[Алгоритмы и структуры данных#Задача о наименьшем общем предке | Задача о наименьшем общем предке]]
* [[Алгоритмы и структуры данных#Хеширование | Хеширование]]
* [[Алгоритмы и структуры данных#Сортировки | Сортировки]]
* [[Алгоритмы и структуры данных#Сортирующие сети | Сортирующие сети]]
* [[Алгоритмы и структуры данных#Алгоритмы поиска | Алгоритмы поиска]]
* [[Алгоритмы и структуры данных#Динамическое программирование | Динамическое программирование]]
* [[Алгоритмы и структуры данных#Алгоритмы во внешней памяти | Алгоритмы во внешней памяти]]

== [[Теория графов | Теория графов]]==
* [[Теория графов#Основные определения теории графов | Основные определения теории графов]]
* [[Теория графов#Связность в графах | Связность в графах]]
* [[Теория графов#Остовные деревья | Остовные деревья]]
* [[Теория графов#Обходы графов | Обходы графов]]
* [[Теория графов# Укладки графов | Укладки графов]]
* [[Теория графов#Раскраски графов | Раскраски графов]]
* [[Теория графов#Обход в глубину | Обход в глубину]]
* [[Теория графов#Кратчайшие пути в графах | Кратчайшие пути в графах]]
* [[Теория графов#Задача о паросочетании | Задача о паросочетании]]
* [[Теория графов#Задача о максимальном потоке | Задача о максимальном потоке]]
* [[Теория графов#Задача о потоке минимальной стоимости | Задача о потоке минимальной стоимости]]
* [[Теория графов#Cлучайные графы | Cлучайные графы]]

== [[Алгоритмы на строках | Алгоритмы на строках]]==
* [[Алгоритмы на строках# Поиск подстроки в строке | Поиск подстроки в строке]]
* [[Алгоритмы на строках#Суффиксное дерево |Суффиксное дерево]]
* [[Алгоритмы на строках#Суффиксный массив | Суффиксный массив]]

== [[Методы трансляции | Методы трансляции]] ==
* [[Методы трансляции#Нисходящий разбор|Нисходящий разбор]]
* [[Методы трансляции#Восходящий разбор | Восходящий разбор]]

== [[Вычислительная геометрия|Вычислительная геометрия ]]==
* [[Вычислительная геометрия#Основание вычислительной геометрии|Основание вычислительной геометрии]]
* [[Вычислительная геометрия#Вычисление геометрических предикатов|Вычисление геометрических предикатов]]
* [[Вычислительная геометрия#Пересечение отрезков|Пересечение отрезков]]
* [[Вычислительная геометрия#Выпуклые оболочки|Выпуклые оболочки]]
* [[Вычислительная геометрия#Поиск|Поиск]]
* [[Вычислительная геометрия#Триангуляция|Триангуляция]]
* [[Вычислительная геометрия#ППЛГ и РСДС|ППЛГ и РСДС]]
* [[Вычислительная геометрия#Алгоритмы локализации|Алгоритмы локализации]]
* [[Вычислительная геометрия#Триангуляция Делоне и диаграмма Вороного|Триангуляция Делоне и диаграмма Вороного]]
* [[Вычислительная геометрия#Планирование движения (Motion planning)|Планирование движения (Motion planning)]]

== [[Язык программирования Java|Язык программирования Java]]==
*[[Основная информация о языкe]]
*[[Программирование по контракту]]
*[[Обработка ошибок и исключения]]
*[[Generics]]
*[[Перечисления]]

== [[Параллельное программирование|Параллельное программирование]]==
*[[Очередь Майкла и Скотта]]

== [[Машинное обучение|Машинное обучение]]==

*[[Модель алгоритма и ее выбор]]
*[[Переобучение]]
*[[Кросс-валидация]]
*[[Выброс]]
*[[Машинное обучение|Другие темы]]

= Непроверяемые конспекты =

*[[Алгебра и геометрия 1 курс | Алгебра и геометрия — 1, 2 семестр]]
*[[Математический анализ 1 курс | Математический анализ — 1, 2 семестр]]
*[[Математический анализ 2 курс | Математический анализ — 3, 4 семестр]]
*[[Математическая логика|Математическая логика — 3 семестр]]
*[[Участник:Qwerty787788/плюсы3сем | С++ — 2, 3 семестр]]
*[[Дифференциальные уравнения | Дифференциальные уравнения — 3 семестр]]
*[[Assembler|Assembler — 4 семестр]]
*[[Алгоритмы алгебры и теории чисел|Алгоритмы алгебры и теории чисел — 4 семестр]]
*[[Функциональный_анализ_3_курс | Функциональный анализ — 5, 6 семестр]]
*[[Параллельное программирование|Параллельное программирование — 6 семестр]]
*[[Базы данных|Базы данных — 7 семестр]]
*[[Компьютерные сети|Компьютерные сети — 7, 8 семестр]]
*[[Эволюционные алгоритмы|Эволюционные алгоритмы — 10 семестр]]

[[Категория:Всё]]

Теория графов

2019-12-25T20:25:29Z

176.59.11.230:

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]<tex>^\star</tex>
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
* [[Двудольные графы]]
* [[Дополнительный, самодополнительный граф]]
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
* [[Рёберное ядро]]
* [[Факторизация графов]]<tex>^\star</tex>
* [[Группы графов]]<tex>^\star</tex>
* [[Гиперграфы]]<tex>^\star</tex>
* [[Алгебра графов]]<tex>^\star</tex>
* [[Барицентр дерева]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
* [[Задача о динамической связности]]

== Остовные деревья ==
=== Построение остовных деревьев ===
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]
* [[Минимально узкое остовное дерево]]
* [[Остовное дерево в планарном графе]]
* [[Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами]]

=== Свойства остовных деревьев ===
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом]]
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие рёбер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Графы де Брюина]]
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>

=== Гамильтоновы графы ===
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Теорема Поша]]<tex>^\star</tex>
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
* [[Теорема Гринберга]]<tex>^\star</tex>
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Теорема Вагнера]]
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
* [[Двойственный граф планарного графа]]
* [[Теорема Фари]]<tex>^\star</tex>
* [[Гамма-алгоритм]]
* [[Разрез в планарных графах]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Хроматическое число планарного графа]]
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Проблема четырех красок]]<tex>^\star</tex>
* [[Многочлен Татта]]<tex>^\star</tex>
* [[Теория Рамсея]]<tex>^\star</tex>
* [[Рёберная раскраска двудольного графа]]
* [[Теорема Турана об экстремальном графе]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Левита]]<tex>^\star</tex>
* [[Алгоритм A*]] <tex>^\star</tex>
* [[Алгоритм D*]] <tex>^\star</tex>
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>

== Задача о паросочетании ==
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Рёберное ядро]]<tex>^\star</tex>
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Теорема Татта о существовании полного паросочетания]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
* [[Лапы и минимальные по включению барьеры в графе]]
* [[Пересечение всех максимальных по включению барьеров]]
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
* [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Сложение и разность потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
* [[Примеры сведения к задачам поиска потока]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>

== Случайные графы ==
* [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория графов]]

Заглавная страница

2019-12-25T20:23:22Z

176.59.11.230: /* Теория графов */

Добро пожаловать на сайт [[Вики-конспекты|вики-конспектов]]!

= Проверяемые конспекты =

== [[Дискретная математика | Дискретная математика]]==
* [[Дискретная математика#Отношения| Отношения]]
* [[Дискретная математика#Булевы функции| Булевы функции]]
* [[Дискретная математика#Схемы из функциональных элементов| Схемы из функциональных элементов]]
* [[Дискретная математика#Представление информации| Представление информации]]
* [[Дискретная математика#Алгоритмы сжатия| Алгоритмы сжатия данных]]
* [[Дискретная математика#Комбинаторика| Комбинаторика]]
* [[Дискретная математика#Производящая функция|Производящая функция]]

==[[Теория вероятностей | Теория вероятностей]]==
* [[Теория вероятностей # Теория вероятностей| Базовые определения и формулы расчета вероятности]]
* [[Теория вероятностей #Марковские цепи| Марковские цепи]]

==[[Теория формальных языков|Теория формальных языков]]==
* [[Теория формальных языков#Автоматы и регулярные языки|Автоматы и регулярные языки]]
* [[Теория формальных языков#Контекстно-свободные грамматики|Контекстно-свободные грамматики]]

== [[Теория матроидов | Теория матроидов]]==

* [[Теория матроидов#Основные факты теории матроидов | Основные факты]]
* [[Теория матроидов#Пересечение матроидов | Пересечение матроидов]]
* [[Теория матроидов#Объединение матроидов | Объединение матроидов]]

== [[Теория расписаний | Теория расписаний]]==

*[[Теория расписаний#Задачи с одним станком | Задачи с одним станком]]
*[[Теория расписаний#Специальные случаи задач для двух станков | Специальные случаи задач для двух станков]]
*[[Теория расписаний#Задачи для произвольного числа станков | Задачи для произвольного числа станков]]

== [[Теория вычислимости | Теория вычислимости]]==
* [[Теория вычислимости#Разрешимые и перечислимые языки | Разрешимые и перечислимые языки]]
* [[Теория вычислимости#Вычислительные формализмы | Вычислительные формализмы]]
* [[Теория вычислимости#Примеры неразрешимых задач | Примеры неразрешимых задач]]

==[[Теория сложности | Теория сложности]]==
* [[Теория сложности#Детерминированные и недетерминированные вычисления, сложность по времени и по памяти | Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
* [[Теория сложности#Схемная сложность | Схемная сложность]]
* [[Теория сложности#Вероятностные сложностные классы | Вероятностные сложностные классы]]

== [[Алгоритмы и структуры данных | Алгоритмы и структуры данных]]==
* [[Алгоритмы и структуры данных#Амортизационный анализ | Амортизационный анализ]]
* [[Алгоритмы и структуры данных#Персистентные структуры данных | Персистентные структуры данных]]
* [[Алгоритмы и структуры данных#Приоритетные очереди | Приоритетные очереди]]
* [[Алгоритмы и структуры данных#Система непересекающихся множеств | Система непересекающихся множеств]]
* [[Алгоритмы и структуры данных#Поисковые структуры данных | Поисковые структуры данных]]
* [[Алгоритмы и структуры данных#Запросы на отрезках | Запросы на отрезках]]
* [[Алгоритмы и структуры данных#Дерево Фенвика | Дерево Фенвика]]
* [[Алгоритмы и структуры данных#Задача о наименьшем общем предке | Задача о наименьшем общем предке]]
* [[Алгоритмы и структуры данных#Хеширование | Хеширование]]
* [[Алгоритмы и структуры данных#Сортировки | Сортировки]]
* [[Алгоритмы и структуры данных#Сортирующие сети | Сортирующие сети]]
* [[Алгоритмы и структуры данных#Алгоритмы поиска | Алгоритмы поиска]]
* [[Алгоритмы и структуры данных#Динамическое программирование | Динамическое программирование]]
* [[Алгоритмы и структуры данных#Алгоритмы во внешней памяти | Алгоритмы во внешней памяти]]

== [[Теория графов | Теория графов]]==
* [[Теория графов#Основные определения теории графов | Основные определения теории графов]]
* [[Теория графов#Связность в графах | Связность в графах]]
* [[Теория графов#Остовные деревья | Остовные деревья]]
* [[Теория графов#Обходы графов | Обходы графов]]
* [[Теория графов# Укладки графов | Укладки графов]]
* [[Теория графов#Раскраски графов | Раскраски графов]]
* [[Теория графов#Обход в глубину | Обход в глубину]]
* [[Теория графов#Кратчайшие пути в графах | Кратчайшие пути в графах]]
* [[Теория графов#Задача о паросочетании | Задача о паросочетании]]
* [[Теория графов#Задача о максимальном потоке | Задача о максимальном потоке]]
* [[Теория графов#Задача о потоке минимальной стоимости | Задача о потоке минимальной стоимости]]
* [[Теория графов#Cлучайные графы]]

== [[Алгоритмы на строках | Алгоритмы на строках]]==
* [[Алгоритмы на строках# Поиск подстроки в строке | Поиск подстроки в строке]]
* [[Алгоритмы на строках#Суффиксное дерево |Суффиксное дерево]]
* [[Алгоритмы на строках#Суффиксный массив | Суффиксный массив]]

== [[Методы трансляции | Методы трансляции]] ==
* [[Методы трансляции#Нисходящий разбор|Нисходящий разбор]]
* [[Методы трансляции#Восходящий разбор | Восходящий разбор]]

== [[Вычислительная геометрия|Вычислительная геометрия ]]==
* [[Вычислительная геометрия#Основание вычислительной геометрии|Основание вычислительной геометрии]]
* [[Вычислительная геометрия#Вычисление геометрических предикатов|Вычисление геометрических предикатов]]
* [[Вычислительная геометрия#Пересечение отрезков|Пересечение отрезков]]
* [[Вычислительная геометрия#Выпуклые оболочки|Выпуклые оболочки]]
* [[Вычислительная геометрия#Поиск|Поиск]]
* [[Вычислительная геометрия#Триангуляция|Триангуляция]]
* [[Вычислительная геометрия#ППЛГ и РСДС|ППЛГ и РСДС]]
* [[Вычислительная геометрия#Алгоритмы локализации|Алгоритмы локализации]]
* [[Вычислительная геометрия#Триангуляция Делоне и диаграмма Вороного|Триангуляция Делоне и диаграмма Вороного]]
* [[Вычислительная геометрия#Планирование движения (Motion planning)|Планирование движения (Motion planning)]]

== [[Язык программирования Java|Язык программирования Java]]==
*[[Основная информация о языкe]]
*[[Программирование по контракту]]
*[[Обработка ошибок и исключения]]
*[[Generics]]
*[[Перечисления]]

== [[Параллельное программирование|Параллельное программирование]]==
*[[Очередь Майкла и Скотта]]

== [[Машинное обучение|Машинное обучение]]==

*[[Модель алгоритма и ее выбор]]
*[[Переобучение]]
*[[Кросс-валидация]]
*[[Выброс]]
*[[Машинное обучение|Другие темы]]

= Непроверяемые конспекты =

*[[Алгебра и геометрия 1 курс | Алгебра и геометрия — 1, 2 семестр]]
*[[Математический анализ 1 курс | Математический анализ — 1, 2 семестр]]
*[[Математический анализ 2 курс | Математический анализ — 3, 4 семестр]]
*[[Математическая логика|Математическая логика — 3 семестр]]
*[[Участник:Qwerty787788/плюсы3сем | С++ — 2, 3 семестр]]
*[[Дифференциальные уравнения | Дифференциальные уравнения — 3 семестр]]
*[[Assembler|Assembler — 4 семестр]]
*[[Алгоритмы алгебры и теории чисел|Алгоритмы алгебры и теории чисел — 4 семестр]]
*[[Функциональный_анализ_3_курс | Функциональный анализ — 5, 6 семестр]]
*[[Параллельное программирование|Параллельное программирование — 6 семестр]]
*[[Базы данных|Базы данных — 7 семестр]]
*[[Компьютерные сети|Компьютерные сети — 7, 8 семестр]]
*[[Эволюционные алгоритмы|Эволюционные алгоритмы — 10 семестр]]

[[Категория:Всё]]