3622
правки
Изменения
Новая страница: «Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы. == 1. Основные ...»
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
== 1. Основные определения теории графов ==
# '''взяли''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
## moar англоязычных терминов
## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
## Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).
## "некоторые абстрактные множества." — а что такое неабстрактные множества?
## "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.
## запись "<tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex>" я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)
## альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно <tex>ends : E \rightarrow V \times V</tex>, а декартово произведение у нас еще как упорядочено.
# [[Лемма о рукопожатиях]]
# [[Теорема о существовании простого пути в случае существования пути]]
## перенести определения в "Основные определения"
## форматирование в некоторых местах какое-то упоротое, думаю, это видно.
# [[Теорема о существовании простого цикла в случае существования цикла]]
## добавить интервики
## форматирование в некоторых местах какое-то упоротое
# [[Матрица смежности графа]]
## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
# [[Связь степени матрицы смежности и количества путей]]
# [[Матрица инцидентности графа]]
## Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
# [[Циклическое пространство графа]]
## Пункт "Определение" не нужен, см. правила форматирования
## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
## интервики
## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
# [[Фундаментальные циклы графа]]
## определения "каркаса", кажется, до этого не было, а вообще это вроде то же самое, что "остов", который используется во всем остальном курсе, так что если это так, заменить.
## Раздел "Определение" не нужен.
# [[Дерево, эквивалентные определения]]
## Кажется, ранее не было определний <tex>K_n</tex>, если нет, то надо куда-нибудь их добавить и сделать на них ссылку.
# [[Дополнительный, самодополнительный граф]]
## Оформить нормально определение изоморфности графов (видимо, его надо в "Основные опредения"), и добавить на него ссылку
## англоязычные термины
== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
## англоязычные термины
## интервики
# [[Отношение реберной двусвязности]]
## англоязычные термины
# [[Отношение вершинной двусвязности]]
## англоязычные термины
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
## Капс какой-то зачем-то
# [[Точка сочленения, эквивалентные определения]]
## Цифры в начале определений не нужны, их можно в хедер определения
# [[Мост, эквивалентные определения]]
## англоязычные термины
## Цифры в начале определений не нужны, их можно в хедер определения
# [[k-связность]]
## англоязычные термины
# [[Теорема Менгера]]
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
## пункт "Определения" не нужен
== 3. Остовные деревья ==
# [[Матрица Кирхгофа]]
## Пункт "Определение" не нужен, вынести в начало статьи
## "простого графа" — а простой — это какой? Кинуть ссылку на определение простого графа.
## 0, else — так не говорят, говорят "0, otherwise"
# [[Связь матрицы Кирхгофа и матрицы инцидентности]]
# [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
# [[Количество помеченных деревьев]]
## англоязычные термины
# [[Коды Прюфера]]
== 4. Обходы графов ==
# '''fixed''' [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
## англоязычные термины
## не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести
## "См. Также" — зачем "также" с большой буквы?
# [[Покрытие ребер графа путями]]
# [[Алгоритм построения Эйлерова цикла]]
# [[Произвольно вычерчиваемые из заданной вершины графы]]
# '''fixed''' [[Гамильтоновы графы]]
## англоязычные термины
# [[Теорема Хватала]]
# [[Теорема Дирака]]
# [[Теорема Оре]]
# [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
# [[Турниры]]
# [[Теорема Редеи-Камиона]]
== 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'' [[Раскраска графа]]
## пункт "Раскраска графа" не нужен, перенести в заголовок
## англоязычные термины
## "Хроматическим многочлен"
## надо бы написать, почему нам вообще интересно раскрашивать графы
# [[Двудольные графы и раскраска в 2 цвета]]
# [[Хроматический многочлен]]
# [[Формула Зыкова]]
# [[Формула Уитни]]
# [[Теорема Брукса]]
# [[Верхние и нижние оценки хроматического числа]]
== 7. Обход в глубину ==
# [[Обход в глубину, цвета вершин]]
# [[Лемма о белых путях]]
# [[Использование обхода в глубину для проверки связности]]
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
# [[Использование обхода в глубину для топологической сортировки]]
# [[Использование обхода в глубину для поиска компонент сильной связности]]
# [[Использование обхода в глубину для поиска точек сочленения]]
# [[Построение компонент вершинной двусвязности]]
# [[Использование обхода в глубину для поиска мостов]]
# [[Построение компонент реберной двусвязности]]
== 8. Кратчайшие пути в графах ==
# [[Обход в ширину]]
# [[Алгоритм Форда-Беллмана]]
# [[Алгоритм Дейкстры]]
# [[Алгоритм Левита]] '''(в процессе редактирования)'''
# [[Алгоритм Флойда]]
# '''!!!''' [[Алгоритм A*]]
## что-то со второй картиночкой, там гифка, а почему-то не отображается
## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.
## какая-то тут муть написана, что в корректности, что в оптимальности
## а еще можно написать про случай с монотонной эвристикой
# [[Алгоритм Джонсона]]
== 9. Построение остовных деревьев ==
# [[Лемма о безопасном ребре]]
# [[Алгоритм Прима]]
# [[Алгоритм Краскала]]
# [[Алгоритм Борувки]]
# [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
# [[Алгоритм двух китайцев]]
== 10. Задача о паросочетании ==
# [[Теорема о максимальном паросочетании и дополняющих цепях]]
## англоязычные термины
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое
# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]
## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы
## код -- копипаста с емакса
## источники перечислять с помощью *, а не :
# [[Теорема Холла]]
## добавить ссылку на английскую википедию
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
## перечислять ссылки через *
# [[Связь вершинного покрытия и независимого множества]]
## источники перечислять с помощью *, 1. 2.
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример
== 11. Задача о максимальном потоке ==
# ''fixed'' [[Определение сети, потока]]
## ссылки на русскую и английскую википедию
# ''fixed'' [[Разрез, лемма о потоке через разрез]]
## англоязычные термины
## добавить определение минимального разреза
## ссылки на русскую и английскую википедию
# ''fixed'' [[Дополняющая сеть, дополняющий путь]]
## Дополняющую сеть также называют остаточной, указать это
## ссылки на русскую и английскую википедию
# ''fixed'' [[Лемма о сложении потоков]]
## добавить внутренних ссылок
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
## гм, и зачем "дельта" русским словом в псевдокоде?
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.
# [[Алоритм Эдмондса-Карпа]]
## а описание алгоритма где?
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
## ссылки на русскую/английскую википедию
# [[Алгоритм масштабирования потока]]
## ссылки на русскую/английскую википедию
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
# [[Блокирующий поток]]
## англоязычные термины
## ссылки на русскую и английскую википедию
# [[Схема алгоритма Диница]]
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
## "makeGl" назвать как-нибудь нормально
## "algorithmDinica" тоже назвать нормально
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
## может, назвать остаточную сеть $G_f$, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?
## В лемме в утверждении фигурирует поток $f$, но дальше про него ничего нет. Зачем он?
## "Мы можем применить Лемму(2" — лемму 3, наверное?
# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]
## "Жадный Алгоритм" — зачем с большой буквы алгоритм?
## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# [[Метод проталкивания предпотока]]
## зачем какие-то кванторы в for?
## initialaze -> initialize
## названия функций в тексте оборачиваются в \mathrm
# [[Алгоритм "поднять-в-начало"]]
## названия функций в тексте оборачиваются в \mathrm
## relable -> relabel
# [[Теорема о декомпозиции]]
## кванторы в псевдокоде не нужну, написать просто not exists
# [[Теорема о декомпозиционном барьере]]
# [[Циркуляция потока]]
## англоязычные термины
## ссылки на русскую и английскую википедию
## раздел постановка задачи не нужен, перенести в заголовок
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
# [[Алгоритм Каргера для нахождения минимального разреза]]
## внутреннюю ссылку на мультиграф
## названия функций в тексте оборачиваются в \mathrm
== 12. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]]
## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
# '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]]
## написать более подробный псевдокод
== 1. Основные определения теории графов ==
# '''взяли''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
## moar англоязычных терминов
## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
## Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).
## "некоторые абстрактные множества." — а что такое неабстрактные множества?
## "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.
## запись "<tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex>" я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)
## альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно <tex>ends : E \rightarrow V \times V</tex>, а декартово произведение у нас еще как упорядочено.
# [[Лемма о рукопожатиях]]
# [[Теорема о существовании простого пути в случае существования пути]]
## перенести определения в "Основные определения"
## форматирование в некоторых местах какое-то упоротое, думаю, это видно.
# [[Теорема о существовании простого цикла в случае существования цикла]]
## добавить интервики
## форматирование в некоторых местах какое-то упоротое
# [[Матрица смежности графа]]
## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
# [[Связь степени матрицы смежности и количества путей]]
# [[Матрица инцидентности графа]]
## Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
# [[Циклическое пространство графа]]
## Пункт "Определение" не нужен, см. правила форматирования
## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
## интервики
## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
# [[Фундаментальные циклы графа]]
## определения "каркаса", кажется, до этого не было, а вообще это вроде то же самое, что "остов", который используется во всем остальном курсе, так что если это так, заменить.
## Раздел "Определение" не нужен.
# [[Дерево, эквивалентные определения]]
## Кажется, ранее не было определний <tex>K_n</tex>, если нет, то надо куда-нибудь их добавить и сделать на них ссылку.
# [[Дополнительный, самодополнительный граф]]
## Оформить нормально определение изоморфности графов (видимо, его надо в "Основные опредения"), и добавить на него ссылку
## англоязычные термины
== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
## англоязычные термины
## интервики
# [[Отношение реберной двусвязности]]
## англоязычные термины
# [[Отношение вершинной двусвязности]]
## англоязычные термины
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
## Капс какой-то зачем-то
# [[Точка сочленения, эквивалентные определения]]
## Цифры в начале определений не нужны, их можно в хедер определения
# [[Мост, эквивалентные определения]]
## англоязычные термины
## Цифры в начале определений не нужны, их можно в хедер определения
# [[k-связность]]
## англоязычные термины
# [[Теорема Менгера]]
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
## пункт "Определения" не нужен
== 3. Остовные деревья ==
# [[Матрица Кирхгофа]]
## Пункт "Определение" не нужен, вынести в начало статьи
## "простого графа" — а простой — это какой? Кинуть ссылку на определение простого графа.
## 0, else — так не говорят, говорят "0, otherwise"
# [[Связь матрицы Кирхгофа и матрицы инцидентности]]
# [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
# [[Количество помеченных деревьев]]
## англоязычные термины
# [[Коды Прюфера]]
== 4. Обходы графов ==
# '''fixed''' [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
## англоязычные термины
## не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести
## "См. Также" — зачем "также" с большой буквы?
# [[Покрытие ребер графа путями]]
# [[Алгоритм построения Эйлерова цикла]]
# [[Произвольно вычерчиваемые из заданной вершины графы]]
# '''fixed''' [[Гамильтоновы графы]]
## англоязычные термины
# [[Теорема Хватала]]
# [[Теорема Дирака]]
# [[Теорема Оре]]
# [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
# [[Турниры]]
# [[Теорема Редеи-Камиона]]
== 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'' [[Раскраска графа]]
## пункт "Раскраска графа" не нужен, перенести в заголовок
## англоязычные термины
## "Хроматическим многочлен"
## надо бы написать, почему нам вообще интересно раскрашивать графы
# [[Двудольные графы и раскраска в 2 цвета]]
# [[Хроматический многочлен]]
# [[Формула Зыкова]]
# [[Формула Уитни]]
# [[Теорема Брукса]]
# [[Верхние и нижние оценки хроматического числа]]
== 7. Обход в глубину ==
# [[Обход в глубину, цвета вершин]]
# [[Лемма о белых путях]]
# [[Использование обхода в глубину для проверки связности]]
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
# [[Использование обхода в глубину для топологической сортировки]]
# [[Использование обхода в глубину для поиска компонент сильной связности]]
# [[Использование обхода в глубину для поиска точек сочленения]]
# [[Построение компонент вершинной двусвязности]]
# [[Использование обхода в глубину для поиска мостов]]
# [[Построение компонент реберной двусвязности]]
== 8. Кратчайшие пути в графах ==
# [[Обход в ширину]]
# [[Алгоритм Форда-Беллмана]]
# [[Алгоритм Дейкстры]]
# [[Алгоритм Левита]] '''(в процессе редактирования)'''
# [[Алгоритм Флойда]]
# '''!!!''' [[Алгоритм A*]]
## что-то со второй картиночкой, там гифка, а почему-то не отображается
## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.
## какая-то тут муть написана, что в корректности, что в оптимальности
## а еще можно написать про случай с монотонной эвристикой
# [[Алгоритм Джонсона]]
== 9. Построение остовных деревьев ==
# [[Лемма о безопасном ребре]]
# [[Алгоритм Прима]]
# [[Алгоритм Краскала]]
# [[Алгоритм Борувки]]
# [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
# [[Алгоритм двух китайцев]]
== 10. Задача о паросочетании ==
# [[Теорема о максимальном паросочетании и дополняющих цепях]]
## англоязычные термины
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое
# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]
## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы
## код -- копипаста с емакса
## источники перечислять с помощью *, а не :
# [[Теорема Холла]]
## добавить ссылку на английскую википедию
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
## перечислять ссылки через *
# [[Связь вершинного покрытия и независимого множества]]
## источники перечислять с помощью *, 1. 2.
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример
== 11. Задача о максимальном потоке ==
# ''fixed'' [[Определение сети, потока]]
## ссылки на русскую и английскую википедию
# ''fixed'' [[Разрез, лемма о потоке через разрез]]
## англоязычные термины
## добавить определение минимального разреза
## ссылки на русскую и английскую википедию
# ''fixed'' [[Дополняющая сеть, дополняющий путь]]
## Дополняющую сеть также называют остаточной, указать это
## ссылки на русскую и английскую википедию
# ''fixed'' [[Лемма о сложении потоков]]
## добавить внутренних ссылок
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
## гм, и зачем "дельта" русским словом в псевдокоде?
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.
# [[Алоритм Эдмондса-Карпа]]
## а описание алгоритма где?
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
## ссылки на русскую/английскую википедию
# [[Алгоритм масштабирования потока]]
## ссылки на русскую/английскую википедию
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
# [[Блокирующий поток]]
## англоязычные термины
## ссылки на русскую и английскую википедию
# [[Схема алгоритма Диница]]
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
## "makeGl" назвать как-нибудь нормально
## "algorithmDinica" тоже назвать нормально
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
## может, назвать остаточную сеть $G_f$, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?
## В лемме в утверждении фигурирует поток $f$, но дальше про него ничего нет. Зачем он?
## "Мы можем применить Лемму(2" — лемму 3, наверное?
# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]
## "Жадный Алгоритм" — зачем с большой буквы алгоритм?
## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# [[Метод проталкивания предпотока]]
## зачем какие-то кванторы в for?
## initialaze -> initialize
## названия функций в тексте оборачиваются в \mathrm
# [[Алгоритм "поднять-в-начало"]]
## названия функций в тексте оборачиваются в \mathrm
## relable -> relabel
# [[Теорема о декомпозиции]]
## кванторы в псевдокоде не нужну, написать просто not exists
# [[Теорема о декомпозиционном барьере]]
# [[Циркуляция потока]]
## англоязычные термины
## ссылки на русскую и английскую википедию
## раздел постановка задачи не нужен, перенести в заголовок
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
# [[Алгоритм Каргера для нахождения минимального разреза]]
## внутреннюю ссылку на мультиграф
## названия функций в тексте оборачиваются в \mathrm
== 12. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]]
## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
# '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]]
## написать более подробный псевдокод
