Изменения

=== 2 3 Эйлеровы графы ===

=== 3 4 Гамильтовы графы ===

== 45. Обход в глубину ==# [[Обход в глубину, цвета вершин]] 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"

== 56. Кратчайшие пути в графах ==# [[Обход в ширину]]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 памяти в таблице про Европу

== 67. Задача о паросочетании ==

# [[Алгоритм Куна для поиска максимального паросочетания]]0.5## поправить тех у "dfs"

== 78. Задача о максимальном потоке ==# [[Определение сети, потока]]0.5## добавить "см. также"# [[Разрез, лемма о потоке через разрез]] 0.5## добавить "см. также"## поправить тех для чисел # [[Дополняющая сеть, дополняющий путь]]0.5## добавить "см. также"# [[Лемма о сложении потоков]]0.5## добавить "см. также"# [[Теорема Форда-Фалкерсона]]0.5## исправить "\text{in}"# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]0.5## нормально расположить картинки# [[Алоритм Алгоритм Эдмондса-Карпа]] (0,25).5

# [[Схема алгоритма Диница]]0.5## добавить "см. также"## поправить тех

# [[Алгоритм "поднять-в-начало"]]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"## добавить "см. также"

== 89. Задача о потоке минимальной стоимости ==# [[Поток минимальной стоимости]]3## исправить замечания из обсуждения статьи<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]перенаправляется на "Поиск потока мин.стоимости...", который ниже есть --> # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] 0.5## добавить "см. также"## поправить тех сигм# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]0.5## поправить тех "G"

# [[Венгерский алгоритм решения задачи о назначениях]]0.5## поправить тех## сделать wikitable