748
правок
Изменения
Новая страница: «== 1. Основные определения теории графов == # [[Основные определения теории графов|Основные ...»
== 1. Основные определения теории графов ==
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
# [[Лемма о рукопожатиях]]
# ''fixed'' [[Теорема о существовании простого пути в случае существования пути]] (4)
## Алгоритм и предположение зря оформлены как псевдокод
## Добавить ссылок
## Заменить названия способов доказательств на конструктивное и неконструктивное
## Исправить ошибку в доказательстве построением
## Плохо, что картинка наплывает на заголовок {{---}} переделать
## Добавить в формулировку теоремы, что вершинно-простой путь
# [[Теорема о существовании простого цикла в случае существования цикла]]
# [[Матрица смежности графа]]
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Добавить ссылок в источники информации
## Англоязычные термины
## Оформить правильно источники информации
## Добавить См. также на матрицу смежности
## Добавить про списки смежности и их оформить тоже в таблички
# [[Циклическое пространство графа]]
# ''fixed'' [[Фундаментальные циклы графа]] (1)
## Источники информации нормально оформить
## Подписать получше картинку
## Заменить многоточия на \ldots
## Отформатировать по правилам
# ''fixed'' [[Дерево, эквивалентные определения]] (1)
## Англоязычные термины
## Пофиксить знаки неравенств
## Источники информации нормально оформить
## Оформить красиво доказательства
# [[Алгоритмы на деревьях]]
# ''fixed'' [[Дополнительный, самодополнительный граф]] (1)
## Англоязычные термины оформить правильно
## Заменить угловые скобки на \langle и \rangle
## Интервики
## Добавить ссылки в источники информации
## Шаблоном заменить тире
# [[Теоретико-множественные операции над графами]]
# [[Рёберное ядро]] (2)
## Добавить больше интервики в конспект
## В конце теоремы в доказательстве какая-то лажа
## Источники информации
## Оформить следствия красиво
# [[Факторизация графов]]
== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]]
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# ''fixed'' [[Теорема Менгера]] (0.5)
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
## Тире заменить на шаблон
## Можно добавить ссылок, оформить см. также по-другому
## Источники информации
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## пункт "Определения" не нужен
## Изменить знаки неравенств в tex
## Не надо дублировать определения из другого конспекта
## Отформатировать псевдокод
## find_flow какой-то стрёмный
## Источники информации
## k-связность с маленькой буквы
## Добавить См. также на что-нибудь разумное
## Добавить см. также
== 3. Остовные деревья ==
=== Построение остовных деревьев ===
<ol>
<li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li>
<li>[[Алгоритм Прима]]</li>
<li> [[Алгоритм Краскала]] </li>
<li> [[Алгоритм Борувки]] </li>
<li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li>
# Доказательство красиво оформить
# Заменить дефис на шаблон
# Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
# Почему ребро uv {{---}} единственное ребро, пересекающее разрез?
# Источники информации
# Знаки неравенств
# Категория
<li> '''!!!''' [[Алгоритм двух китайцев]] (7) </li>
# Англоязычные термины оформить правильно
# Добавить определение покрывающего дерева
# Описать реализацию красиво
# Дефис заменить на тире
# Отформатировать псевдокод
# Доказать, почему не более V конденсаций
# Источники информации оформить правильно
# Доказать второе замечание
# Добавить отступы в описании примера
# 5ый пункт в описании алгоритма расписать чуть понятней
# Категория
</ol>
=== Свойства остовных деревьев ===
<ol>
<li value="7">[[Матрица Кирхгофа]]</li>
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
<li> [[Количество помеченных деревьев]] </li>
<li> [[Коды Прюфера]] </li>
</ol>
== 4. Обходы графов ==
=== Эйлеровы графы ===
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li>
# Какое-то мутное доказательства
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
# Какое-то мутное доказательство леммы про корректность алгоритма
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
</ol>
=== Гамильтоновы графы ===
<ol>
<li value="5"> [[Гамильтоновы графы]] </li>
<li> [[Теорема Хватала]] </li>
<li> [[Теорема Дирака]] </li>
<li> [[Теорема Оре]] </li>
<li> [[Теорема Поша]]</li>
<li> [[Теорема Гуйя-Ури]] </li>
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Пояснить переходы в теореме
# Внести пояснение в определение бонда
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
# Картинку сделать красивой
<li> '''взяли''' [[Турниры]] (6) </li>
# Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
<li> [[Теорема Редеи-Камиона]] </li>
</ol>
== 5. Укладки графов ==
# [[Укладка графа на плоскости]]
# [[Формула Эйлера]]
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
## Исправить знаки неравенств
## Источники информации
## Константы в Tex
# [[Укладка дерева]]
# [[Укладка графа с планарными компонентами реберной двусвязности]]
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
# [[Теорема Понтрягина-Куратовского]]
# [[Род, толщина, крупность, число скрещиваний]]
# [[Двойственный граф планарного графа]]
# [[Теорема Фари]]
# [[Гамма-алгоритм]]
== 6. Раскраски графов ==
# [[Раскраска графа]]
# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)
## Англоязычные термины
## Убрать определение двудольного графа и сделать интервики на основной конспект
## Картинку двудольного графа перенести ниже, а то плохо смотрится
## Интервики
## Добавить, что можно ещё за проход в ширину проверить
## Оформить правильно источники информации и См. также
## Перенести см. также до источников информации, а ссылку заменить на интервики
# [[Хроматический многочлен]]
# [[Формула Зыкова]]
# [[Формула Уитни]]
# [[Теорема Брукса]]
# [[Верхние и нижние оценки хроматического числа]]
# [[Хроматическое число планарного графа]]
# [[Многочлен Татта]]
# [[Теория Рамсея]] ('''10''')
## Тут вообще ад какой-то
== 7. Обход в глубину ==
# '''fixed''' [[Обход в глубину, цвета вершин]] (5)
## Англоязычные термины правильно оформить
## Отформатировать псевдокод
## Красивую картинку с цветными вершинами
# [[Лемма о белых путях]]
# [[Использование обхода в глубину для проверки связности]]
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
# [[Использование обхода в глубину для топологической сортировки]]
# [[Использование обхода в глубину для поиска компонент сильной связности]]
# ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4)
## Что-то картинки неудачно расположены
## Кривая структура у доказательства
## Отформатировать псевдокод
## Источники информации красиво оформить
# [[Построение компонент вершинной двусвязности]]
# [[Использование обхода в глубину для поиска мостов]]
# [[Построение компонент реберной двусвязности]]
== 8. Кратчайшие пути в графах ==
# [[Обход в ширину]]
# [[Алгоритм Форда-Беллмана]]
# [[Алгоритм Дейкстры]]
# [[Алгоритм Флойда]]
# [[Алгоритм Джонсона]]
# [[Алгоритм Левита]]
# [[Алгоритм A*]]
# [[Алгоритм D*]]
# [[Эвристики для поиска кратчайших путей]]
== 9. Задача о паросочетании ==
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]]
# [[Теорема Холла]]
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
# [[Связь вершинного покрытия и независимого множества]]
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# [[Теорема Татта о существовании полного паросочетания]]
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
# [[Декомпозиция Эдмондса-Галлаи]]
# '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
## Переменные и константы в Tex
## Добавить сначала постановку задачи
## Кривая ссылка на паросочетание
## Дефисы на тире
## Определения выделять жирным
## Отформатировать псевдокоды
## Зачем-то списки в доказательствах лемм использованы
## Битая ссылка на соседей
## Надо бы доказать все леммы
## Оформить правильно источники информации
## И вообще всё оформить надо
== 10. Задача о максимальном потоке ==
# [[Определение сети, потока]]
# [[Разрез, лемма о потоке через разрез]]
# [[Дополняющая сеть, дополняющий путь]]
# [[Лемма о сложении потоков]]
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
# '''взяли''' [[Алоритм Эдмондса-Карпа]] (5)
## Полностью описать пример про грибок с картинками в конспекте
# [[Алгоритм масштабирования потока]]
# ''взяли'' [[Блокирующий поток]] (1)
## англоязычные термины
## ссылки на русскую и английскую википедию
## Добавить немного общей информации
## Расположить красиво картинки, чтобы не наезжали
# [[Схема алгоритма Диница]]
# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
## "Мы можем применить Лемму(2" — лемму 3, наверное?
## Дефисы на тире
## Знаки неравенств
## Источники информации
# [[Алгоритм поиска блокирующего потока в ациклической сети]]
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# '''!!!''' [[Метод проталкивания предпотока]] (7)
## Картиночки с резервуарами!
## Источники информации
## Добавить см. также
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]
# [[Теорема о декомпозиции]]
# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)
## Источники информации
## Пояснить,почему такие константы используются
## Увеличить дроби
## А что из этой теоремы следует?
# [[Циркуляция потока]]
# [[Алгоритм Каргера для нахождения минимального разреза]]
== 11. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]]
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
## Интервики на декомпозицию
## Знаки неравенств
## Источники информации
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)
## Взять задачи в шаблон
## Оформить покрасивей и правильней
# [[Венгерский алгоритм решения задачи о назначениях]]
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
# [[Лемма о рукопожатиях]]
# ''fixed'' [[Теорема о существовании простого пути в случае существования пути]] (4)
## Алгоритм и предположение зря оформлены как псевдокод
## Добавить ссылок
## Заменить названия способов доказательств на конструктивное и неконструктивное
## Исправить ошибку в доказательстве построением
## Плохо, что картинка наплывает на заголовок {{---}} переделать
## Добавить в формулировку теоремы, что вершинно-простой путь
# [[Теорема о существовании простого цикла в случае существования цикла]]
# [[Матрица смежности графа]]
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Добавить ссылок в источники информации
## Англоязычные термины
## Оформить правильно источники информации
## Добавить См. также на матрицу смежности
## Добавить про списки смежности и их оформить тоже в таблички
# [[Циклическое пространство графа]]
# ''fixed'' [[Фундаментальные циклы графа]] (1)
## Источники информации нормально оформить
## Подписать получше картинку
## Заменить многоточия на \ldots
## Отформатировать по правилам
# ''fixed'' [[Дерево, эквивалентные определения]] (1)
## Англоязычные термины
## Пофиксить знаки неравенств
## Источники информации нормально оформить
## Оформить красиво доказательства
# [[Алгоритмы на деревьях]]
# ''fixed'' [[Дополнительный, самодополнительный граф]] (1)
## Англоязычные термины оформить правильно
## Заменить угловые скобки на \langle и \rangle
## Интервики
## Добавить ссылки в источники информации
## Шаблоном заменить тире
# [[Теоретико-множественные операции над графами]]
# [[Рёберное ядро]] (2)
## Добавить больше интервики в конспект
## В конце теоремы в доказательстве какая-то лажа
## Источники информации
## Оформить следствия красиво
# [[Факторизация графов]]
== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]]
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# ''fixed'' [[Теорема Менгера]] (0.5)
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
## Тире заменить на шаблон
## Можно добавить ссылок, оформить см. также по-другому
## Источники информации
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## пункт "Определения" не нужен
## Изменить знаки неравенств в tex
## Не надо дублировать определения из другого конспекта
## Отформатировать псевдокод
## find_flow какой-то стрёмный
## Источники информации
## k-связность с маленькой буквы
## Добавить См. также на что-нибудь разумное
## Добавить см. также
== 3. Остовные деревья ==
=== Построение остовных деревьев ===
<ol>
<li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li>
<li>[[Алгоритм Прима]]</li>
<li> [[Алгоритм Краскала]] </li>
<li> [[Алгоритм Борувки]] </li>
<li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li>
# Доказательство красиво оформить
# Заменить дефис на шаблон
# Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
# Почему ребро uv {{---}} единственное ребро, пересекающее разрез?
# Источники информации
# Знаки неравенств
# Категория
<li> '''!!!''' [[Алгоритм двух китайцев]] (7) </li>
# Англоязычные термины оформить правильно
# Добавить определение покрывающего дерева
# Описать реализацию красиво
# Дефис заменить на тире
# Отформатировать псевдокод
# Доказать, почему не более V конденсаций
# Источники информации оформить правильно
# Доказать второе замечание
# Добавить отступы в описании примера
# 5ый пункт в описании алгоритма расписать чуть понятней
# Категория
</ol>
=== Свойства остовных деревьев ===
<ol>
<li value="7">[[Матрица Кирхгофа]]</li>
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
<li> [[Количество помеченных деревьев]] </li>
<li> [[Коды Прюфера]] </li>
</ol>
== 4. Обходы графов ==
=== Эйлеровы графы ===
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li>
# Какое-то мутное доказательства
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
# Какое-то мутное доказательство леммы про корректность алгоритма
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
</ol>
=== Гамильтоновы графы ===
<ol>
<li value="5"> [[Гамильтоновы графы]] </li>
<li> [[Теорема Хватала]] </li>
<li> [[Теорема Дирака]] </li>
<li> [[Теорема Оре]] </li>
<li> [[Теорема Поша]]</li>
<li> [[Теорема Гуйя-Ури]] </li>
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Пояснить переходы в теореме
# Внести пояснение в определение бонда
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
# Картинку сделать красивой
<li> '''взяли''' [[Турниры]] (6) </li>
# Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
<li> [[Теорема Редеи-Камиона]] </li>
</ol>
== 5. Укладки графов ==
# [[Укладка графа на плоскости]]
# [[Формула Эйлера]]
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
## Исправить знаки неравенств
## Источники информации
## Константы в Tex
# [[Укладка дерева]]
# [[Укладка графа с планарными компонентами реберной двусвязности]]
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
# [[Теорема Понтрягина-Куратовского]]
# [[Род, толщина, крупность, число скрещиваний]]
# [[Двойственный граф планарного графа]]
# [[Теорема Фари]]
# [[Гамма-алгоритм]]
== 6. Раскраски графов ==
# [[Раскраска графа]]
# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)
## Англоязычные термины
## Убрать определение двудольного графа и сделать интервики на основной конспект
## Картинку двудольного графа перенести ниже, а то плохо смотрится
## Интервики
## Добавить, что можно ещё за проход в ширину проверить
## Оформить правильно источники информации и См. также
## Перенести см. также до источников информации, а ссылку заменить на интервики
# [[Хроматический многочлен]]
# [[Формула Зыкова]]
# [[Формула Уитни]]
# [[Теорема Брукса]]
# [[Верхние и нижние оценки хроматического числа]]
# [[Хроматическое число планарного графа]]
# [[Многочлен Татта]]
# [[Теория Рамсея]] ('''10''')
## Тут вообще ад какой-то
== 7. Обход в глубину ==
# '''fixed''' [[Обход в глубину, цвета вершин]] (5)
## Англоязычные термины правильно оформить
## Отформатировать псевдокод
## Красивую картинку с цветными вершинами
# [[Лемма о белых путях]]
# [[Использование обхода в глубину для проверки связности]]
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
# [[Использование обхода в глубину для топологической сортировки]]
# [[Использование обхода в глубину для поиска компонент сильной связности]]
# ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4)
## Что-то картинки неудачно расположены
## Кривая структура у доказательства
## Отформатировать псевдокод
## Источники информации красиво оформить
# [[Построение компонент вершинной двусвязности]]
# [[Использование обхода в глубину для поиска мостов]]
# [[Построение компонент реберной двусвязности]]
== 8. Кратчайшие пути в графах ==
# [[Обход в ширину]]
# [[Алгоритм Форда-Беллмана]]
# [[Алгоритм Дейкстры]]
# [[Алгоритм Флойда]]
# [[Алгоритм Джонсона]]
# [[Алгоритм Левита]]
# [[Алгоритм A*]]
# [[Алгоритм D*]]
# [[Эвристики для поиска кратчайших путей]]
== 9. Задача о паросочетании ==
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]]
# [[Теорема Холла]]
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
# [[Связь вершинного покрытия и независимого множества]]
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# [[Теорема Татта о существовании полного паросочетания]]
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
# [[Декомпозиция Эдмондса-Галлаи]]
# '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
## Переменные и константы в Tex
## Добавить сначала постановку задачи
## Кривая ссылка на паросочетание
## Дефисы на тире
## Определения выделять жирным
## Отформатировать псевдокоды
## Зачем-то списки в доказательствах лемм использованы
## Битая ссылка на соседей
## Надо бы доказать все леммы
## Оформить правильно источники информации
## И вообще всё оформить надо
== 10. Задача о максимальном потоке ==
# [[Определение сети, потока]]
# [[Разрез, лемма о потоке через разрез]]
# [[Дополняющая сеть, дополняющий путь]]
# [[Лемма о сложении потоков]]
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
# '''взяли''' [[Алоритм Эдмондса-Карпа]] (5)
## Полностью описать пример про грибок с картинками в конспекте
# [[Алгоритм масштабирования потока]]
# ''взяли'' [[Блокирующий поток]] (1)
## англоязычные термины
## ссылки на русскую и английскую википедию
## Добавить немного общей информации
## Расположить красиво картинки, чтобы не наезжали
# [[Схема алгоритма Диница]]
# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
## "Мы можем применить Лемму(2" — лемму 3, наверное?
## Дефисы на тире
## Знаки неравенств
## Источники информации
# [[Алгоритм поиска блокирующего потока в ациклической сети]]
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# '''!!!''' [[Метод проталкивания предпотока]] (7)
## Картиночки с резервуарами!
## Источники информации
## Добавить см. также
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]
# [[Теорема о декомпозиции]]
# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)
## Источники информации
## Пояснить,почему такие константы используются
## Увеличить дроби
## А что из этой теоремы следует?
# [[Циркуляция потока]]
# [[Алгоритм Каргера для нахождения минимального разреза]]
== 11. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]]
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
## Интервики на декомпозицию
## Знаки неравенств
## Источники информации
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)
## Взять задачи в шаблон
## Оформить покрасивей и правильней
# [[Венгерский алгоритм решения задачи о назначениях]]
