748
правок
Изменения
→2 Связность в графах
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7)
== 31. Остовные деревья ==
=== Построение остовных деревьев ===
<ol>
# Категория
</ol>
== 2 Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]] 4
## разобраться с доказательством теоремы из 7 пунктов
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# [[Теорема Менгера]]
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
# [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
# [[Задача о динамической связности]]
== Обходы графов ==
=== 3 Эйлеровы графы ===
# [[Алгоритм построения Эйлерова цикла]] (2)
## Какое-то мутное доказательство леммы про корректность алгоритма
=== 4 Гамильтовы графы ===
<ol value="2">
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
</ol>
== 75. Обход в глубину ==# [[Обход в глубину, цвета вершин]] 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"
== 86. Кратчайшие пути в графах ==# [[Обход в ширину]]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 памяти в таблице про Европу
== 97. Задача о паросочетании ==
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]]0.5## поправить тех у "dfs"
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
== 108. Задача о максимальном потоке ==# [[Определение сети, потока]]0.5## добавить "см. также"# [[Разрез, лемма о потоке через разрез]] 0.5## добавить "см. также"## поправить тех для чисел # [[Дополняющая сеть, дополняющий путь]]0.5## добавить "см. также"# [[Лемма о сложении потоков]]0.5## добавить "см. также"# [[Теорема Форда-Фалкерсона]]0.5## исправить "\text{in}"# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]0.5## нормально расположить картинки# [[Алоритм Алгоритм Эдмондса-Карпа]] (0,25).5
## Добавить см также
# [[Алгоритм масштабирования потока]]
## Добавить немного общей информации
## Интервики
# [[Схема алгоритма Диница]]0.5## добавить "см. также"## поправить тех
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
# [[Алгоритм поиска блокирующего потока в ациклической сети]] (10)
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]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"## добавить "см. также"
== 119. Задача о потоке минимальной стоимости ==# [[Поток минимальной стоимости]]3## исправить замечания из обсуждения статьи<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]перенаправляется на "Поиск потока мин.стоимости...", который ниже есть --> # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] 0.5## добавить "см. также"## поправить тех сигм# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]0.5## поправить тех "G"
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
## Добавить см также
## Источники информации оформить нормально
# [[Венгерский алгоритм решения задачи о назначениях]]0.5## поправить тех## сделать wikitable
