Теория графов:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎7. Задача о максимальном потоке)
(→‎2 Связность в графах)
 
(не показано 10 промежуточных версий 2 участников)
Строка 22: Строка 22:
 
# Категория
 
# Категория
 
</ol>
 
</ol>
 +
 +
== 2 Связность в графах ==
 +
# [[Отношение связности, компоненты связности]]
 +
# [[Отношение реберной двусвязности]]
 +
# [[Отношение вершинной двусвязности]]
 +
# [[Точка сочленения, эквивалентные определения]] 4
 +
## разобраться с доказательством теоремы из 7 пунктов
 +
# [[Мост, эквивалентные определения]]
 +
# [[Граф компонент реберной двусвязности]]
 +
# [[Граф блоков-точек сочленения]]
 +
# [[k-связность]]
 +
# [[Теорема Менгера]]
 +
# [[Теорема Менгера, альтернативное доказательство]]
 +
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
# [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 +
# [[Задача о динамической связности]]
  
 
== Обходы графов ==
 
== Обходы графов ==
−
=== 2 Эйлеровы графы ===
+
=== 3 Эйлеровы графы ===
  
 
# [[Алгоритм построения Эйлерова цикла]] (2)
 
# [[Алгоритм построения Эйлерова цикла]] (2)
 
## Какое-то мутное доказательство леммы про корректность алгоритма
 
## Какое-то мутное доказательство леммы про корректность алгоритма
  
−
=== 3 Гамильтовы графы ===
+
=== 4 Гамильтовы графы ===
 
<ol value="2">
 
<ol value="2">
 
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
 
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
 
</ol>
 
</ol>
  
−
== 4. Обход в глубину ==
+
== 5. Обход в глубину ==
−
# [[Обход в глубину, цвета вершин]]  
+
# [[Обход в глубину, цвета вершин]] 1
 
## поправить тех (цифры и аргументы функций)
 
## поправить тех (цифры и аргументы функций)
 
## разделить функции в псевдокоде
 
## разделить функции в псевдокоде
 
## убрать из названия конспекта "цвета вершин"
 
## убрать из названия конспекта "цвета вершин"
 
## Заменить "NILL" на что-то более подходящее
 
## Заменить "NILL" на что-то более подходящее
−
# [[Лемма о белых путях]]
+
# [[Лемма о белых путях]] 1
 
## поправить тех (названия функций)
 
## поправить тех (названия функций)
 
## добавить "см. также"
 
## добавить "см. также"
 
## "...есть как белые, так и черные, и серые вершины" - бред
 
## "...есть как белые, так и черные, и серые вершины" - бред
 
## источники информации
 
## источники информации
−
# [[Использование обхода в глубину для проверки связности]]
+
# [[Использование обхода в глубину для проверки связности]] 2
 
## СНМ не к месту
 
## СНМ не к месту
 
## источники информации
 
## источники информации
−
# [[Использование обхода в глубину для поиска цикла]]
+
# [[Использование обхода в глубину для поиска цикла]] 3
 
## добавить реализацию для неориентированного графа
 
## добавить реализацию для неориентированного графа
−
# [[Использование обхода в глубину для топологической сортировки]]
+
# [[Использование обхода в глубину для топологической сортировки]] 3
 
## поправить теорему в "постановке задачи"
 
## поправить теорему в "постановке задачи"
 
## поправить тех для dfs-ов
 
## поправить тех для dfs-ов
Строка 56: Строка 72:
 
## описать в псевдокоде ans, visited
 
## описать в псевдокоде ans, visited
 
## пример отнести к применениям
 
## пример отнести к применениям
−
# [[Использование обхода в глубину для поиска компонент сильной связности]]
+
# [[Использование обхода в глубину для поиска компонент сильной связности]] 2
 
## тех для чисел
 
## тех для чисел
 
## максимально перевести объяснения в коде на русском в псевдокод
 
## максимально перевести объяснения в коде на русском в псевдокод
 
## "см. также"
 
## "см. также"
−
# [[Использование обхода в глубину для поиска точек сочленения]]
+
# [[Использование обхода в глубину для поиска точек сочленения]] 2
 
## разделить функции в псевдокоде
 
## разделить функции в псевдокоде
 
## добавить комментарии к псевдокоду
 
## добавить комментарии к псевдокоду
−
# [[Построение компонент вершинной двусвязности]]
+
# [[Построение компонент вершинной двусвязности]] 0.5
 
## поправить тех (для "dfs", "paint")
 
## поправить тех (для "dfs", "paint")
−
# [[Использование обхода в глубину для поиска мостов]]
+
# [[Использование обхода в глубину для поиска мостов]] 1
 
## шаблон "задача"
 
## шаблон "задача"
 
## 2 одинаковых "enter(x)" в описании ret(v)
 
## 2 одинаковых "enter(x)" в описании ret(v)
 
## "enter" и "ret" (как функции) - в \mathrm
 
## "enter" и "ret" (как функции) - в \mathrm
−
# [[Построение компонент реберной двусвязности]]
+
# [[Построение компонент реберной двусвязности]] 0.5
 
## поправить тех для "dfs", "paint"
 
## поправить тех для "dfs", "paint"
  
−
== 5. Кратчайшие пути в графах ==
+
== 6. Кратчайшие пути в графах ==
−
# [[Обход в ширину]]
+
# [[Обход в ширину]] 5
 
## исправить речевые ошибки в описании
 
## исправить речевые ошибки в описании
 
## поправить тех
 
## поправить тех
Строка 80: Строка 96:
 
## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")
 
## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")
 
## добавить "см. также"  
 
## добавить "см. также"  
−
# [[Алгоритм Форда-Беллмана]]
+
# [[Алгоритм Форда-Беллмана]] 6
 
## поправить тех для чисел
 
## поправить тех для чисел
 
## из s достижимы циклы отрицательного веса <tex>\nRightarrow</tex> не существует кратчайших путей
 
## из s достижимы циклы отрицательного веса <tex>\nRightarrow</tex> не существует кратчайших путей
Строка 92: Строка 108:
 
## в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи  
 
## в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи  
 
## добавить "см. также"
 
## добавить "см. также"
−
# [[Алгоритм Флойда]]
+
# [[Алгоритм Флойда]] 1.5
 
## поправить нерабочий тех
 
## поправить нерабочий тех
 
## переписать, чтобы индексация d была везде через "[]"
 
## переписать, чтобы индексация d была везде через "[]"
 
## комментарии в псевдокоде несодержательны
 
## комментарии в псевдокоде несодержательны
−
# [[Алгоритм Джонсона]]
+
# [[Алгоритм Джонсона]] 0.5
 
## поправить псевдокод
 
## поправить псевдокод
−
# [[Алгоритм Левита]]
+
# [[Алгоритм Левита]] 3
 
## избавиться от тернарного оператора
 
## избавиться от тернарного оператора
 
## поправить тех min
 
## поправить тех min
Строка 104: Строка 120:
 
## про реализацию через дек внести ясность
 
## про реализацию через дек внести ясность
 
## утверждение о сложности обернуть в соответствующих шаблон
 
## утверждение о сложности обернуть в соответствующих шаблон
−
# [[Алгоритм A*]]
+
# [[Алгоритм A*]] 5
 
## теорема доказана не полностью
 
## теорема доказана не полностью
−
# [[Алгоритм D*]]
+
# [[Алгоритм D*]] 4
 
## ссылки на доказательства заменить на доказательства
 
## ссылки на доказательства заменить на доказательства
 
## использование g(s) до ее определения
 
## использование g(s) до ее определения
Строка 114: Строка 130:
 
## описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся
 
## описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся
 
## добавить "см. также"
 
## добавить "см. также"
−
# [[Эвристики для поиска кратчайших путей]]
+
# [[Эвристики для поиска кратчайших путей]] 0.5
 
## поправить тех
 
## поправить тех
 
## вряд ли 16MB памяти в таблице про Европу
 
## вряд ли 16MB памяти в таблице про Европу
  
−
== 6. Задача о паросочетании ==
+
== 7. Задача о паросочетании ==
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
−
# [[Алгоритм Куна для поиска максимального паросочетания]]
+
# [[Алгоритм Куна для поиска максимального паросочетания]] 0.5
 
## поправить тех у "dfs"
 
## поправить тех у "dfs"
 
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
  
−
== 7. Задача о максимальном потоке ==
+
== 8. Задача о максимальном потоке ==
−
# [[Определение сети, потока]]
+
# [[Определение сети, потока]] 0.5
 
## добавить "см. также"
 
## добавить "см. также"
−
# [[Разрез, лемма о потоке через разрез]]
+
# [[Разрез, лемма о потоке через разрез]] 0.5
 
## добавить "см. также"
 
## добавить "см. также"
 
## поправить тех для чисел  
 
## поправить тех для чисел  
−
# [[Дополняющая сеть, дополняющий путь]]
+
# [[Дополняющая сеть, дополняющий путь]] 0.5
 
## добавить "см. также"
 
## добавить "см. также"
−
# [[Лемма о сложении потоков]]
+
# [[Лемма о сложении потоков]] 0.5
 
## добавить "см. также"
 
## добавить "см. также"
−
# [[Теорема Форда-Фалкерсона]]
+
# [[Теорема Форда-Фалкерсона]] 0.5
 
## исправить "\text{in}"
 
## исправить "\text{in}"
−
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
+
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] 0.5
 
## нормально расположить картинки
 
## нормально расположить картинки
−
# [[Алгоритм Эдмондса-Карпа]] (0,25)
+
# [[Алгоритм Эдмондса-Карпа]] 0.5
 
## Добавить см также
 
## Добавить см также
 
# [[Алгоритм масштабирования потока]]
 
# [[Алгоритм масштабирования потока]]
Строка 145: Строка 161:
 
## Добавить немного общей информации
 
## Добавить немного общей информации
 
## Интервики
 
## Интервики
−
# [[Схема алгоритма Диница]]
+
# [[Схема алгоритма Диница]] 0.5
 
## добавить "см. также"
 
## добавить "см. также"
 
## поправить тех
 
## поправить тех
Строка 157: Строка 173:
 
## Дефисы заменить на тире
 
## Дефисы заменить на тире
 
## Отформатировать псевдокоды
 
## Отформатировать псевдокоды
−
# [[Алгоритм "поднять-в-начало"]]
+
# [[Алгоритм "поднять-в-начало"]] 2
 
## <tex>O(V^3)</tex> не сравнимо с <tex>O(V^2E)</tex>
 
## <tex>O(V^3)</tex> не сравнимо с <tex>O(V^2E)</tex>
 
## поправить тех
 
## поправить тех
−
# [[Теорема о декомпозиции]]
+
# [[Теорема о декомпозиции]] 0.5
 
## добавить "см. также"
 
## добавить "см. также"
 
## поправить "-" в псевдокоде
 
## поправить "-" в псевдокоде
−
# [[Теорема о декомпозиционном барьере]]
+
# [[Теорема о декомпозиционном барьере]] 1
 
## оформить следствие
 
## оформить следствие
−
# [[Циркуляция потока]]
+
# [[Циркуляция потока]] 0.5
 
## поправить тех
 
## поправить тех
 
## добавить "см. также"
 
## добавить "см. также"
−
# [[Алгоритм Каргера для нахождения минимального разреза]]
+
# [[Алгоритм Каргера для нахождения минимального разреза]] 3
 
## поправить сигму в определении веса разреза и определение множества там же
 
## поправить сигму в определении веса разреза и определение множества там же
 
## поправить псевдокод (если возможно)
 
## поправить псевдокод (если возможно)
Строка 178: Строка 194:
 
## добавить "см. также"
 
## добавить "см. также"
  
−
== 8. Задача о потоке минимальной стоимости ==
+
== 9. Задача о потоке минимальной стоимости ==
 
# [[Поток минимальной стоимости]] 3
 
# [[Поток минимальной стоимости]] 3
 
## исправить замечания из обсуждения статьи
 
## исправить замечания из обсуждения статьи
−
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
+
<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] перенаправляется на "Поиск потока мин.стоимости...", который ниже есть -->
−
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]  
+
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] 0.5
−
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
+
## добавить "см. также"
−
# взяли [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
+
## поправить тех сигм
 +
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] 0.5
 +
## поправить тех "G"
 +
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
 
## Написать и оформить так, чтобы не было чуши
 
## Написать и оформить так, чтобы не было чуши
 
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
 
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
 
## Добавить см также
 
## Добавить см также
 
## Источники информации оформить нормально
 
## Источники информации оформить нормально
−
# [[Венгерский алгоритм решения задачи о назначениях]]
+
# [[Венгерский алгоритм решения задачи о назначениях]] 0.5
 +
## поправить тех
 +
## сделать wikitable

Текущая версия на 16:33, 5 сентября 2019

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

1. Остовные деревья

Построение остовных деревьев

  1. Остовные деревья: определения, лемма о безопасном ребре
  2. Алгоритм Прима
  3. Алгоритм Краскала
  4. Алгоритм Борувки
  5. Теорема Тарьяна (критерий минимальности остовного дерева)
  6. Алгоритм двух китайцев (7)
    1. Англоязычные термины оформить правильно
    2. Добавить определение покрывающего дерева
    3. Описать реализацию красиво
    4. Дефис заменить на тире
    5. Отформатировать псевдокод
    6. Доказать, почему не более V конденсаций
    7. Источники информации оформить правильно
    8. Доказать второе замечание
    9. Добавить отступы в описании примера
    10. 5ый пункт в описании алгоритма расписать чуть понятней
    11. Категория

2 Связность в графах

  1. Отношение связности, компоненты связности
  2. Отношение реберной двусвязности
  3. Отношение вершинной двусвязности
  4. Точка сочленения, эквивалентные определения 4
    1. разобраться с доказательством теоремы из 7 пунктов
  5. Мост, эквивалентные определения
  6. Граф компонент реберной двусвязности
  7. Граф блоков-точек сочленения
  8. k-связность
  9. Теорема Менгера
  10. Теорема Менгера, альтернативное доказательство
  11. Вершинная, реберная связность, связь между ними и минимальной степенью вершины
  12. Задача о динамической связности оффлайн[math]^\star[/math]
  13. Задача о динамической связности

Обходы графов

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

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

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

  1. Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

5. Обход в глубину

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

6. Кратчайшие пути в графах

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

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

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

8. Задача о максимальном потоке

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

9. Задача о потоке минимальной стоимости

  1. Поток минимальной стоимости 3
    1. исправить замечания из обсуждения статьи
  2. Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети 0.5
    1. добавить "см. также"
    2. поправить тех сигм
  3. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости 0.5
    1. поправить тех "G"
  4. Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
    1. Написать и оформить так, чтобы не было чуши
  5. Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0,5)
    1. Добавить см также
    2. Источники информации оформить нормально
  6. Венгерский алгоритм решения задачи о назначениях 0.5
    1. поправить тех
    2. сделать wikitable
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_графов:Тикеты&oldid=71757»