1679
правок
Изменения
→11. Задача о максимальном потоке
== 5. Укладки графов ==
# ''fixed'' [[Укладка графа на плоскости]]
## англоязычные термины
## думаю, здесь же можно написать, что в 3D любой граф укладывается
# [[Формула Эйлера]]
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
## Дать ссылку на определения K5 и K3,3
# [[Укладка дерева]]
# [[Укладка графа с планарными компонентами реберной двусвязности]]
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
# ''fixed'' [[Теорема Понтрягина-Куратовского]]
## Определение гомеоморфизма есть в "Укладка графа на плоскости", на него и сослаться.
## Формулировку теоермы надо вынести в заголовок, например.
# ''fixed'' [[Двойственный граф планарного графа]]
## англоязычные термины
== 6. Раскраски графов ==
Во всем разделе — надо англоязычные термины (их по 1-2 в каждом конспекте)
# ''fixed'' [[Раскраска графа]]
## пункт "Раскраска графа" не нужен, перенести в заголовок
## англоязычные термины
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое
# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]
## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы
## код -- копипаста с емакса
== 11. Задача о максимальном потоке ==
# ''fixed'' [[Определение сети, потока]]
## ссылки на русскую и английскую википедию
# ''fixed'' [[Разрез, лемма о потоке через разрез]]
## англоязычные термины
## добавить определение минимального разреза
## ссылки на русскую и английскую википедию
# ''fixed'' [[Дополняющая сеть, дополняющий путь]]
## Дополняющую сеть также называют остаточной, указать это
## ссылки на русскую и английскую википедию
# ''fixed'' [[Лемма о сложении потоков]]
## добавить внутренних ссылок
# [[Теорема Форда-Фалкерсона]]
## ссылки на русскую и английскую википедию
# [[Схема алгоритма Диница]]
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
## "makeGl" назвать как-нибудь нормально
## "algorithmDinica" тоже назвать нормально
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
## может, назвать остаточную сеть $G_f$, как в предыдущих конспектах?## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?## В лемме в утверждении фигурирует поток $f$, но дальше про него ничего нет. Зачем он?## "Мы можем применить Лемму(2" — лемму 3, наверное?# '''TODO!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]## "Жадный Алгоритм" — зачем с большой буквы алгоритм?## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# [[Метод проталкивания предпотока]]
## зачем какие-то кванторы в for?
## initialaze -> initialize
## названия функций в тексте оборачиваются в \mathrm
# [[Алгоритм "поднять-в-начало"]]
## названия функций в тексте оборачиваются в \mathrm
## relable -> relabel
# [[Теорема о декомпозиции]]
## кванторы в псевдокоде не нужну, написать просто not exists
# [[Теорема о декомпозиционном барьере]]
# [[Циркуляция потока]]
## англоязычные термины
## ссылки на русскую и английскую википедию
## раздел постановка задачи не нужен, перенести в заголовок
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
# [[Алгоритм Каргера для нахождения минимального разреза]]
## внутреннюю ссылку на мультиграф
## названия функций в тексте оборачиваются в \mathrm
== 12. Задача о потоке минимальной стоимости ==
