Изменения

# '''!!!взяли''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]

# '''fixed''' [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]

# '''fixed''' [[Гамильтоновы графы]]

# ''fixed'' [[Укладка графа на плоскости]]

# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]

# ''fixed'' [[Теорема Понтрягина-Куратовского]]

# ''fixed'' [[Двойственный граф планарного графа]]

# ''fixed'' [[Раскраска графа]]

1. # [[Обход в глубину, цвета вершин]]2. # [[Лемма о белых путях]]3. # [[Использование обхода в глубину для проверки связности]]4. # [[Использование обхода в глубину для поиска цикла в ориентированном графе]]5. # [[Использование обхода в глубину для топологической сортировки]]6. # [[Использование обхода в глубину для поиска компонент сильной связности]]7. # [[Использование обхода в глубину для поиска точек сочленения]]8. # [[Построение компонент вершинной двусвязности]]9. # [[Использование обхода в глубину для поиска мостов]]10. # [[Построение компонент реберной двусвязности]]

* # [[Обход в ширину]]* # [[Алгоритм Форда-Беллмана]]* # [[Алгоритм Дейкстры]]* # [[Алгоритм Левита]] '''(в процессе редактирования)'''* # [[Алгоритм Флойда]]* # '''!!!''' [[Алгоритм A*]]* ## что-то со второй картиночкой, там гифка, а почему-то не отображается## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.## какая-то тут муть написана, что в корректности, что в оптимальности## а еще можно написать про случай с монотонной эвристикой# [[Алгоритм Джонсона]]

1. # [[Лемма о безопасном ребре]]2. # [[Алгоритм Прима]]3. # [[Алгоритм Краскала]]4. # [[Алгоритм Борувки]]5. # [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]6. # [[Алгоритм двух китайцев]]

* # [[Теорема о максимальном паросочетании и дополняющих цепях]]* ## англоязычные термины# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]* ## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы## код -- копипаста с емакса## источники перечислять с помощью * , а не :# [[Теорема Холла]]* ## добавить ссылку на английскую википедию# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]## перечислять ссылки через * # [[Связь вершинного покрытия и независимого множества]]## источники перечислять с помощью * , 1. 2.# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]* # '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример

* # ''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

* # [[Поток минимальной стоимости]]* ## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]* # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]* # [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]* # [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]* # [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]* # '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]]## написать более подробный псевдокод