Участник:Dgerasimov/Тикеты по конспектам year2012 — различия между версиями
(→6. Раскраски графов) |
(→11. Задача о максимальном потоке) |
||
(не показаны 24 промежуточные версии этого же участника) | |||
Строка 2: | Строка 2: | ||
== 1. Основные определения теории графов == | == 1. Основные определения теории графов == | ||
− | # ''' | + | # '''взяли''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]] |
## moar англоязычных терминов | ## moar англоязычных терминов | ||
## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями | ## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями | ||
Строка 72: | Строка 72: | ||
== 4. Обходы графов == | == 4. Обходы графов == | ||
− | # [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | + | # '''fixed''' [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] |
## англоязычные термины | ## англоязычные термины | ||
## не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести | ## не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести | ||
Строка 79: | Строка 79: | ||
# [[Алгоритм построения Эйлерова цикла]] | # [[Алгоритм построения Эйлерова цикла]] | ||
# [[Произвольно вычерчиваемые из заданной вершины графы]] | # [[Произвольно вычерчиваемые из заданной вершины графы]] | ||
− | # [[Гамильтоновы графы]] | + | # '''fixed''' [[Гамильтоновы графы]] |
## англоязычные термины | ## англоязычные термины | ||
# [[Теорема Хватала]] | # [[Теорема Хватала]] | ||
Строка 89: | Строка 89: | ||
== 5. Укладки графов == | == 5. Укладки графов == | ||
− | # [[Укладка графа на плоскости]] | + | # ''fixed'' [[Укладка графа на плоскости]] |
## англоязычные термины | ## англоязычные термины | ||
## думаю, здесь же можно написать, что в 3D любой граф укладывается | ## думаю, здесь же можно написать, что в 3D любой граф укладывается | ||
# [[Формула Эйлера]] | # [[Формула Эйлера]] | ||
− | # [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] | + | # ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] |
## Дать ссылку на определения K5 и K3,3 | ## Дать ссылку на определения K5 и K3,3 | ||
# [[Укладка дерева]] | # [[Укладка дерева]] | ||
# [[Укладка графа с планарными компонентами реберной двусвязности]] | # [[Укладка графа с планарными компонентами реберной двусвязности]] | ||
# [[Укладка графа с планарными компонентами вершинной двусвязности]] | # [[Укладка графа с планарными компонентами вершинной двусвязности]] | ||
− | # [[Теорема Понтрягина-Куратовского]] | + | # ''fixed'' [[Теорема Понтрягина-Куратовского]] |
## Определение гомеоморфизма есть в "Укладка графа на плоскости", на него и сослаться. | ## Определение гомеоморфизма есть в "Укладка графа на плоскости", на него и сослаться. | ||
## Формулировку теоермы надо вынести в заголовок, например. | ## Формулировку теоермы надо вынести в заголовок, например. | ||
− | # [[Двойственный граф планарного графа]] | + | # ''fixed'' [[Двойственный граф планарного графа]] |
## англоязычные термины | ## англоязычные термины | ||
== 6. Раскраски графов == | == 6. Раскраски графов == | ||
− | # [[Раскраска графа]] | + | Во всем разделе — надо англоязычные термины (их по 1-2 в каждом конспекте) |
+ | # ''fixed'' [[Раскраска графа]] | ||
## пункт "Раскраска графа" не нужен, перенести в заголовок | ## пункт "Раскраска графа" не нужен, перенести в заголовок | ||
## англоязычные термины | ## англоязычные термины | ||
Строка 118: | Строка 119: | ||
== 7. Обход в глубину == | == 7. Обход в глубину == | ||
− | + | # [[Обход в глубину, цвета вершин]] | |
− | + | # [[Лемма о белых путях]] | |
− | + | # [[Использование обхода в глубину для проверки связности]] | |
− | + | # [[Использование обхода в глубину для поиска цикла в ориентированном графе]] | |
− | + | # [[Использование обхода в глубину для топологической сортировки]] | |
− | + | # [[Использование обхода в глубину для поиска компонент сильной связности]] | |
− | + | # [[Использование обхода в глубину для поиска точек сочленения]] | |
− | + | # [[Построение компонент вершинной двусвязности]] | |
− | + | # [[Использование обхода в глубину для поиска мостов]] | |
− | + | # [[Построение компонент реберной двусвязности]] | |
== 8. Кратчайшие пути в графах == | == 8. Кратчайшие пути в графах == | ||
− | + | # [[Обход в ширину]] | |
− | + | # [[Алгоритм Форда-Беллмана]] | |
− | + | # [[Алгоритм Дейкстры]] | |
− | + | # [[Алгоритм Левита]] '''(в процессе редактирования)''' | |
− | + | # [[Алгоритм Флойда]] | |
− | + | # '''!!!''' [[Алгоритм A*]] | |
+ | ## что-то со второй картиночкой, там гифка, а почему-то не отображается | ||
+ | ## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative. | ||
+ | ## какая-то тут муть написана, что в корректности, что в оптимальности | ||
+ | ## а еще можно написать про случай с монотонной эвристикой | ||
+ | # [[Алгоритм Джонсона]] | ||
== 9. Построение остовных деревьев == | == 9. Построение остовных деревьев == | ||
− | + | # [[Лемма о безопасном ребре]] | |
− | + | # [[Алгоритм Прима]] | |
− | + | # [[Алгоритм Краскала]] | |
− | + | # [[Алгоритм Борувки]] | |
− | + | # [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] | |
− | + | # [[Алгоритм двух китайцев]] | |
== 10. Задача о паросочетании == | == 10. Задача о паросочетании == | ||
− | + | # [[Теорема о максимальном паросочетании и дополняющих цепях]] | |
− | + | ## англоязычные термины | |
− | + | # [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | |
− | * [[Теорема Холла]] | + | ## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое |
− | + | # '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]] | |
− | * [[Связь вершинного покрытия и независимого множества]] | + | ## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы |
− | * [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | + | ## код -- копипаста с емакса |
− | + | ## источники перечислять с помощью *, а не : | |
+ | # [[Теорема Холла]] | ||
+ | ## добавить ссылку на английскую википедию | ||
+ | # [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] | ||
+ | ## перечислять ссылки через * | ||
+ | # [[Связь вершинного покрытия и независимого множества]] | ||
+ | ## источники перечислять с помощью *, 1. 2. | ||
+ | # [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | ||
+ | # '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | ||
+ | ## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример | ||
== 11. Задача о максимальном потоке == | == 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. Задача о потоке минимальной стоимости == | == 12. Задача о потоке минимальной стоимости == | ||
− | + | # [[Поток минимальной стоимости]] | |
− | + | ## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму) | |
− | + | # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | |
− | + | # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] | |
− | + | # [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] | |
− | + | # [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] | |
− | + | # [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] | |
+ | # '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]] | ||
+ | ## написать более подробный псевдокод |
Текущая версия на 21:38, 6 января 2014
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
1. Основные определения теории графов
- взяли Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- moar англоязычных терминов
- "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
- Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).
- "некоторые абстрактные множества." — а что такое неабстрактные множества?
- "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.
- запись " " я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)
- альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно , а декартово произведение у нас еще как упорядочено.
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- перенести определения в "Основные определения"
- форматирование в некоторых местах какое-то упоротое, думаю, это видно.
- Теорема о существовании простого цикла в случае существования цикла
- добавить интервики
- форматирование в некоторых местах какое-то упоротое
- Матрица смежности графа
- "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
- Циклическое пространство графа
- Пункт "Определение" не нужен, см. правила форматирования
- Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
- интервики
- "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
- Фундаментальные циклы графа
- определения "каркаса", кажется, до этого не было, а вообще это вроде то же самое, что "остов", который используется во всем остальном курсе, так что если это так, заменить.
- Раздел "Определение" не нужен.
- Дерево, эквивалентные определения
- Кажется, ранее не было определний , если нет, то надо куда-нибудь их добавить и сделать на них ссылку.
- Дополнительный, самодополнительный граф
- Оформить нормально определение изоморфности графов (видимо, его надо в "Основные опредения"), и добавить на него ссылку
- англоязычные термины
2. Связность в графах
- Отношение связности, компоненты связности
- англоязычные термины
- интервики
- Отношение реберной двусвязности
- англоязычные термины
- Отношение вершинной двусвязности
- англоязычные термины
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Капс какой-то зачем-то
- Точка сочленения, эквивалентные определения
- Цифры в начале определений не нужны, их можно в хедер определения
- Мост, эквивалентные определения
- англоязычные термины
- Цифры в начале определений не нужны, их можно в хедер определения
- k-связность
- англоязычные термины
- Теорема Менгера
- убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
- пункт "Определения" не нужен
3. Остовные деревья
- Матрица Кирхгофа
- Пункт "Определение" не нужен, вынести в начало статьи
- "простого графа" — а простой — это какой? Кинуть ссылку на определение простого графа.
- 0, else — так не говорят, говорят "0, otherwise"
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- англоязычные термины
- Коды Прюфера
4. Обходы графов
- fixed Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- англоязычные термины
- не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести
- "См. Также" — зачем "также" с большой буквы?
- Покрытие ребер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- fixed Гамильтоновы графы
- англоязычные термины
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Турниры
- Теорема Редеи-Камиона
5. Укладки графов
- fixed Укладка графа на плоскости
- англоязычные термины
- думаю, здесь же можно написать, что в 3D любой граф укладывается
- Формула Эйлера
- fixed Непланарность
и
- Дать ссылку на определения 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. Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- !!! Венгерский алгоритм решения задачи о назначениях
- написать более подробный псевдокод