Просмотр исходного текста страницы Теория графов:Тикеты

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7)

== 1. Остовные деревья ==
=== Построение остовных деревьев ===
<ol>
<li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li>
<li>[[Алгоритм Прима]]</li>
<li> [[Алгоритм Краскала]] </li>
<li> [[Алгоритм Борувки]] </li>
<li> [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]</li>
<li> [[Алгоритм двух китайцев]] (7) </li>
# Англоязычные термины оформить правильно
# Добавить определение покрывающего дерева
# Описать реализацию красиво
# Дефис заменить на тире
# Отформатировать псевдокод
# Доказать, почему не более V конденсаций
# Источники информации оформить правильно
# Доказать второе замечание
# Добавить отступы в описании примера
# 5ый пункт в описании алгоритма расписать чуть понятней
# Категория
</ol>

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

== Обходы графов ==
=== 3 Эйлеровы графы ===

# [[Алгоритм построения Эйлерова цикла]] (2)
## Какое-то мутное доказательство леммы про корректность алгоритма

=== 4 Гамильтовы графы ===
<ol value="2">
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
</ol>

== 5. Обход в глубину ==
# [[Обход в глубину, цвета вершин]] 1
## поправить тех (цифры и аргументы функций)
## разделить функции в псевдокоде
## убрать из названия конспекта "цвета вершин"
## Заменить "NILL" на что-то более подходящее
# [[Лемма о белых путях]] 1
## поправить тех (названия функций)
## добавить "см. также"
## "...есть как белые, так и черные, и серые вершины" - бред
## источники информации
# [[Использование обхода в глубину для проверки связности]] 2
## СНМ не к месту
## источники информации
# [[Использование обхода в глубину для поиска цикла]]  3
## добавить реализацию для неориентированного графа
# [[Использование обхода в глубину для топологической сортировки]] 3
## поправить теорему в "постановке задачи"
## поправить тех для dfs-ов
## поправить тех в псевдокоде
## описать в псевдокоде ans, visited
## пример отнести к применениям
# [[Использование обхода в глубину для поиска компонент сильной связности]] 2
## тех для чисел
## максимально перевести объяснения в коде на русском в псевдокод
## "см. также"
# [[Использование обхода в глубину для поиска точек сочленения]] 2
## разделить функции в псевдокоде
## добавить комментарии к псевдокоду
# [[Построение компонент вершинной двусвязности]] 0.5
## поправить тех (для "dfs", "paint")
# [[Использование обхода в глубину для поиска мостов]] 1
## шаблон "задача"
## 2 одинаковых "enter(x)" в описании ret(v)
## "enter" и "ret" (как функции) - в \mathrm
# [[Построение компонент реберной двусвязности]] 0.5
## поправить тех для "dfs", "paint"

== 6. Кратчайшие пути в графах ==
# [[Обход в ширину]] 5
## исправить речевые ошибки в описании
## поправить тех
## 0-1 bfs переписать
## нормально сформулировать доказательство 1ого утверждения
## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")
## добавить "см. также" 
# [[Алгоритм Форда-Беллмана]] 6
## поправить тех для чисел
## из s достижимы циклы отрицательного веса <tex>\nRightarrow</tex> не существует кратчайших путей
## весь конспект бессвязный - не ясно что к чему и как относится. Нормально структурировать
## сделать доказательство первой леммы более содержательным
## пункт "Псевдокод" - бред почти полностью
## иногда w(x, y), иногда w(xy) - исправить; обычно написано в неверном порядке
## систематизировать комментарии в псевдокоде (добавить, сделать содержательными)
## добавить "см. также"
# [[Алгоритм Дейкстры]] 0.5
## в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи 
## добавить "см. также"
# [[Алгоритм Флойда]] 1.5
## поправить нерабочий тех
## переписать, чтобы индексация d была везде через "[]"
## комментарии в псевдокоде несодержательны
# [[Алгоритм Джонсона]] 0.5
## поправить псевдокод
# [[Алгоритм Левита]] 3
## избавиться от тернарного оператора
## поправить тех min
## формализовать (хотя бы частично) доказательство лемм (возможно, добавить еще)
## про реализацию через дек внести ясность
## утверждение о сложности обернуть в соответствующих шаблон
# [[Алгоритм A*]] 5
## теорема доказана не полностью
# [[Алгоритм D*]] 4
## ссылки на доказательства заменить на доказательства
## использование g(s) до ее определения
## описание g(s) очень мутное
## "исходящие" и "входящие" вершины - правильно назвать
## в определении rhs не хватает скобок
## описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся
## добавить "см. также"
# [[Эвристики для поиска кратчайших путей]] 0.5
## поправить тех
## вряд ли 16MB памяти в таблице про Европу

== 7. Задача о паросочетании ==
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]] 0.5
## поправить тех у "dfs"
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками

== 8. Задача о максимальном потоке ==
# [[Определение сети, потока]] 0.5
## добавить "см. также"
# [[Разрез, лемма о потоке через разрез]] 0.5
## добавить "см. также"
## поправить тех для чисел 
# [[Дополняющая сеть, дополняющий путь]] 0.5
## добавить "см. также"
# [[Лемма о сложении потоков]] 0.5
## добавить "см. также"
# [[Теорема Форда-Фалкерсона]] 0.5
## исправить "\text{in}"
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] 0.5
## нормально расположить картинки
# [[Алгоритм Эдмондса-Карпа]] 0.5
## Добавить см также
# [[Алгоритм масштабирования потока]]
# [[Блокирующий поток]] (0,5)
## Добавить немного общей информации
## Интервики
# [[Схема алгоритма Диница]] 0.5
## добавить "см. также"
## поправить тех
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] 
# [[Алгоритм поиска блокирующего потока в ациклической сети]] (10)
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении 
# [[Метод проталкивания предпотока]] (7)
## Картиночки с резервуарами!
## Источники информации
## Добавить см. также
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]] 2
## <tex>O(V^3)</tex> не сравнимо с <tex>O(V^2E)</tex>
## поправить тех
# [[Теорема о декомпозиции]] 0.5
## добавить "см. также"
## поправить "-" в псевдокоде
# [[Теорема о декомпозиционном барьере]] 1
## оформить следствие
# [[Циркуляция потока]] 0.5
## поправить тех
## добавить "см. также"
# [[Алгоритм Каргера для нахождения минимального разреза]] 3
## поправить сигму в определении веса разреза и определение множества там же
## поправить псевдокод (если возможно)
## поправить комментарий в псевдокоде 
## теорема не утверждает "что вероятность получить правильный ответ ... очень мала". Нормально сформулировать
## <tex>e^{count⋅(−\frac{2}{n^2})}=e^{−2ln(n)}</tex> - это как вообще?
## <tex>\log</tex> можно использовать без базы только в оценках <tex>O(...)</tex>
## заменить "/" на "\frac"
## добавить "см. также"

== 9. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]] 3
## исправить замечания из обсуждения статьи
<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] перенаправляется на "Поиск потока мин.стоимости...", который ниже есть --> 
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] 0.5
## добавить "см. также"
## поправить тех сигм
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] 0.5
## поправить тех "G"
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
## Добавить см также
## Источники информации оформить нормально
# [[Венгерский алгоритм решения задачи о назначениях]] 0.5
## поправить тех
## сделать wikitable