Теория графов:Тикеты — различия между версиями
(→10. Задача о максимальном потоке) |
(→2 Связность в графах) |
||
| (не показано 29 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | + | == 1. Остовные деревья == |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
=== Построение остовных деревьев === | === Построение остовных деревьев === | ||
<ol> | <ol> | ||
| Строка 51: | Строка 8: | ||
<li> [[Алгоритм Краскала]] </li> | <li> [[Алгоритм Краскала]] </li> | ||
<li> [[Алгоритм Борувки]] </li> | <li> [[Алгоритм Борувки]] </li> | ||
| − | <li> [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] | + | <li> [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]</li> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Алгоритм двух китайцев]] (7) </li> | <li> [[Алгоритм двух китайцев]] (7) </li> | ||
# Англоязычные термины оформить правильно | # Англоязычные термины оформить правильно | ||
| Строка 73: | Строка 23: | ||
</ol> | </ol> | ||
| − | == | + | == 2 Связность в графах == |
| − | + | # [[Отношение связности, компоненты связности]] | |
| − | + | # [[Отношение реберной двусвязности]] | |
| − | + | # [[Отношение вершинной двусвязности]] | |
| − | + | # [[Точка сочленения, эквивалентные определения]] 4 | |
| − | + | ## разобраться с доказательством теоремы из 7 пунктов | |
| − | + | # [[Мост, эквивалентные определения]] | |
| − | </ | + | # [[Граф компонент реберной двусвязности]] |
| + | # [[Граф блоков-точек сочленения]] | ||
| + | # [[k-связность]] | ||
| + | # [[Теорема Менгера]] | ||
| + | # [[Теорема Менгера, альтернативное доказательство]] | ||
| + | # [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | ||
| + | # [[Задача о динамической связности оффлайн]]<tex>^\star</tex> | ||
| + | # [[Задача о динамической связности]] | ||
| + | |||
| + | == Обходы графов == | ||
| + | === 3 Эйлеровы графы === | ||
| − | + | # [[Алгоритм построения Эйлерова цикла]] (2) | |
| − | + | ## Какое-то мутное доказательство леммы про корректность алгоритма | |
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | # Какое-то мутное доказательство леммы про корректность алгоритма | ||
| − | |||
| − | |||
| − | === | + | === 4 Гамильтовы графы === |
| − | <ol | + | <ol value="2"> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li> | <li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ol> | </ol> | ||
| − | == 5. | + | == 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>") |
| − | # [[Алгоритм A*]] | + | ## добавить "см. также" |
| − | # [[Алгоритм D*]] | + | # [[Алгоритм Форда-Беллмана]] 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) | # [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7) | ||
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками | ## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | + | == 8. Задача о максимальном потоке == |
| − | # [[Определение сети, потока]] | + | # [[Определение сети, потока]] 0.5 |
| − | # [[Разрез, лемма о потоке через разрез]] | + | ## добавить "см. также" |
| − | # [[Дополняющая сеть, дополняющий путь]] | + | # [[Разрез, лемма о потоке через разрез]] 0.5 |
| − | # [[Лемма о сложении потоков]] | + | ## добавить "см. также" |
| − | # [[Теорема Форда-Фалкерсона]] | + | ## поправить тех для чисел |
| − | # [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | + | # [[Дополняющая сеть, дополняющий путь]] 0.5 |
| − | # | + | ## добавить "см. также" |
| − | ## | + | # [[Лемма о сложении потоков]] 0.5 |
| + | ## добавить "см. также" | ||
| + | # [[Теорема Форда-Фалкерсона]] 0.5 | ||
| + | ## исправить "\text{in}" | ||
| + | # [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] 0.5 | ||
| + | ## нормально расположить картинки | ||
| + | # [[Алгоритм Эдмондса-Карпа]] 0.5 | ||
| + | ## Добавить см также | ||
# [[Алгоритм масштабирования потока]] | # [[Алгоритм масштабирования потока]] | ||
| − | # | + | # [[Блокирующий поток]] (0,5) |
| − | |||
| − | |||
## Добавить немного общей информации | ## Добавить немного общей информации | ||
| − | ## | + | ## Интервики |
| − | # [[Схема алгоритма Диница]] | + | # [[Схема алгоритма Диница]] 0.5 |
| − | # | + | ## добавить "см. также" |
| − | + | ## поправить тех | |
| − | + | # [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] | |
| − | + | # [[Алгоритм поиска блокирующего потока в ациклической сети]] (10) | |
| − | + | ## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении | |
| − | + | # [[Метод проталкивания предпотока]] (7) | |
| − | |||
| − | |||
| − | # [[Алгоритм поиска блокирующего потока в ациклической сети]] | ||
| − | ## | ||
| − | # | ||
## Картиночки с резервуарами! | ## Картиночки с резервуарами! | ||
## Источники информации | ## Источники информации | ||
| Строка 212: | Строка 173: | ||
## Дефисы заменить на тире | ## Дефисы заменить на тире | ||
## Отформатировать псевдокоды | ## Отформатировать псевдокоды | ||
| − | # [[Алгоритм "поднять-в-начало"]] | + | # [[Алгоритм "поднять-в-начало"]] 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 | ||
Текущая версия на 16:33, 5 сентября 2019
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7)
Содержание
1. Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев (7)
- Англоязычные термины оформить правильно
- Добавить определение покрывающего дерева
- Описать реализацию красиво
- Дефис заменить на тире
- Отформатировать псевдокод
- Доказать, почему не более V конденсаций
- Источники информации оформить правильно
- Доказать второе замечание
- Добавить отступы в описании примера
- 5ый пункт в описании алгоритма расписать чуть понятней
- Категория
2 Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения 4
- разобраться с доказательством теоремы из 7 пунктов
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
- Задача о динамической связности оффлайн
- Задача о динамической связности
Обходы графов
3 Эйлеровы графы
- Алгоритм построения Эйлерова цикла (2)
- Какое-то мутное доказательство леммы про корректность алгоритма
4 Гамильтовы графы
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", "=="(хотя уже есть ), "Q = ")
- добавить "см. также"
- Алгоритм Форда-Беллмана 6
- поправить тех для чисел
- из s достижимы циклы отрицательного веса не существует кратчайших путей
- весь конспект бессвязный - не ясно что к чему и как относится. Нормально структурировать
- сделать доказательство первой леммы более содержательным
- пункт "Псевдокод" - бред почти полностью
- иногда 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
- не сравнимо с
- поправить тех
- Теорема о декомпозиции 0.5
- добавить "см. также"
- поправить "-" в псевдокоде
- Теорема о декомпозиционном барьере 1
- оформить следствие
- Циркуляция потока 0.5
- поправить тех
- добавить "см. также"
- Алгоритм Каргера для нахождения минимального разреза 3
- поправить сигму в определении веса разреза и определение множества там же
- поправить псевдокод (если возможно)
- поправить комментарий в псевдокоде
- теорема не утверждает "что вероятность получить правильный ответ ... очень мала". Нормально сформулировать
- - это как вообще?
- можно использовать без базы только в оценках
- заменить "/" на "\frac"
- добавить "см. также"
9. Задача о потоке минимальной стоимости
- Поток минимальной стоимости 3
- исправить замечания из обсуждения статьи
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети 0.5
- добавить "см. также"
- поправить тех сигм
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости 0.5
- поправить тех "G"
- Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
- Написать и оформить так, чтобы не было чуши
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0,5)
- Добавить см также
- Источники информации оформить нормально
- Венгерский алгоритм решения задачи о назначениях 0.5
- поправить тех
- сделать wikitable
