Участник:Shersh/Тикеты к 3ему терму — различия между версиями
Shersh (обсуждение | вклад) (→Эйлеровы графы) |
Shersh (обсуждение | вклад) м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 3ему терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))) |
||
| (не показаны 44 промежуточные версии этого же участника) | |||
| Строка 3: | Строка 3: | ||
== 1. Основные определения теории графов == | == 1. Основные определения теории графов == | ||
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]] | # [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]] | ||
| − | # | + | # [[Лемма о рукопожатиях]] |
| − | + | # ''fixed'' [[Теорема о существовании простого пути в случае существования пути]] (4) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | # '' | ||
## Алгоритм и предположение зря оформлены как псевдокод | ## Алгоритм и предположение зря оформлены как псевдокод | ||
## Добавить ссылок | ## Добавить ссылок | ||
| Строка 17: | Строка 12: | ||
## Добавить в формулировку теоремы, что вершинно-простой путь | ## Добавить в формулировку теоремы, что вершинно-простой путь | ||
# [[Теорема о существовании простого цикла в случае существования цикла]] | # [[Теорема о существовании простого цикла в случае существования цикла]] | ||
| − | # | + | # [[Матрица смежности графа]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'') | # ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'') | ||
## Добавить свойства матрицы инцидентности с доказательствами | ## Добавить свойства матрицы инцидентности с доказательствами | ||
| Строка 34: | Строка 21: | ||
## Добавить про списки смежности и их оформить тоже в таблички | ## Добавить про списки смежности и их оформить тоже в таблички | ||
# [[Циклическое пространство графа]] | # [[Циклическое пространство графа]] | ||
| − | # '' | + | # ''fixed'' [[Фундаментальные циклы графа]] (1) |
## Источники информации нормально оформить | ## Источники информации нормально оформить | ||
## Подписать получше картинку | ## Подписать получше картинку | ||
## Заменить многоточия на \ldots | ## Заменить многоточия на \ldots | ||
| − | # '' | + | ## Отформатировать по правилам |
| + | # ''fixed'' [[Дерево, эквивалентные определения]] (1) | ||
## Англоязычные термины | ## Англоязычные термины | ||
## Пофиксить знаки неравенств | ## Пофиксить знаки неравенств | ||
## Источники информации нормально оформить | ## Источники информации нормально оформить | ||
| + | ## Оформить красиво доказательства | ||
# [[Алгоритмы на деревьях]] | # [[Алгоритмы на деревьях]] | ||
| − | # '' | + | # ''fixed'' [[Дополнительный, самодополнительный граф]] (1) |
## Англоязычные термины оформить правильно | ## Англоязычные термины оформить правильно | ||
## Заменить угловые скобки на \langle и \rangle | ## Заменить угловые скобки на \langle и \rangle | ||
| Строка 50: | Строка 39: | ||
## Шаблоном заменить тире | ## Шаблоном заменить тире | ||
# [[Теоретико-множественные операции над графами]] | # [[Теоретико-множественные операции над графами]] | ||
| + | # [[Рёберное ядро]] (2) | ||
| + | ## Добавить больше интервики в конспект | ||
| + | ## В конце теоремы в доказательстве какая-то лажа | ||
| + | ## Источники информации | ||
| + | ## Оформить следствия красиво | ||
| + | # [[Факторизация графов]] | ||
== 2. Связность в графах == | == 2. Связность в графах == | ||
| − | # | + | # [[Отношение связности, компоненты связности]] |
| − | # | + | # [[Отношение реберной двусвязности]] |
| − | + | # [[Отношение вершинной двусвязности]] | |
| − | + | # [[Точка сочленения, эквивалентные определения]] | |
| − | + | # [[Мост, эквивалентные определения]] | |
| − | + | # [[Граф компонент реберной двусвязности]] | |
| − | + | # [[Граф блоков-точек сочленения]] | |
| − | + | # [[k-связность]] | |
| − | + | # ''fixed'' [[Теорема Менгера]] (0.5) | |
| − | # | ||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Теорема Менгера]] (0.5) | ||
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами | ## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами | ||
## Тире заменить на шаблон | ## Тире заменить на шаблон | ||
## Можно добавить ссылок, оформить см. также по-другому | ## Можно добавить ссылок, оформить см. также по-другому | ||
## Источники информации | ## Источники информации | ||
| − | # | + | # [[Теорема Менгера, альтернативное доказательство]] |
| − | |||
| − | |||
| − | |||
| − | |||
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5) | # [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5) | ||
## пункт "Определения" не нужен | ## пункт "Определения" не нужен | ||
| Строка 113: | Строка 78: | ||
<li>[[Алгоритм Прима]]</li> | <li>[[Алгоритм Прима]]</li> | ||
<li> [[Алгоритм Краскала]] </li> | <li> [[Алгоритм Краскала]] </li> | ||
| − | <li> | + | <li> [[Алгоритм Борувки]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li> | <li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li> | ||
# Доказательство красиво оформить | # Доказательство красиво оформить | ||
| Строка 130: | Строка 87: | ||
# Знаки неравенств | # Знаки неравенств | ||
# Категория | # Категория | ||
| − | <li> '''!!!''' [[Алгоритм двух китайцев]] ( | + | <li> '''!!!''' [[Алгоритм двух китайцев]] (7) </li> |
# Англоязычные термины оформить правильно | # Англоязычные термины оформить правильно | ||
# Добавить определение покрывающего дерева | # Добавить определение покрывающего дерева | ||
| Строка 147: | Строка 104: | ||
<ol> | <ol> | ||
<li value="7">[[Матрица Кирхгофа]]</li> | <li value="7">[[Матрица Кирхгофа]]</li> | ||
| − | <li> | + | <li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li> |
| − | + | <li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li> | |
| − | + | <li> [[Количество помеченных деревьев]] </li> | |
| − | + | <li> [[Коды Прюфера]] </li> | |
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
</ol> | </ol> | ||
| Строка 176: | Строка 114: | ||
<ol> | <ol> | ||
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li> | <li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li> | ||
| − | <li> '' | + | <li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li> |
| − | # | + | # Какое-то мутное доказательства |
| − | + | <li> [[Алгоритм построения Эйлерова цикла]] (2) </li> | |
| − | + | # Какое-то мутное доказательство леммы про корректность алгоритма | |
| − | + | <li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li> | |
| − | |||
| − | |||
| − | <li> | ||
| − | # | ||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ol> | </ol> | ||
=== Гамильтоновы графы === | === Гамильтоновы графы === | ||
<ol> | <ol> | ||
| − | <li value="5"> | + | <li value="5"> [[Гамильтоновы графы]] </li> |
| − | + | <li> [[Теорема Хватала]] </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Теорема Дирака]] </li> | <li> [[Теорема Дирака]] </li> | ||
<li> [[Теорема Оре]] </li> | <li> [[Теорема Оре]] </li> | ||
| − | <li> | + | <li> [[Теорема Поша]]</li> |
| − | + | <li> [[Теорема Гуйя-Ури]] </li> | |
| − | + | <li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li> | |
| − | + | <li> '''!!!''' [[Теорема Гринберга]] (5) </li> | |
| − | + | # Пояснить переходы в теореме | |
| − | + | # Внести пояснение в определение бонда | |
| − | + | # И зачем нужно доказывать отсутствие гамильтонова бонда в графе? | |
| − | + | # Картинку сделать красивой | |
| − | <li> ''' | + | <li> '''взяли''' [[Турниры]] (6) </li> |
| − | # | + | # Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация) |
| − | # | + | <li> [[Теорема Редеи-Камиона]] </li> |
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | # | ||
| − | |||
| − | <li> ''' | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # Доказательства всех утверждений из конспекта (эквивалентность | ||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
</ol> | </ol> | ||
== 5. Укладки графов == | == 5. Укладки графов == | ||
| − | # | + | # [[Укладка графа на плоскости]] |
| − | + | # [[Формула Эйлера]] | |
| − | + | # ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5) | |
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5) | ||
## Исправить знаки неравенств | ## Исправить знаки неравенств | ||
## Источники информации | ## Источники информации | ||
## Константы в Tex | ## Константы в Tex | ||
| − | # | + | # [[Укладка дерева]] |
| − | # | + | # [[Укладка графа с планарными компонентами реберной двусвязности]] |
| − | + | # [[Укладка графа с планарными компонентами вершинной двусвязности]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Теорема Понтрягина-Куратовского]] | # [[Теорема Понтрягина-Куратовского]] | ||
| − | # | + | # [[Род, толщина, крупность, число скрещиваний]] |
| − | + | # [[Двойственный граф планарного графа]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Теорема Фари]] | # [[Теорема Фари]] | ||
| + | # [[Гамма-алгоритм]] | ||
== 6. Раскраски графов == | == 6. Раскраски графов == | ||
| − | # | + | # [[Раскраска графа]] |
| − | + | # ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # '' | ||
## Англоязычные термины | ## Англоязычные термины | ||
## Убрать определение двудольного графа и сделать интервики на основной конспект | ## Убрать определение двудольного графа и сделать интервики на основной конспект | ||
| Строка 311: | Строка 167: | ||
## Перенести см. также до источников информации, а ссылку заменить на интервики | ## Перенести см. также до источников информации, а ссылку заменить на интервики | ||
# [[Хроматический многочлен]] | # [[Хроматический многочлен]] | ||
| − | # | + | # [[Формула Зыкова]] |
| − | + | # [[Формула Уитни]] | |
| − | + | # [[Теорема Брукса]] | |
| − | + | # [[Верхние и нижние оценки хроматического числа]] | |
| − | + | # [[Хроматическое число планарного графа]] | |
| − | + | # [[Многочлен Татта]] | |
| − | + | # [[Теория Рамсея]] ('''10''') | |
| − | # | ||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Теория Рамсея]] (''' | ||
## Тут вообще ад какой-то | ## Тут вообще ад какой-то | ||
== 7. Обход в глубину == | == 7. Обход в глубину == | ||
| − | # ''' | + | # '''fixed''' [[Обход в глубину, цвета вершин]] (5) |
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
| − | |||
## Красивую картинку с цветными вершинами | ## Красивую картинку с цветными вершинами | ||
# [[Лемма о белых путях]] | # [[Лемма о белых путях]] | ||
| − | # | + | # [[Использование обхода в глубину для проверки связности]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]] | # [[Использование обхода в глубину для поиска цикла в ориентированном графе]] | ||
# [[Использование обхода в глубину для топологической сортировки]] | # [[Использование обхода в глубину для топологической сортировки]] | ||
| − | # | + | # [[Использование обхода в глубину для поиска компонент сильной связности]] |
| − | + | # ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4) | |
| − | + | ## Что-то картинки неудачно расположены | |
| − | + | ## Кривая структура у доказательства | |
| − | # '' | ||
| − | ## | ||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
## Источники информации красиво оформить | ## Источники информации красиво оформить | ||
| − | # | + | # [[Построение компонент вершинной двусвязности]] |
| − | + | # [[Использование обхода в глубину для поиска мостов]] | |
| − | + | # [[Построение компонент реберной двусвязности]] | |
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
== 8. Кратчайшие пути в графах == | == 8. Кратчайшие пути в графах == | ||
# [[Обход в ширину]] | # [[Обход в ширину]] | ||
| − | # | + | # [[Алгоритм Форда-Беллмана]] |
| − | # | + | # [[Алгоритм Дейкстры]] |
| − | + | # [[Алгоритм Флойда]] | |
| − | + | # [[Алгоритм Джонсона]] | |
| − | + | # [[Алгоритм Левита]] | |
| − | + | # [[Алгоритм A*]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Алгоритм D*]] | # [[Алгоритм D*]] | ||
| − | # | + | # [[Эвристики для поиска кратчайших путей]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== 9. Задача о паросочетании == | == 9. Задача о паросочетании == | ||
| − | # | + | # [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] |
| − | + | # [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | |
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Алгоритм Куна для поиска максимального паросочетания]] | # [[Алгоритм Куна для поиска максимального паросочетания]] | ||
| − | # | + | # [[Теорема Холла]] |
| − | # | + | # [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] |
| − | + | # [[Связь вершинного покрытия и независимого множества]] | |
| − | + | # [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | |
| − | + | # [[Теорема Татта о существовании полного паросочетания]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7) | # '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7) | ||
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками | ## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками | ||
| − | # | + | # [[Декомпозиция Эдмондса-Галлаи]] |
| − | + | # '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)'' | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # ''' | ||
## Переменные и константы в Tex | ## Переменные и константы в Tex | ||
## Добавить сначала постановку задачи | ## Добавить сначала постановку задачи | ||
| Строка 518: | Строка 233: | ||
== 10. Задача о максимальном потоке == | == 10. Задача о максимальном потоке == | ||
# [[Определение сети, потока]] | # [[Определение сети, потока]] | ||
| − | # | + | # [[Разрез, лемма о потоке через разрез]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Дополняющая сеть, дополняющий путь]] | # [[Дополняющая сеть, дополняющий путь]] | ||
| − | # | + | # [[Лемма о сложении потоков]] |
| − | + | # [[Теорема Форда-Фалкерсона]] | |
| − | + | # [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | |
| − | + | # '''взяли''' [[Алоритм Эдмондса-Карпа]] (5) | |
| − | # | + | ## Полностью описать пример про грибок с картинками в конспекте |
| − | + | # [[Алгоритм масштабирования потока]] | |
| − | + | # ''взяли'' [[Блокирующий поток]] (1) | |
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # ''' | ||
| − | ## | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Блокирующий поток]] (1) | ||
## англоязычные термины | ## англоязычные термины | ||
## ссылки на русскую и английскую википедию | ## ссылки на русскую и английскую википедию | ||
## Добавить немного общей информации | ## Добавить немного общей информации | ||
## Расположить красиво картинки, чтобы не наезжали | ## Расположить красиво картинки, чтобы не наезжали | ||
| − | # | + | # [[Схема алгоритма Диница]] |
| − | + | # '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | # ''' | ||
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах? | ## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах? | ||
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли? | ## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли? | ||
| Строка 577: | Строка 255: | ||
## Знаки неравенств | ## Знаки неравенств | ||
## Источники информации | ## Источники информации | ||
| − | # | + | # [[Алгоритм поиска блокирующего потока в ациклической сети]] |
| − | |||
| − | |||
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении | ## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении | ||
| − | # ''' | + | # '''!!!''' [[Метод проталкивания предпотока]] (7) |
| − | ## | + | ## Картиночки с резервуарами! |
| − | + | ## Источники информации | |
| − | + | ## Добавить см. также | |
| − | + | ## Дефисы заменить на тире | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | ## | ||
| − | ## | ||
| − | ## | ||
## Отформатировать псевдокоды | ## Отформатировать псевдокоды | ||
| − | # | + | # [[Алгоритм "поднять-в-начало"]] |
| − | + | # [[Теорема о декомпозиции]] | |
| − | + | # ''fixed'' [[Теорема о декомпозиционном барьере]] (3) | |
| − | |||
| − | |||
| − | # [[Теорема о декомпозиционном барьере]] (3) | ||
## Источники информации | ## Источники информации | ||
## Пояснить,почему такие константы используются | ## Пояснить,почему такие константы используются | ||
## Увеличить дроби | ## Увеличить дроби | ||
## А что из этой теоремы следует? | ## А что из этой теоремы следует? | ||
| − | # | + | # [[Циркуляция потока]] |
| − | # | + | # [[Алгоритм Каргера для нахождения минимального разреза]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== 11. Задача о потоке минимальной стоимости == | == 11. Задача о потоке минимальной стоимости == | ||
| − | # | + | # [[Поток минимальной стоимости]] |
| − | + | # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | |
| − | + | # ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5) | |
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5) | ||
## Интервики на декомпозицию | ## Интервики на декомпозицию | ||
## Знаки неравенств | ## Знаки неравенств | ||
## Источники информации | ## Источники информации | ||
| − | # | + | # [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] |
| − | |||
| − | |||
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5) | # '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5) | ||
## Написать и оформить так, чтобы не было чуши | ## Написать и оформить так, чтобы не было чуши | ||
| − | # [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5) | + | # ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5) |
## Взять задачи в шаблон | ## Взять задачи в шаблон | ||
## Оформить покрасивей и правильней | ## Оформить покрасивей и правильней | ||
| − | # | + | # [[Венгерский алгоритм решения задачи о назначениях]] |
| − | |||
| − | |||
| − | |||
Текущая версия на 19:15, 23 февраля 2017
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
Содержание
- 1 1. Основные определения теории графов
- 2 2. Связность в графах
- 3 3. Остовные деревья
- 4 4. Обходы графов
- 5 5. Укладки графов
- 6 6. Раскраски графов
- 7 7. Обход в глубину
- 8 8. Кратчайшие пути в графах
- 9 9. Задача о паросочетании
- 10 10. Задача о максимальном потоке
- 11 11. Задача о потоке минимальной стоимости
1. Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- fixed Теорема о существовании простого пути в случае существования пути (4)
- Алгоритм и предположение зря оформлены как псевдокод
- Добавить ссылок
- Заменить названия способов доказательств на конструктивное и неконструктивное
- Исправить ошибку в доказательстве построением
- Плохо, что картинка наплывает на заголовок — переделать
- Добавить в формулировку теоремы, что вершинно-простой путь
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- взяли Матрица инцидентности графа (4 или больше, зависит от свойств)
- Добавить свойства матрицы инцидентности с доказательствами
- Добавить ссылок в источники информации
- Англоязычные термины
- Оформить правильно источники информации
- Добавить См. также на матрицу смежности
- Добавить про списки смежности и их оформить тоже в таблички
- Циклическое пространство графа
- fixed Фундаментальные циклы графа (1)
- Источники информации нормально оформить
- Подписать получше картинку
- Заменить многоточия на \ldots
- Отформатировать по правилам
- fixed Дерево, эквивалентные определения (1)
- Англоязычные термины
- Пофиксить знаки неравенств
- Источники информации нормально оформить
- Оформить красиво доказательства
- Алгоритмы на деревьях
- fixed Дополнительный, самодополнительный граф (1)
- Англоязычные термины оформить правильно
- Заменить угловые скобки на \langle и \rangle
- Интервики
- Добавить ссылки в источники информации
- Шаблоном заменить тире
- Теоретико-множественные операции над графами
- Рёберное ядро (2)
- Добавить больше интервики в конспект
- В конце теоремы в доказательстве какая-то лажа
- Источники информации
- Оформить следствия красиво
- Факторизация графов
2. Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- fixed Теорема Менгера (0.5)
- убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
- Тире заменить на шаблон
- Можно добавить ссылок, оформить см. также по-другому
- Источники информации
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины (1.5)
- пункт "Определения" не нужен
- Изменить знаки неравенств в tex
- Не надо дублировать определения из другого конспекта
- Отформатировать псевдокод
- find_flow какой-то стрёмный
- Источники информации
- k-связность с маленькой буквы
- Добавить См. также на что-нибудь разумное
- Добавить см. также
3. Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- !!! Теорема Тарьяна (критерий минимальности остовного дерева) (5)
- Доказательство красиво оформить
- Заменить дефис на шаблон
- Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
- Почему ребро uv — единственное ребро, пересекающее разрез?
- Источники информации
- Знаки неравенств
- Категория
- !!! Алгоритм двух китайцев (7)
- Англоязычные термины оформить правильно
- Добавить определение покрывающего дерева
- Описать реализацию красиво
- Дефис заменить на тире
- Отформатировать псевдокод
- Доказать, почему не более V конденсаций
- Источники информации оформить правильно
- Доказать второе замечание
- Добавить отступы в описании примера
- 5ый пункт в описании алгоритма расписать чуть понятней
- Категория
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
4. Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- взяли Покрытие ребер графа путями (3)
- Какое-то мутное доказательства
- Алгоритм построения Эйлерова цикла (2)
- Какое-то мутное доказательство леммы про корректность алгоритма
- Произвольно вычерчиваемые из заданной вершины графы
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Теорема Поша
- Теорема Гуйя-Ури
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- !!! Теорема Гринберга (5)
- Пояснить переходы в теореме
- Внести пояснение в определение бонда
- И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
- Картинку сделать красивой
- взяли Турниры (6)
- Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
- Теорема Редеи-Камиона
5. Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- fixed Непланарность и (0.5)
- Исправить знаки неравенств
- Источники информации
- Константы в Tex
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Род, толщина, крупность, число скрещиваний
- Двойственный граф планарного графа
- Теорема Фари
- Гамма-алгоритм
6. Раскраски графов
- Раскраска графа
- fixed Двудольные графы и раскраска в 2 цвета (3)
- Англоязычные термины
- Убрать определение двудольного графа и сделать интервики на основной конспект
- Картинку двудольного графа перенести ниже, а то плохо смотрится
- Интервики
- Добавить, что можно ещё за проход в ширину проверить
- Оформить правильно источники информации и См. также
- Перенести см. также до источников информации, а ссылку заменить на интервики
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Верхние и нижние оценки хроматического числа
- Хроматическое число планарного графа
- Многочлен Татта
- Теория Рамсея (10)
- Тут вообще ад какой-то
7. Обход в глубину
- fixed Обход в глубину, цвета вершин (5)
- Англоязычные термины правильно оформить
- Отформатировать псевдокод
- Красивую картинку с цветными вершинами
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- fixed Использование обхода в глубину для поиска точек сочленения (4)
- Что-то картинки неудачно расположены
- Кривая структура у доказательства
- Отформатировать псевдокод
- Источники информации красиво оформить
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
8. Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
9. Задача о паросочетании
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Теорема Татта о существовании полного паросочетания
- !!! Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
- как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
- Декомпозиция Эдмондса-Галлаи
- взяли Задача об устойчивом паросочетании (все правки стоят 10 баллов)
- Переменные и константы в Tex
- Добавить сначала постановку задачи
- Кривая ссылка на паросочетание
- Дефисы на тире
- Определения выделять жирным
- Отформатировать псевдокоды
- Зачем-то списки в доказательствах лемм использованы
- Битая ссылка на соседей
- Надо бы доказать все леммы
- Оформить правильно источники информации
- И вообще всё оформить надо
10. Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- взяли Алоритм Эдмондса-Карпа (5)
- Полностью описать пример про грибок с картинками в конспекте
- Алгоритм масштабирования потока
- взяли Блокирующий поток (1)
- англоязычные термины
- ссылки на русскую и английскую википедию
- Добавить немного общей информации
- Расположить красиво картинки, чтобы не наезжали
- Схема алгоритма Диница
- fixed Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями (6)
- может, назвать остаточную сеть , как в предыдущих конспектах?
- "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
- В лемме в утверждении фигурирует поток , но дальше про него ничего нет. Зачем он?
- "Мы можем применить Лемму(2" — лемму 3, наверное?
- Дефисы на тире
- Знаки неравенств
- Источники информации
- Алгоритм поиска блокирующего потока в ациклической сети
- !!! (10) алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
- !!! Метод проталкивания предпотока (7)
- Картиночки с резервуарами!
- Источники информации
- Добавить см. также
- Дефисы заменить на тире
- Отформатировать псевдокоды
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- fixed Теорема о декомпозиционном барьере (3)
- Источники информации
- Пояснить,почему такие константы используются
- Увеличить дроби
- А что из этой теоремы следует?
- Циркуляция потока
- Алгоритм Каргера для нахождения минимального разреза
11. Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- fixed Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети (0.5)
- Интервики на декомпозицию
- Знаки неравенств
- Источники информации
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- !!! Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
- Написать и оформить так, чтобы не было чуши
- взяли Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0.5)
- Взять задачи в шаблон
- Оформить покрасивей и правильней
- Венгерский алгоритм решения задачи о назначениях
