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

Алгоритмы на строках:Тикеты

2018-01-25T15:43:52Z

5.18.205.24: /* 3 Суффиксное дерево */

'''Взяли все'''
== 1 Основные определения. Простые комбинаторные свойства слов ==

# [[Основные определения, связанные со строками]]
# [[Период и бордер, их связь]]
# [[Слово Фибоначчи]]
# [[Слово Туэ-Морса]]
# '''взяли''' [[Декомпозиция Линдона]]<tex>^\star</tex> 0,5
## заменить <tex>..</tex> на <tex>\ldots</tex>
## см. также
# [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
# [[Алгоритм Крочемора]]<tex>^\star</tex>
# [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
# '''взяли''' [[Алгоритм Манакера]]<tex>^\star</tex>0.5
## заменить <tex>..</tex> на <tex>\ldots</tex>
## <tex>d1</tex> заменить на <tex>d_1</tex>
# [[Дерево палиндромов]]<tex>^\star</tex>

== 2 Поиск подстроки в строке ==
0 [[Поиск подстроки в строке]] 0.25
## См. также
=== 1 Точный поиск ===
# [[Наивный алгоритм поиска подстроки в строке]] 0,25
## См. также
# [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Префикс-функция]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Кнута-Морриса-Пратта]]
# [[Автомат Кнута-Морриса-Пратта]]
# [[Z-функция]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Бор]]
# [[Алгоритм Ахо-Корасик]]
# [[Суффиксный автомат]]
# [[Алгоритм Бойера-Мура]] 0,25
## См. также
# [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex>
# [[Алгоритм Колусси]]<tex>^\star</tex> 0,25
## См. также
# [[Алгоритм Райта]]<tex>^\star</tex>
# [[Алгоритм Shift-And]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Двусторонний алгоритм]]<tex>^\star</tex>
# [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex>

=== 2 Нечёткий поиск ===
# [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>

== 3 Суффиксное дерево ==
# [[Суффиксный бор]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
## Trie -> Tree
# [[Сжатое суффиксное дерево]]
# [[Алгоритм Укконена]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм МакКрейта]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Фарача]]<tex>^\star</tex>

== 4 Суффиксный массив ==
# [[Суффиксный массив]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# '''взяли'''[[Построение суффиксного массива с помощью стандартных методов сортировки]] 2
## <tex>..</tex> заменить на <tex>\ldots</tex>
## разобраться с псевдокодом
# '''взяли''' [[Алгоритм цифровой сортировки суффиксов циклической строки]] 2
## <tex>..</tex> заменить на <tex>\ldots</tex>
## в картинки с примером есть ошибка
# [[Алгоритм Касаи и др.]]
# [[Алгоритм Карккайнена-Сандерса]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
# [[Количество подпалиндромов в строке]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>

Теорема Турана об экстремальном графе

2018-01-01T16:06:17Z

5.18.205.24:

==Теорема Турана==
[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]
'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов<ref>[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]</ref>.
Она послужила образцом для большого количества подобных теорем, которые изучают, как наличие тех или иных подструктур влияет на некоторые глобальные параметры ([[Раскраска графа|хроматическое число]]).

Впервые теорему сформулировал венгерский математик Пал Туран в <tex>1941</tex> году.

{{Определение
|definition=
<tex>K_n</tex> {{---}} полный граф на <tex>n</tex> вершинах.
}}

{{Определение
|definition=
<tex>ex(n, K_r)</tex> {{---}} максимальное количество ребер, которое может иметь граф на <tex>n</tex> вершинах, не включая в себя <tex>K_r</tex> как подграф.
}}

{{Определение
|definition=
'''Граф Турана''' <tex>T^{r-1}(n)</tex> {{---}} полный <tex>(r - 1)</tex>-[[Двудольные графы|дольный]] граф на <tex>n > r-1</tex> вершинах, доли которого по мощности отличаются не более чем на <tex>1</tex>. Если количество вершин не превосходит количество долей (<tex>n \leqslant r - 1</tex>), то <tex>T^{r-1}(n) = K_n</tex>.
}}

{{Определение
|definition=
<tex>t_{r-1}(n)</tex> {{---}} количество ребер в <tex>T^{r-1}(n)</tex>.
}}

{{Лемма
|statement=
Если <tex>G</tex> {{---}} <tex>(r - 1)</tex>-дольный граф с максимальным количеством ребер, то <tex>G = T^{r-1}(n)</tex>.
|proof=
Докажем от противного. Пусть существует <tex>(r - 1)</tex>-дольный граф с максимальным числом ребер, который не является графом Турана.
Обозначим его <tex>G_m</tex>.
Очевидно, что <tex>G_m</tex> является полным <tex>(r - 1)</tex>-дольным.
Так как <tex>G_m \ne T^{r-1}(n) </tex>, то в <tex>G_m</tex> существуют доли <tex>V_1</tex> и <tex>V_2</tex>, что <tex>|V_1| - |V_2| > 1</tex>.
Но тогда возьмем вершину <tex>a \in V_1</tex> и перекинем ее в <tex>V_2</tex>. Тогда количество вершин, которые не могут быть соседями <tex>a</tex> уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось.
Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер.

Значит лемма доказана.
}}
{{Теорема
|statement=
Для всех натуральных чисел <tex>r</tex>, <tex>n</tex>, где <tex>r > 1</tex>, любой граф <tex>G \nsubseteq K_r</tex> с <tex>n</tex> вершинами и <tex>ex(n, K_r)</tex> ребрами есть <tex>T^{r-1}(n)</tex>.
|proof=
[[Файл:Turan theorem induction step.png|300px|thumb|left|Шаг индукции]]
Применим индукцию по <tex>n</tex>.

'''База:'''

При <tex>n \leqslant r - 1</tex> имеем <tex>G = K_n = T^{r-1}(n)</tex>, что и утверждалось. База доказана.

'''Шаг индукции:'''

Пусть теперь <tex>n \geqslant r</tex>.
Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K_r</tex>, то <tex>G</tex> содержит подграф <tex>K^{r-1}</tex>.
Обозначим любой из них как <tex>K</tex>.
Тогда по индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r-1}(n - r + 1)</tex> ребер, а любая вершина <tex>G - K</tex> имеет не более <tex>r - 2</tex> соседей в <tex>K.</tex>
Следовательно мы можем оценить количество ребер в <tex>G</tex>:

<tex>|E(G)| \leqslant \underbrace{t_{r-1}(n + r - 1)}_{G-K} + \underbrace{(n - r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)</tex>

Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.

Поскольку <tex>G</tex> экстремален для <tex>K_r</tex>, то в <tex>(1)</tex> имеет место равенство.
Таким образом, любая вершина из <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно так же, как и вершины <tex>x_1,\cdots, x_{r-1}</tex> из самого <tex>K</tex>.

При <tex>i = 1,\cdots, r-1</tex> пусть <tex>V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}</tex> есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> отличны от <tex>x_i</tex>.
Так как каждая вершина <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex>, то все <tex>V_i</tex> не зависимы.
При этом они в объединении дают <tex>V(G)</tex> поскольку <tex>K_r \nsubseteq G</tex>.
Следовательно, граф <tex>G</tex> является <tex>(r-1)</tex>-дольным.
Тогда по лемме из предположения об экстремальности <tex>G</tex> следует, что <tex>G = T^{r-1}(n)</tex>.

}}
==См. также==
*[[Раскраска графа]]
*[[Двудольные графы]]
==Примечания==
<references />
==Источники информации==
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]

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

Теорема Турана об экстремальном графе

2018-01-01T16:05:46Z

5.18.205.24:

==Теорема Турана==
[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]
'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов)<ref>[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]</ref>.
Она послужила образцом для большого количества подобных теорем, которые изучают, как наличие тех или иных подструктур влияет на некоторые глобальные параметры ([[Раскраска графа|хроматическое число]]).

Впервые теорему сформулировал венгерский математик Пал Туран в <tex>1941</tex> году.

{{Определение
|definition=
<tex>K_n</tex> {{---}} полный граф на <tex>n</tex> вершинах.
}}

{{Определение
|definition=
<tex>ex(n, K_r)</tex> {{---}} максимальное количество ребер, которое может иметь граф на <tex>n</tex> вершинах, не включая в себя <tex>K_r</tex> как подграф.
}}

{{Определение
|definition=
'''Граф Турана''' <tex>T^{r-1}(n)</tex> {{---}} полный <tex>(r - 1)</tex>-[[Двудольные графы|дольный]] граф на <tex>n > r-1</tex> вершинах, доли которого по мощности отличаются не более чем на <tex>1</tex>. Если количество вершин не превосходит количество долей (<tex>n \leqslant r - 1</tex>), то <tex>T^{r-1}(n) = K_n</tex>.
}}

{{Определение
|definition=
<tex>t_{r-1}(n)</tex> {{---}} количество ребер в <tex>T^{r-1}(n)</tex>.
}}

{{Лемма
|statement=
Если <tex>G</tex> {{---}} <tex>(r - 1)</tex>-дольный граф с максимальным количеством ребер, то <tex>G = T^{r-1}(n)</tex>.
|proof=
Докажем от противного. Пусть существует <tex>(r - 1)</tex>-дольный граф с максимальным числом ребер, который не является графом Турана.
Обозначим его <tex>G_m</tex>.
Очевидно, что <tex>G_m</tex> является полным <tex>(r - 1)</tex>-дольным.
Так как <tex>G_m \ne T^{r-1}(n) </tex>, то в <tex>G_m</tex> существуют доли <tex>V_1</tex> и <tex>V_2</tex>, что <tex>|V_1| - |V_2| > 1</tex>.
Но тогда возьмем вершину <tex>a \in V_1</tex> и перекинем ее в <tex>V_2</tex>. Тогда количество вершин, которые не могут быть соседями <tex>a</tex> уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось.
Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер.

Значит лемма доказана.
}}
{{Теорема
|statement=
Для всех натуральных чисел <tex>r</tex>, <tex>n</tex>, где <tex>r > 1</tex>, любой граф <tex>G \nsubseteq K_r</tex> с <tex>n</tex> вершинами и <tex>ex(n, K_r)</tex> ребрами есть <tex>T^{r-1}(n)</tex>.
|proof=
[[Файл:Turan theorem induction step.png|300px|thumb|left|Шаг индукции]]
Применим индукцию по <tex>n</tex>.

'''База:'''

При <tex>n \leqslant r - 1</tex> имеем <tex>G = K_n = T^{r-1}(n)</tex>, что и утверждалось. База доказана.

'''Шаг индукции:'''

Пусть теперь <tex>n \geqslant r</tex>.
Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K_r</tex>, то <tex>G</tex> содержит подграф <tex>K^{r-1}</tex>.
Обозначим любой из них как <tex>K</tex>.
Тогда по индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r-1}(n - r + 1)</tex> ребер, а любая вершина <tex>G - K</tex> имеет не более <tex>r - 2</tex> соседей в <tex>K.</tex>
Следовательно мы можем оценить количество ребер в <tex>G</tex>:

<tex>|E(G)| \leqslant \underbrace{t_{r-1}(n + r - 1)}_{G-K} + \underbrace{(n - r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)</tex>

Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.

Поскольку <tex>G</tex> экстремален для <tex>K_r</tex>, то в <tex>(1)</tex> имеет место равенство.
Таким образом, любая вершина из <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно так же, как и вершины <tex>x_1,\cdots, x_{r-1}</tex> из самого <tex>K</tex>.

При <tex>i = 1,\cdots, r-1</tex> пусть <tex>V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}</tex> есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> отличны от <tex>x_i</tex>.
Так как каждая вершина <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex>, то все <tex>V_i</tex> не зависимы.
При этом они в объединении дают <tex>V(G)</tex> поскольку <tex>K_r \nsubseteq G</tex>.
Следовательно, граф <tex>G</tex> является <tex>(r-1)</tex>-дольным.
Тогда по лемме из предположения об экстремальности <tex>G</tex> следует, что <tex>G = T^{r-1}(n)</tex>.

}}
==См. также==
*[[Раскраска графа]]
*[[Двудольные графы]]
==Примечания==
<references />
==Источники информации==
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]

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

Теорема Турана об экстремальном графе

2018-01-01T15:56:56Z

5.18.205.24:

==Теорема Турана==
[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]
'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов<ref>https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2</ref>.
Она послужила образцом для большого количества подобных теорем, которые изучают, как наличие тех или иных подструктур влияет на некоторые глобальные параметры ([[Раскраска графа|хроматическое число]]).

Впервые теорему сформулировал венгерский математик Пал Туран в <tex>1941</tex> году.

{{Определение
|definition=
<tex>K_n</tex> {{---}} полный граф на <tex>n</tex> вершинах.
}}

{{Определение
|definition=
<tex>ex(n, K_r)</tex> {{---}} максимальное количество ребер, которое может иметь граф на <tex>n</tex> вершинах, не включая в себя <tex>K_r</tex> как подграф.
}}

{{Определение
|definition=
'''Граф Турана''' <tex>T^{r-1}(n)</tex> {{---}} полный <tex>(r - 1)</tex>-[[Двудольные графы|дольный]] граф на <tex>n > r-1</tex> вершинах, доли которого по мощности отличаются не более чем на <tex>1</tex>. Если количество вершин не превосходит количество долей (<tex>n \leqslant r - 1</tex>), то <tex>T^{r-1}(n) = K_n</tex>.
}}

{{Определение
|definition=
<tex>t_{r-1}(n)</tex> {{---}} количество ребер в <tex>T^{r-1}(n)</tex>.
}}

{{Лемма
|statement=
Если <tex>G</tex> {{---}} <tex>(r - 1)</tex>-дольный граф с максимальным количеством ребер, то <tex>G = T^{r-1}(n)</tex>.
|proof=
Докажем от противного. Пусть существует <tex>(r - 1)</tex>-дольный граф с максимальным числом ребер, который не является графом Турана.
Обозначим его <tex>G_m</tex>.
Очевидно, что <tex>G_m</tex> является полным <tex>(r - 1)</tex>-дольным.
Так как <tex>G_m \ne T^{r-1}(n) </tex>, то в <tex>G_m</tex> существуют доли <tex>V_1</tex> и <tex>V_2</tex>, что <tex>|V_1| - |V_2| > 1</tex>.
Но тогда возьмем вершину <tex>a \in V_1</tex> и перекинем ее в <tex>V_2</tex>. Тогда количество вершин, которые не могут быть соседями <tex>a</tex> уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось.
Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер.

Значит лемма доказана.
}}
{{Теорема
|statement=
Для всех натуральных чисел <tex>r</tex>, <tex>n</tex>, где <tex>r > 1</tex>, любой граф <tex>G \nsubseteq K_r</tex> с <tex>n</tex> вершинами и <tex>ex(n, K_r)</tex> ребрами есть <tex>T^{r-1}(n)</tex>.
|proof=
[[Файл:Turan theorem induction step.png|300px|thumb|left|Шаг индукции]]
Применим индукцию по <tex>n</tex>.

'''База:'''

При <tex>n \leqslant r - 1</tex> имеем <tex>G = K_n = T^{r-1}(n)</tex>, что и утверждалось. База доказана.

'''Шаг индукции:'''

Пусть теперь <tex>n \geqslant r</tex>.
Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K_r</tex>, то <tex>G</tex> содержит подграф <tex>K^{r-1}</tex>.
Обозначим любой из них как <tex>K</tex>.
Тогда по индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r-1}(n - r + 1)</tex> ребер, а любая вершина <tex>G - K</tex> имеет не более <tex>r - 2</tex> соседей в <tex>K.</tex>
Следовательно мы можем оценить количество ребер в <tex>G</tex>:

<tex>|E(G)| \leqslant \underbrace{t_{r-1}(n + r - 1)}_{G-K} + \underbrace{(n - r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)</tex>

Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.

Поскольку <tex>G</tex> экстремален для <tex>K_r</tex>, то в <tex>(1)</tex> имеет место равенство.
Таким образом, любая вершина из <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно так же, как и вершины <tex>x_1,\cdots, x_{r-1}</tex> из самого <tex>K</tex>.

При <tex>i = 1,\cdots, r-1</tex> пусть <tex>V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}</tex> есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> отличны от <tex>x_i</tex>.
Так как каждая вершина <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex>, то все <tex>V_i</tex> не зависимы.
При этом они в объединении дают <tex>V(G)</tex> поскольку <tex>K_r \nsubseteq G</tex>.
Следовательно, граф <tex>G</tex> является <tex>(r-1)</tex>-дольным.
Тогда по лемме из предположения об экстремальности <tex>G</tex> следует, что <tex>G = T^{r-1}(n)</tex>.

}}
==См. также==
*[[Раскраска графа]]
*[[Двудольные графы]]
==Примечания==
<references/>
==Источники информации==
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]

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

Теорема Турана об экстремальном графе

2018-01-01T15:54:25Z

5.18.205.24:

==Теорема Турана==
[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]
'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема
[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 экстремальной теории графов].
Она послужила образцом для большого количества подобных теорем, которые изучают, как наличие тех или иных подструктур влияет на некоторые глобальные параметры([[Раскраска графа| хроматическое число]]).

Впервые теорему сформулировал венгерский математик Пал Туран в <tex>1941</tex> году.

{{Определение
|definition=
<tex>K_n</tex> {{---}} полный граф на <tex>n</tex> вершинах.
}}

{{Определение
|definition=
<tex>ex(n, K_r)</tex> {{---}} максимальное количество ребер, которое может иметь граф на <tex>n</tex> вершинах, не включая в себя <tex>K_r</tex> как подграф.
}}

{{Определение
|definition=
'''Граф Турана''' <tex>T^{r-1}(n)</tex> {{---}} полный <tex>(r - 1)</tex>-[[Двудольные графы|дольный]] граф на <tex>n > r-1</tex> вершинах, доли которого по мощности отличаются не более чем на <tex>1</tex>. Если количество вершин не превосходит количество долей (<tex>n \leqslant r - 1</tex>), то <tex>T^{r-1}(n) = K_n</tex>.
}}

{{Определение
|definition=
<tex>t_{r-1}(n)</tex> {{---}} количество ребер в <tex>T^{r-1}(n)</tex>.
}}

{{Лемма
|statement=
Если <tex>G</tex> {{---}} <tex>(r - 1)</tex>-дольный граф с максимальным количеством ребер, то <tex>G = T^{r-1}(n)</tex>.
|proof=
Докажем от противного. Пусть существует <tex>(r - 1)</tex>-дольный граф с максимальным числом ребер, который не является графом Турана.
Обозначим его <tex>G_m</tex>.
Очевидно, что <tex>G_m</tex> является полным <tex>(r - 1)</tex>-дольным.
Так как <tex>G_m \ne T^{r-1}(n) </tex>, то в <tex>G_m</tex> существуют доли <tex>V_1</tex> и <tex>V_2</tex>, что <tex>|V_1| - |V_2| > 1</tex>.
Но тогда возьмем вершину <tex>a \in V_1</tex> и перекинем ее в <tex>V_2</tex>. Тогда количество вершин, которые не могут быть соседями <tex>a</tex> уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось.
Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер.

Значит лемма доказана.
}}
{{Теорема
|statement=
Для всех натуральных чисел <tex>r</tex>, <tex>n</tex>, где <tex>r > 1</tex>, любой граф <tex>G \nsubseteq K_r</tex> с <tex>n</tex> вершинами и <tex>ex(n, K_r)</tex> ребрами есть <tex>T^{r-1}(n)</tex>.
|proof=
[[Файл:Turan theorem induction step.png|300px|thumb|left|Шаг индукции]]
Применим индукцию по <tex>n</tex>.

'''База:'''

При <tex>n \leqslant r - 1</tex> имеем <tex>G = K_n = T^{r-1}(n)</tex>, что и утверждалось. База доказана.

'''Шаг индукции:'''

Пусть теперь <tex>n \geqslant r</tex>.
Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K_r</tex>, то <tex>G</tex> содержит подграф <tex>K^{r-1}</tex>.
Обозначим любой из них как <tex>K</tex>.
Тогда по индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r-1}(n - r + 1)</tex> ребер, а любая вершина <tex>G - K</tex> имеет не более <tex>r - 2</tex> соседей в <tex>K.</tex>
Следовательно мы можем оценить количество ребер в <tex>G</tex>:

<tex>|E(G)| \leqslant \underbrace{t_{r-1}(n + r - 1)}_{G-K} + \underbrace{(n - r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)</tex>

Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.

Поскольку <tex>G</tex> экстремален для <tex>K_r</tex>, то в <tex>(1)</tex> имеет место равенство.
Таким образом, любая вершина из <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно так же, как и вершины <tex>x_1,\cdots, x_{r-1}</tex> из самого <tex>K</tex>.

При <tex>i = 1,\cdots, r-1</tex> пусть <tex>V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}</tex> есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> отличны от <tex>x_i</tex>.
Так как каждая вершина <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex>, то все <tex>V_i</tex> не зависимы.
При этом они в объединении дают <tex>V(G)</tex> поскольку <tex>K_r \nsubseteq G</tex>.
Следовательно, граф <tex>G</tex> является <tex>(r-1)</tex>-дольным.
Тогда по лемме из предположения об экстремальности <tex>G</tex> следует, что <tex>G = T^{r-1}(n)</tex>.

}}
==См. также==
*[[Раскраска графа]]
*[[Двудольные графы]]
==Источники информации==
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]

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

Алгоритмы на строках:Тикеты

2017-12-29T19:07:10Z

5.18.205.24: /* 1 Основные определения. Простые комбинаторные свойства слов */

'''Взяли все'''
== 1 Основные определения. Простые комбинаторные свойства слов ==

# [[Основные определения, связанные со строками]]
# [[Период и бордер, их связь]]
# [[Слово Фибоначчи]]
# [[Слово Туэ-Морса]]
# '''взяли''' [[Декомпозиция Линдона]]<tex>^\star</tex> 0,5
## заменить <tex>..</tex> на <tex>\ldots</tex>
## см. также
# [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
# [[Алгоритм Крочемора]]<tex>^\star</tex>
# [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
# '''взяли''' [[Алгоритм Манакера]]<tex>^\star</tex>0.5
## заменить <tex>..</tex> на <tex>\ldots</tex>
## <tex>d1</tex> заменить на <tex>d_1</tex>
# [[Дерево палиндромов]]<tex>^\star</tex>

== 2 Поиск подстроки в строке ==
0 [[Поиск подстроки в строке]] 0.25
## См. также
=== 1 Точный поиск ===
# [[Наивный алгоритм поиска подстроки в строке]] 0,25
## См. также
# [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Префикс-функция]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Кнута-Морриса-Пратта]]
# [[Автомат Кнута-Морриса-Пратта]]
# [[Z-функция]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Бор]]
# [[Алгоритм Ахо-Корасик]]
# [[Суффиксный автомат]]
# [[Алгоритм Бойера-Мура]] 0,25
## См. также
# [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex>
# [[Алгоритм Колусси]]<tex>^\star</tex> 0,25
## См. также
# [[Алгоритм Райта]]<tex>^\star</tex>
# [[Алгоритм Shift-And]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Двусторонний алгоритм]]<tex>^\star</tex>
# [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex>

=== 2 Нечёткий поиск ===
# [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>

== 3 Суффиксное дерево ==
# [[Суффиксный бор]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Сжатое суффиксное дерево]]
# [[Алгоритм Укконена]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм МакКрейта]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Фарача]]<tex>^\star</tex>

== 4 Суффиксный массив ==
# [[Суффиксный массив]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# '''взяли'''[[Построение суффиксного массива с помощью стандартных методов сортировки]] 2
## <tex>..</tex> заменить на <tex>\ldots</tex>
## разобраться с псевдокодом
# '''взяли''' [[Алгоритм цифровой сортировки суффиксов циклической строки]] 2
## <tex>..</tex> заменить на <tex>\ldots</tex>
## в картинки с примером есть ошибка
# [[Алгоритм Касаи и др.]]
# [[Алгоритм Карккайнена-Сандерса]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
# [[Количество подпалиндромов в строке]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>

Алгоритмы на строках:Тикеты

2017-12-29T19:05:40Z

5.18.205.24: /* 4 Суффиксный массив */

'''Взяли все'''
== 1 Основные определения. Простые комбинаторные свойства слов ==

# [[Основные определения, связанные со строками]]
# [[Период и бордер, их связь]]
# [[Слово Фибоначчи]]
# [[Слово Туэ-Морса]]
# [[Декомпозиция Линдона]]<tex>^\star</tex> 0,5
## заменить <tex>..</tex> на <tex>\ldots</tex>
## см. также
# [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
# [[Алгоритм Крочемора]]<tex>^\star</tex>
# [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
# [[Алгоритм Манакера]]<tex>^\star</tex>0.5
## заменить <tex>..</tex> на <tex>\ldots</tex>
## <tex>d1</tex> заменить на <tex>d_1</tex>
# [[Дерево палиндромов]]<tex>^\star</tex>

== 2 Поиск подстроки в строке ==
0 [[Поиск подстроки в строке]] 0.25
## См. также
=== 1 Точный поиск ===
# [[Наивный алгоритм поиска подстроки в строке]] 0,25
## См. также
# [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Префикс-функция]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Кнута-Морриса-Пратта]]
# [[Автомат Кнута-Морриса-Пратта]]
# [[Z-функция]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Бор]]
# [[Алгоритм Ахо-Корасик]]
# [[Суффиксный автомат]]
# [[Алгоритм Бойера-Мура]] 0,25
## См. также
# [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex>
# [[Алгоритм Колусси]]<tex>^\star</tex> 0,25
## См. также
# [[Алгоритм Райта]]<tex>^\star</tex>
# [[Алгоритм Shift-And]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Двусторонний алгоритм]]<tex>^\star</tex>
# [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex>

=== 2 Нечёткий поиск ===
# [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>

== 3 Суффиксное дерево ==
# [[Суффиксный бор]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Сжатое суффиксное дерево]]
# [[Алгоритм Укконена]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм МакКрейта]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Фарача]]<tex>^\star</tex>

== 4 Суффиксный массив ==
# [[Суффиксный массив]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# '''взяли'''[[Построение суффиксного массива с помощью стандартных методов сортировки]] 2
## <tex>..</tex> заменить на <tex>\ldots</tex>
## разобраться с псевдокодом
# '''взяли''' [[Алгоритм цифровой сортировки суффиксов циклической строки]] 2
## <tex>..</tex> заменить на <tex>\ldots</tex>
## в картинки с примером есть ошибка
# [[Алгоритм Касаи и др.]]
# [[Алгоритм Карккайнена-Сандерса]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
# [[Количество подпалиндромов в строке]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>

Дискретная математика3:Тикеты

2017-12-29T18:44:18Z

5.18.205.24: /* 10 Объединение матроидов */

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Матрица Кирхгофа из раздела Остовные деревья имеет тикет 3-1)

= Теория графов =
== 1. Основные определения теории графов ==
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
# [[Лемма о рукопожатиях]]
# [[Теорема о существовании простого пути в случае существования пути]]
# [[Теорема о существовании простого цикла в случае существования цикла]]
# [[Матрица смежности графа]]
# [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Источники -> Источники информации
## Добавить про списки смежности и их оформить тоже в таблички
# [[Циклическое пространство графа]]
# [[Фундаментальные циклы графа]]
# [[Дерево, эквивалентные определения]]
# [[Алгоритмы на деревьях]]
# [[Дополнительный, самодополнительный граф]]
# [[Теоретико-множественные операции над графами]]
# [[Рёберное ядро]] (2)
## Добавить больше интервики в конспект
## В конце теоремы в доказательстве какая-то лажа
## Источники информации
## Оформить следствия красиво
# [[Факторизация графов]]

== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]]
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# [[Теорема Менгера]]
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## пункт "Определения" не нужен
## Изменить знаки неравенств в tex
## Не надо дублировать определения из другого конспекта
## Отформатировать псевдокод
## find_flow какой-то стрёмный
## Источники информации
## k-связность с маленькой буквы
## Добавить См. также на что-нибудь разумное

== 3. Остовные деревья ==
=== Свойства остовных деревьев ===
<ol>
<li>[[Матрица Кирхгофа]]</li>
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
<li> [[Количество помеченных деревьев]] </li>
<li> [[Коды Прюфера]] </li>
</ol>

== 4. Обходы графов ==
=== Эйлеровы графы ===
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> [[Покрытие ребер графа путями]] (3)</li>
# Какое-то мутное доказательства
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
</ol>

=== Гамильтоновы графы ===
<ol>
<li value="5"> [[Гамильтоновы графы]] </li>
<li> [[Теорема Хватала]] </li>
<li> [[Теорема Дирака]] </li>
<li> [[Теорема Оре]] </li>
<li> [[Теорема Поша]]</li>
<li> [[Теорема Гуйя-Ури]] </li>
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Пояснить переходы в теореме
# Внести пояснение в определение бонда
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
# Картинку сделать красивой
<li> [[Турниры]] </li>
<li> [[Теорема Редеи-Камиона]] </li>
</ol>

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

== 6. Раскраски графов ==
# [[Раскраска графа]]
# [[Двудольные графы и раскраска в 2 цвета]]
# [[Хроматический многочлен]]
# [[Формула Зыкова]]
# [[Формула Уитни]]
# [[Теорема Брукса]]
# [[Верхние и нижние оценки хроматического числа]]
# [[Хроматическое число планарного графа]]
# [[Многочлен Татта]]
# [[Теория Рамсея]] ('''10''')
## Тут вообще ад какой-то

== 7. Задача о паросочетании ==
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
# [[Теорема Холла]]
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
# [[Связь вершинного покрытия и независимого множества]]
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# [[Теорема Татта о существовании полного паросочетания]]
# [[Декомпозиция Эдмондса-Галлаи]]
# '''взяли''' [[Задача об устойчивом паросочетании]] (5)
## паросочетание в интервики
## пару оформить нормально
## Зачем-то списки в доказательствах лемм использованы
## Надо бы доказать все леммы

= Матроиды =
== 8 Основные факты теории матроидов ==
# [[Определение матроида]]
# [[Примеры матроидов]]
# [[Прямая сумма матроидов]] 0,25
## Источники информации
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
# [[Теорема о базах]]
# [[Аксиоматизация матроида базами]]
# [[Теорема о циклах]] 0,25
## См также
# [[Аксиоматизация матроида циклами]] 0,25
## См также
# [[Ранговая функция, полумодулярность]]
# [[Аксиоматизация матроида рангами]]
# [[Двойственный матроид]]
# [[Оператор замыкания для матроидов]]
# [[Покрытия, закрытые множества]]
# [[Матроид Вамоса]]<tex>^\star</tex>
## См также

== 9 Пересечение матроидов ==
# [[Пересечение матроидов, определение, примеры]]
# [[Граф замен]]
# [[Алгоритм построения базы в пересечении матроидов]]

== 10 Объединение матроидов ==
# [[Объединение матроидов, проверка множества на независимость]]
# [[Объединение матроидов, доказательство того, что объединение является матроидом]] 1
## Добавить категории
## Добавить интервики
## Отформатировать по правилам
## Помёрджить с предыдущим конспектом
## См также
## Источники информации
# [[Алгоритм построения базы в объединении матроидов]] 7
## В определение само определение выделить жирным
## Добавить категории
## Добавить псевдокод
## Написать более подробное описание алгоритма поиска базы в объединении

Дискретная математика3:Тикеты

2017-12-29T18:43:55Z

5.18.205.24: /* 1. Основные определения теории графов */

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Матрица Кирхгофа из раздела Остовные деревья имеет тикет 3-1)

= Теория графов =
== 1. Основные определения теории графов ==
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
# [[Лемма о рукопожатиях]]
# [[Теорема о существовании простого пути в случае существования пути]]
# [[Теорема о существовании простого цикла в случае существования цикла]]
# [[Матрица смежности графа]]
# [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Источники -> Источники информации
## Добавить про списки смежности и их оформить тоже в таблички
# [[Циклическое пространство графа]]
# [[Фундаментальные циклы графа]]
# [[Дерево, эквивалентные определения]]
# [[Алгоритмы на деревьях]]
# [[Дополнительный, самодополнительный граф]]
# [[Теоретико-множественные операции над графами]]
# [[Рёберное ядро]] (2)
## Добавить больше интервики в конспект
## В конце теоремы в доказательстве какая-то лажа
## Источники информации
## Оформить следствия красиво
# [[Факторизация графов]]

== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]]
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# [[Теорема Менгера]]
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## пункт "Определения" не нужен
## Изменить знаки неравенств в tex
## Не надо дублировать определения из другого конспекта
## Отформатировать псевдокод
## find_flow какой-то стрёмный
## Источники информации
## k-связность с маленькой буквы
## Добавить См. также на что-нибудь разумное

== 3. Остовные деревья ==
=== Свойства остовных деревьев ===
<ol>
<li>[[Матрица Кирхгофа]]</li>
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
<li> [[Количество помеченных деревьев]] </li>
<li> [[Коды Прюфера]] </li>
</ol>

== 4. Обходы графов ==
=== Эйлеровы графы ===
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> [[Покрытие ребер графа путями]] (3)</li>
# Какое-то мутное доказательства
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
</ol>

=== Гамильтоновы графы ===
<ol>
<li value="5"> [[Гамильтоновы графы]] </li>
<li> [[Теорема Хватала]] </li>
<li> [[Теорема Дирака]] </li>
<li> [[Теорема Оре]] </li>
<li> [[Теорема Поша]]</li>
<li> [[Теорема Гуйя-Ури]] </li>
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Пояснить переходы в теореме
# Внести пояснение в определение бонда
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
# Картинку сделать красивой
<li> [[Турниры]] </li>
<li> [[Теорема Редеи-Камиона]] </li>
</ol>

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

== 6. Раскраски графов ==
# [[Раскраска графа]]
# [[Двудольные графы и раскраска в 2 цвета]]
# [[Хроматический многочлен]]
# [[Формула Зыкова]]
# [[Формула Уитни]]
# [[Теорема Брукса]]
# [[Верхние и нижние оценки хроматического числа]]
# [[Хроматическое число планарного графа]]
# [[Многочлен Татта]]
# [[Теория Рамсея]] ('''10''')
## Тут вообще ад какой-то

== 7. Задача о паросочетании ==
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
# [[Теорема Холла]]
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
# [[Связь вершинного покрытия и независимого множества]]
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# [[Теорема Татта о существовании полного паросочетания]]
# [[Декомпозиция Эдмондса-Галлаи]]
# '''взяли''' [[Задача об устойчивом паросочетании]] (5)
## паросочетание в интервики
## пару оформить нормально
## Зачем-то списки в доказательствах лемм использованы
## Надо бы доказать все леммы

= Матроиды =
== 8 Основные факты теории матроидов ==
# [[Определение матроида]]
# [[Примеры матроидов]]
# [[Прямая сумма матроидов]] 0,25
## Источники информации
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
# [[Теорема о базах]]
# [[Аксиоматизация матроида базами]]
# [[Теорема о циклах]] 0,25
## См также
# [[Аксиоматизация матроида циклами]] 0,25
## См также
# [[Ранговая функция, полумодулярность]]
# [[Аксиоматизация матроида рангами]]
# [[Двойственный матроид]]
# [[Оператор замыкания для матроидов]]
# [[Покрытия, закрытые множества]]
# [[Матроид Вамоса]]<tex>^\star</tex>
## См также

== 9 Пересечение матроидов ==
# [[Пересечение матроидов, определение, примеры]]
# [[Граф замен]]
# [[Алгоритм построения базы в пересечении матроидов]]

== 10 Объединение матроидов ==
# [[Объединение матроидов, проверка множества на независимость]]
# '''взяли''' [[Объединение матроидов, доказательство того, что объединение является матроидом]] 1
## Добавить категории
## Добавить интервики
## Отформатировать по правилам
## Помёрджить с предыдущим конспектом
## См также
## Источники информации
# [[Алгоритм построения базы в объединении матроидов]] 7
## В определение само определение выделить жирным
## Добавить категории
## Добавить псевдокод
## Написать более подробное описание алгоритма поиска базы в объединении

Дискретная математика:Тикеты

2017-12-23T08:07:35Z

5.18.205.24: /* 4 Свойства комбинаторных объектов */

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)

== 1. Отношения ==
#[[Определение отношения]] 0.5
## Оформить правильно источники информации
## Английские термины к видам отношений
#[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] 1
## Английские термины
## Источники информации
## Все формулы в тех
## Свойства оформить красиво
## Оформить правильно источники информации
# '''взяли''' [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] 0,25
## См. также
#[[Симметричное отношение]]
#[[Антисимметричное отношение]]
# '''взяли''' [[Транзитивное отношение]] 0,25
## Добавить См. также
#[[Отношение порядка]] 0,5
## Английские термины
## Добавить см. также
## Оформить правильно источники информации
#[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
# '''взяли''' [[Отношение эквивалентности]] 0,25
## добавить см. также
# '''взяли''' [[Транзитивное замыкание|Транзитивное замыкание отношения]] 0,5
## Добавить см. также
## Многоточие заменить на \ldots
#[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
# '''взяли''' [[Транзитивный остов]] 0,25
## Английские термины

== 2 Булевы функции ==
# [[Определение булевой функции]] 1,5
## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]])
## Добавить кратко про ДНФ, КНФ, полином Жегалкина и схемы из функциональных элементов
# [[Побитовые операции]]<tex>^\star</tex> 1
## Добавить краткую суть алгоритмов Флойда и Фенвика
# '''взяли''' [[Суперпозиции]] 0,5
## Добавить см. также
## Многоточие заменить на \ldots
#[[ДНФ]] 0,5 {{---}} 2 (зависит от примера)
## Многоточие заменить на \ldots
## Добавить пример еще какой нибудь функции
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
#[[КНФ]] 0,5 {{---}} 2 (зависит от примера)
## Многоточие заменить на \ldots
## Добавить пример еще какой нибудь функции
## Добавить см. также
#[[2-SAT]]
#[[XOR-SAT]]<tex>^\star</tex>
#[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
#'''взяли''' [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] 0,5
## Добавить см. также
## Многоточие заменить на \ldots
## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]])
#'''взяли''' [[Полные системы функций. Теорема Поста о полной системе функций]] 0,25
## Добавить см. также
#[[Представление функции класса DM с помощью медианы]] 0.5
## Добавить см. также
## Правильно оформить источники информации
## Заменить знаки неравенств
#'''взяли''' [[Пороговая функция]] 0.5
## Добавить см. также
## Многоточие заменить на \ldots
#[[Троичная логика]]<tex>^\star</tex>

== 3 Схемы из функциональных элементов ==
#[[Реализация булевой функции схемой из функциональных элементов]]
#'''взяли''' [[Простейшие методы синтеза схем из функциональных элементов]] 0.5
## Изменить знаки неравенств
## Ссылку на метод синтеза схем Шэннона сделать примечанием
## Определение жирным
## Оформить правильно См. также и Источники информации
## Увеличить дроби
#'''взяли''' [[Метод Лупанова синтеза схем]] 0.5
## Заменить литературу на источники информации
## Изменить знаки неравенств
## Запятые криво стоят в определении функции g
## Увеличить дроби
#[[Cумматор]]
#[[Каскадный сумматор]]
#[[Двоичный каскадный сумматор]]
#[[Троичный сумматор]]<tex>^\star</tex>
#[[Реализация вычитания сумматором]]
#[[Матричный умножитель]]
#[[Дерево Уоллеса]]
#[[Контактная схема]] 1
## Перерисовать картинки с построением контактных схем и дерево конъюнктов
#[[Триггеры]]<tex>^\star</tex>
#[[Квантовые гейты]]<tex>^\star</tex>

== 4 Представление информации ==
# [[Кодирование информации]]
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
# [[Представление вещественных чисел]]
# [[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== 5 Алгоритмы сжатия ==
# [[Алгоритм Хаффмана]]
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
# '''взяли''' [[Алгоритм Хаффмана за O(n)]] 1
## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
# [[Неравенство Крафта]]
# [[Неравенство Макмиллана]]
# [[Код Шеннона]]
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
# [[Алгоритмы LZ77 и LZ78]] 2
## Переменные и константы взять в Tex
## Добавить примеры итоговых таблиц
## Рассказать, как декодировать
## Правильно оформить источники информации
## Получше расписать описание алгоритма
## Таблицы сделать красивыми
## Интервики
# [[Алгоритм LZW]] 0,25
## См. также
# [[Алгоритм LZSS]]<tex>^\star</tex>
# [[Алгоритм LZMA]]<tex>^\star</tex>
# [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
# [[Преобразование MTF]]
# [[Расстояние Хэмминга]]
# [[Избыточное кодирование, код Хэмминга]] 0,25
## См. также
# [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> 0,25
## См. также

== 6 Комбинаторика ==
=== 1 Комбинаторные объекты ===
# [[Комбинаторные объекты]]
# [[Лексикографический порядок]]
# [[Коды Грея]]
# [[Коды Грея для перестановок]]
# [[Коды антигрея]]
# [[Монотонный код Грея]]
# [[Цепные коды]]
# [[Правильные скобочные последовательности]]

=== 2 Генерация комбинаторных объектов ===
# [[Генерация комбинаторных объектов в лексикографическом порядке]] 0.5
## Заменить скобки "больше-меньше" на угловые
## Нормальную красивую картинку нарисовать
# [[Получение номера по объекту]]
# [[Получение объекта по номеру]]
# [[Получение следующего объекта]]
# [[Получение предыдущего объекта]]<tex>^\star</tex>
# [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
# [[Методы генерации случайного сочетания]]<tex>^\star</tex>

=== 3 Подсчёт числа объектов ===
# [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] 0,5
## Сделать через tex возведение в степень в заголовках
## См. также
# [[Лемма Бёрнсайда и Теорема Пойа]]
# [[Задача об ожерельях]]
# '''взяли''' [[Числа Стирлинга первого рода]] 5
## <tex>\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex> то есть результат не зависит от <tex>m</tex>?
## доказательства дополнительных тождеств
# [[Числа Стирлинга второго рода]]
# '''взяли''' [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex> 0,25
## См. также
# '''взяли''' [[Числа Каталана]] 0,25
## См. также

=== 4 Свойства комбинаторных объектов ===
# '''взяли'''[[Умножение перестановок, обратная перестановка, группа перестановок]] 5
## Английские термины
## Определения жирным
## Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
## Отформатировать псевдокоды
## Все переменные и константы взять в Tex
## Оформить правильно источники информации
## Добавить примеров из конспекта групп по теории чисел
## Добавить реккурентную формулу числа инволюций c доказательством
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
# [[Таблица инверсий]] 0,25
## tex в заголовок
# [[Теорема Кэли]]
# [[Матричное представление перестановок]]
# [[Задача о минимуме/максимуме скалярного произведения]] 0,25
## Cм. также
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] 0.25
## См. также

Дискретная математика:Тикеты

2017-10-22T10:12:41Z

5.18.205.24: /* 4 Свойства комбинаторных объектов */

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-4)

== 1. Отношения ==
#[[Определение отношения]] 0.5
## Оформить правильно источники информации
## Английские термины к видам отношений
#[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] 1
## Английские термины
## Источники информации
## Все формулы в тех
## Свойства оформить красиво
## Оформить правильно источники информации
#[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] 0,25
## См. также
#[[Симметричное отношение]]
#[[Антисимметричное отношение]]
#[[Транзитивное отношение]] 0,25
## Добавить См. также
#[[Отношение порядка]] 0,5
## Английские термины
## Добавить см. также
## Оформить правильно источники информации
#[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
#[[Отношение эквивалентности]] 0,25
## добавить см. также
#[[Транзитивное замыкание|Транзитивное замыкание отношения]] 0,5
## Добавить см. также
## Многоточие заменить на \ldots
#[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
#[[Транзитивный остов]] 0,25
## Английские термины

== 2 Булевы функции ==
# [[Определение булевой функции]] 1,5
## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]])
## Добавить кратко про ДНФ, КНФ, полином Жегалкина и схемы из функциональных элементов
# [[Побитовые операции]]<tex>^\star</tex> 1
## Добавить краткую суть алгоритмов Флойда и Фенвика
#[[Суперпозиции]] 0,5
## Добавить см. также
## Многоточие заменить на \ldots
#[[ДНФ]] 0,5 {{---}} 2 (зависит от примера)
## Многоточие заменить на \ldots
## Добавить пример еще какой нибудь функции
#[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
#[[КНФ]] 0,5 {{---}} 2 (зависит от примера)
## Многоточие заменить на \ldots
## Добавить пример еще какой нибудь функции
## Добавить см. также
#[[2-SAT]]
#[[XOR-SAT]]<tex>^\star</tex>
#[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
#[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] 0,5
## Добавить см. также
## Многоточие заменить на \ldots
## Добавить интервики на термины монотонности, линейности, сохранения <tex>0</tex> и <tex>1</tex>, самодвойственности для булевой функции. (все определения [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|здесь]])
#[[Полные системы функций. Теорема Поста о полной системе функций]] 0,25
## Добавить см. также
#[[Представление функции класса DM с помощью медианы]] 0.5
## Добавить см. также
## Правильно оформить источники информации
## Заменить знаки неравенств
#[[Пороговая функция]] 0.5
## Добавить см. также
## Многоточие заменить на \ldots
#[[Троичная логика]]<tex>^\star</tex>

== 3 Схемы из функциональных элементов ==
#[[Реализация булевой функции схемой из функциональных элементов]]
#[[Простейшие методы синтеза схем из функциональных элементов]] 0.5
## Изменить знаки неравенств
## Ссылку на метод синтеза схем Шэннона сделать примечанием
## Определение жирным
## Оформить правильно См. также и Источники информации
## Увеличить дроби
#[[Метод Лупанова синтеза схем]] 0.5
## Заменить литературу на источники информации
## Изменить знаки неравенств
## Запятые криво стоят в определении функции g
## Увеличить дроби
#[[Cумматор]]
#[[Каскадный сумматор]]
#[[Двоичный каскадный сумматор]]
#[[Троичный сумматор]]<tex>^\star</tex>
#[[Реализация вычитания сумматором]]
#[[Матричный умножитель]]
#[[Дерево Уоллеса]]
#[[Контактная схема]] 1
## Перерисовать картинки с построением контактных схем и дерево конъюнктов
#[[Триггеры]]<tex>^\star</tex>
#[[Квантовые гейты]]<tex>^\star</tex>

== 4 Представление информации ==
# [[Кодирование информации]]
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
# [[Представление вещественных чисел]]
# [[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== 5 Алгоритмы сжатия ==
# [[Алгоритм Хаффмана]]
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
# [[Алгоритм Хаффмана за O(n)]] 1
## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
# [[Неравенство Крафта]]
# [[Неравенство Макмиллана]]
# [[Код Шеннона]]
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
# [[Алгоритмы LZ77 и LZ78]] 2
## Переменные и константы взять в Tex
## Добавить примеры итоговых таблиц
## Рассказать, как декодировать
## Правильно оформить источники информации
## Получше расписать описание алгоритма
## Таблицы сделать красивыми
## Интервики
# [[Алгоритм LZW]] 0,25
## См. также
# [[Алгоритм LZSS]]<tex>^\star</tex>
# [[Алгоритм LZMA]]<tex>^\star</tex>
# [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
# [[Преобразование MTF]]
# [[Расстояние Хэмминга]]
# [[Избыточное кодирование, код Хэмминга]] 0,25
## См. также
# [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> 0,25
## См. также

== 6 Комбинаторика ==
=== 1 Комбинаторные объекты ===
# [[Комбинаторные объекты]]
# [[Лексикографический порядок]]
# [[Коды Грея]]
# [[Коды Грея для перестановок]]
# [[Коды антигрея]]
# [[Монотонный код Грея]]
# [[Цепные коды]]
# [[Правильные скобочные последовательности]]

=== 2 Генерация комбинаторных объектов ===
# [[Генерация комбинаторных объектов в лексикографическом порядке]] 0.5
## Заменить скобки "больше-меньше" на угловые
## Нормальную красивую картинку нарисовать
# [[Получение номера по объекту]]
# [[Получение объекта по номеру]]
# [[Получение следующего объекта]]
# [[Получение предыдущего объекта]]<tex>^\star</tex>
# [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
# [[Методы генерации случайного сочетания]]<tex>^\star</tex>

=== 3 Подсчёт числа объектов ===
# [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] 0,5
## Сделать через tex возведение в степень в заголовках
## См. также
# [[Лемма Бёрнсайда и Теорема Пойа]]
# [[Задача об ожерельях]]
# [[Числа Стирлинга первого рода]] 5
## <tex>\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex> то есть результат не зависит от <tex>m</tex>?
## доказательства дополнительных тождеств
# [[Числа Стирлинга второго рода]]
# [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex> 0,25
## См. также
# [[Числа Каталана]] 0,25
## См. также

=== 4 Свойства комбинаторных объектов ===
# [[Умножение перестановок, обратная перестановка, группа перестановок]] 5
## Английские термины
## Определения жирным
## Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
## Отформатировать псевдокоды
## Все переменные и константы взять в Tex
## Оформить правильно источники информации
## Добавить примеров из конспекта групп по теории чисел
## Добавить реккурентную формулу числа инволюций c доказательством
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
# [[Таблица инверсий]] 0,25
## tex в заголовок
# [[Теорема Кэли]]
# [[Матричное представление перестановок]]
# [[Задача о минимуме/максимуме скалярного произведения]] 0,25
## Cм. также
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] 0.25
## См. также

Кураторство вики-конспектов

2017-09-22T18:52:08Z

5.18.205.24:

== Тикеты ==
* [[Дискретная математика:Тикеты]] 1 семестр
* [[Динамическое программирование:Тикеты]] 2 cеместр
* [[Теория вероятности:Тикеты]] 2 семестр
* [[Теория формальных языков:Тикеты]] 2 семестр
* [[Теория матроидов:Тикеты]] 3 семестр
* [[Теория расписаний:Тикеты]] 3 семестр
* [[Производящие функции:Тикеты]] 4 семестр
* [[Теория вычислимости:Тикеты]] 4 семестр
* [[Дискретная математика3:Тикеты]] 3 семестр дм

* [[Алгоритмы и структуры данных:Тикеты]] 1,2 семестры
* [[Теория графов:Тикеты]] 2,3 семестр
* [[Алгоритмы на строках:Тикеты]] 3,4 семестр

Теория матроидов:Тикеты

2017-03-15T16:18:35Z

5.18.205.24: /* 3 Объединение матроидов */

== 1 Основные факты теории матроидов ==
# [[Определение матроида]]
# [[Примеры матроидов]]
# [[Прямая сумма матроидов]] 0,25
## Источники информации
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
# [[Теорема о базах]]
# [[Аксиоматизация матроида базами]]
# [[Теорема о циклах]] 0,25
## См также
# [[Аксиоматизация матроида циклами]] 0,25
## См также
# [[Ранговая функция, полумодулярность]]
# [[Аксиоматизация матроида рангами]]
# [[Двойственный матроид]]
# [[Оператор замыкания для матроидов]]
# [[Покрытия, закрытые множества]]
# [[Матроид Вамоса]]<tex>^\star</tex>
## См также

== 2 Пересечение матроидов ==
# [[Пересечение матроидов, определение, примеры]]
# взяли [[Граф замен]] 5
## английские термины
## Док-во по индукции оформить красиво
## Исправить док-во: неверный переход
## Заменить xor на треугольник
# [[Алгоритм построения базы в пересечении матроидов]]

== 3 Объединение матроидов ==
# [[Объединение матроидов, проверка множества на независимость]]
# [[Объединение матроидов, доказательство того, что объединение является матроидом]] 1
## Добавить категории
## Добавить интервики
## Отформатировать по правилам
## Помёрджить с предыдущим конспектом
## См также
## Источники информации
# взяли [[Алгоритм построения базы в объединении матроидов]] 7
## В определение само определение выделить жирным
## Добавить категории
## Добавить псевдокод
## Написать более подробное описание алгоритма поиска базы в объединении

Теория матроидов:Тикеты

2017-03-06T20:56:41Z

5.18.205.24: /* 2 Пересечение матроидов */

== 1 Основные факты теории матроидов ==
# [[Определение матроида]]
# [[Примеры матроидов]]
# [[Прямая сумма матроидов]] 0,25
## Источники информации
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
# [[Теорема о базах]]
# [[Аксиоматизация матроида базами]]
# [[Теорема о циклах]] 0,25
## См также
# [[Аксиоматизация матроида циклами]] 0,25
## См также
# [[Ранговая функция, полумодулярность]]
# [[Аксиоматизация матроида рангами]]
# [[Двойственный матроид]]
# [[Оператор замыкания для матроидов]]
# [[Покрытия, закрытые множества]]
# [[Матроид Вамоса]]<tex>^\star</tex>
## См также

== 2 Пересечение матроидов ==
# [[Пересечение матроидов, определение, примеры]]
# взяли [[Граф замен]] 5
## английские термины
## Док-во по индукции оформить красиво
## Исправить док-во: неверный переход
## Заменить xor на треугольник
# [[Алгоритм построения базы в пересечении матроидов]]

== 3 Объединение матроидов ==
# [[Объединение матроидов, проверка множества на независимость]]
# [[Объединение матроидов, доказательство того, что объединение является матроидом]] 1
## Добавить категории
## Добавить интервики
## Отформатировать по правилам
## Помёрджить с предыдущим конспектом
## См также
## Источники информации
# [[Алгоритм построения базы в объединении матроидов]] 7
## В определение само определение выделить жирным
## Добавить категории
## Добавить псевдокод
## Написать более подробное описание алгоритма поиска базы в объединении

Лемма о разрастании для КС-грамматик

2016-10-28T15:34:20Z

5.18.205.24:

__FORCETOC__
== Лемма о разрастании для КС-грамматик ==

{{Лемма
|id=lemma
|about=о разрастании КС-грамматик
|statement=
Пусть <tex>L</tex> — [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]] над алфавитом <tex>\Sigma</tex>, тогда существует такое <tex>n</tex>, что для любого слова <tex> \omega \in L</tex> длины не меньше <tex>n</tex> найдутся слова <tex> u,v,x,y,z \in \Sigma^*</tex>, для которых верно: <tex>uvxyz=\omega, vy\neq \varepsilon, |vxy|\leqslant n</tex> и <tex>\forall k \geqslant 0~uv^{k}xy^{k}z\in L</tex>.
|proof=
[[Файл:CS_lemma_conspect.PNG||left|240px|]] Грамматика любого контекстно-свободного языка может быть записана в [[Нормальная форма Хомского|нормальной форме Хомского (НФХ)]]. Пусть <tex>m</tex> — количество нетерминалов в грамматике языка <tex>L</tex>, записанной в НФХ.
Выберем <tex>n=2^{m+1}</tex>. Построим дерево разбора произвольного слова <tex>\omega</tex> длиной больше, чем <tex>n</tex>. Высотой дерева разбора назовем максимальное число нетерминальных символов на пути от корня дерева к листу. Так как грамматика языка <tex>L</tex> записана в НФХ, то у любого нетерминала в дереве могут быть, либо два потомка нетерминала, либо один потомок терминал. Поэтому высота дерева разбора слова <tex>\omega</tex> не меньше <tex>m+1</tex>.

Выберем путь от корня дерева к листу максимальной длины. Количество нетерминалов в нем не меньше, чем <tex>m+1</tex>, следовательно, найдется такой нетерминал <tex>B</tex>, который встречается на этом пути дважды. Значит, в дереве разбора найдется нетерминал <tex>B</tex>, в поддереве которого содержится нетерминал <tex>B</tex>. Выберем такой нетерминал <tex>A</tex>, чтобы в его поддереве содержался такой же нетерминал и длина пути от него до корня была максимальна среди всех нетерминалов, содержащих в поддереве такой же нетерминал.

Найдем слова <tex> u,v,x,y,z </tex>.

*Рассмотрим нетерминал <tex>A</tex>, содержащийся в поддереве выбранного нетерминала. Тогда <tex>x</tex> {{---}} строка терминалов, которая выведена из рассмотренного нетерминала в данном дереве разбора. Тогда <tex>A \Rightarrow^{*} x</tex>.
*Рассмотрим выбранный ранее нетерминал <tex>A</tex>. Пусть <tex>t</tex> {{---}} строка терминальных символов, которая выведена из рассмотренного нетерминала в данном дереве разбора. Тогда, так как выбранный нетерминал <tex>A</tex> содержит в своем поддереве такой же нетерминал, то <tex>A \Rightarrow^{*}\alpha A \beta \Rightarrow^{*} t</tex>, где <tex>\alpha,\beta</tex> - строки, которые могут содержать как терминалы, так и нетерминалы. При этом как минимум одна из строк <tex>\alpha,\beta</tex> не пуста, так как грамматика языка записана в НФХ. Пусть <tex>v</tex> и <tex>y</tex> - строки, состоящие из терминалов, которые выведены соответственно из <tex>\alpha</tex> и <tex>\beta</tex>, в данном дереве разбора. Тогда <tex>t = vxy</tex>. Так как хотя бы одна из строк <tex>\alpha,\beta</tex> не пуста, то <tex>vy\neq \varepsilon</tex>. Получаем <tex>A \Rightarrow^{*} vAy \Rightarrow^{*} vxy</tex>.
*Рассмотрим стартовый нетерминал <tex>S</tex>. Из <tex>S</tex> выведена строка <tex>\omega</tex>. При этом <tex>S \Rightarrow^{*} \alpha A \beta \Rightarrow^{*} \omega </tex>, где <tex>A</tex> {{---}} выбранный ранее нетерминал. Из <tex>A</tex> в данном дереве разбора выведена строка <tex>vxy</tex>. Пусть <tex>u</tex> и <tex>z</tex> {{---}} строки, состоящие из терминалов, которые выведены соответственно из <tex>\alpha</tex> и <tex>\beta</tex> в данном дереве разбора. Тогда <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} \omega</tex>.

Покажем, что <tex>|vxy| \leqslant n</tex>. Допустим, что <tex>|vxy|>n</tex>. Тогда высота поддерева с корнем в вершине, соответствующей выбранному <tex>A</tex>, не меньше <tex>m+2</tex>. Рассмотрим поддерево вершины, в котором содержится нетерминал <tex>A</tex>. Тогда высота этого поддерева не меньше <tex>m+1</tex>. Рассмотрим путь максимальной длины от корня этого поддерева к листу. В нем содержится не менее <tex>m+1</tex> нетерминалов, причем не содержится стартовый нетерминал. Следовательно, на этом пути найдутся два одинаковых нетерминала, что противоречит условию наибольшей удаленности от корня выбранного ранее нетерминала <tex>A</tex>. Получили противоречие. Поэтому <tex>|vxy|\leqslant n</tex>.
Таким образом, в рамках нашей грамматики мы можем построить цепочку вывода: <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvvAyyz \Rightarrow^{*} uv^{k}Ay^{k}z \Rightarrow^{*} uv^{k}xy^{k}z</tex>.
}}

'''Замечание.''' Условие леммы не является достаточным для контекстно-свободности языка. Но, в силу необходимости условия, данная лемма часто используется для доказательства неконтекстно-свободности языков.

== Пример доказательства неконтекстно-свободности языка с использованием леммы ==

Рассмотрим язык <tex>0^{n}1^{n}2^{n}</tex>. Покажем, что он не является контекстно-свободным.

Для фиксированного <tex>n</tex> рассмотрим слово <tex>\omega=0^n 1^n 2^n</tex>. Пусть <tex>\omega</tex> разбили на <tex>u, v, x, y, z</tex> произвольным образом. Так как <tex>|vxy|\leqslant n</tex>, то в слове <tex>vxy</tex> не содержится либо ни одного символа <tex>0</tex>, либо ни одного символа <tex>2</tex>. Для любого такого разбиения выбираем <tex>k=2</tex> и получаем, что количество символов <tex>1</tex> изменилось, а количество либо <tex>0</tex>, либо <tex>2</tex> осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык <tex>0^{n}1^{n}2^{n}</tex> не является контекстно-свободным по лемме о разрастании для КС-грамматик.

== См. также ==
[[Лемма_Огдена|Лемма Огдена]]

== Источники ==

* Хопкрофт Д., Мотвани Р., Ульман Д. {{---}} Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} Москва, Издательский дом «Вильямс», 2002. {{---}} 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Опровержение контекстно-свободности языка]]