Участник:Dgerasimov/Тикеты по конспектам year2012 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎8. Кратчайшие пути в графах)
(→‎11. Задача о максимальном потоке)
 
(не показана 21 промежуточная версия этого же участника)
Строка 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 в каждом конспекте)
 
Во всем разделе — надо англоязычные термины (их по 1-2 в каждом конспекте)
−
# [[Раскраска графа]]
+
# ''fixed'' [[Раскраска графа]]
 
## пункт "Раскраска графа" не нужен, перенести в заголовок
 
## пункт "Раскраска графа" не нужен, перенести в заголовок
 
## англоязычные термины
 
## англоязычные термины
Строка 119: Строка 119:
  
 
== 7. Обход в глубину ==
 
== 7. Обход в глубину ==
−
* [[Обход в глубину, цвета вершин]]
+
# [[Обход в глубину, цвета вершин]]
−
* [[Лемма о белых путях]]
+
# [[Лемма о белых путях]]
−
* [[Использование обхода в глубину для проверки связности]]
+
# [[Использование обхода в глубину для проверки связности]]
−
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
+
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
−
* [[Использование обхода в глубину для топологической сортировки]]
+
# [[Использование обхода в глубину для топологической сортировки]]
−
* [[Использование обхода в глубину для поиска компонент сильной связности]]
+
# [[Использование обхода в глубину для поиска компонент сильной связности]]
−
* [[Использование обхода в глубину для поиска точек сочленения]]
+
# [[Использование обхода в глубину для поиска точек сочленения]]
−
* [[Построение компонент вершинной двусвязности]]
+
# [[Построение компонент вершинной двусвязности]]
−
* [[Использование обхода в глубину для поиска мостов]]
+
# [[Использование обхода в глубину для поиска мостов]]
−
* [[Построение компонент реберной двусвязности]]
+
# [[Построение компонент реберной двусвязности]]
  
 
== 8. Кратчайшие пути в графах ==
 
== 8. Кратчайшие пути в графах ==
−
* [[Обход в ширину]]
+
# [[Обход в ширину]]
−
* [[Алгоритм Форда-Беллмана]]
+
# [[Алгоритм Форда-Беллмана]]
−
* [[Алгоритм Дейкстры]]
+
# [[Алгоритм Дейкстры]]
−
* [[Алгоритм Левита]] '''(в процессе редактирования)'''
+
# [[Алгоритм Левита]] '''(в процессе редактирования)'''
−
* [[Алгоритм Флойда]]
+
# [[Алгоритм Флойда]]
−
* [[Алгоритм A*]]
+
# '''!!!''' [[Алгоритм 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. Основные определения теории графов

  1. взяли Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
    1. moar англоязычных терминов
    2. "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями
    3. Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).
    4. "некоторые абстрактные множества." — а что такое неабстрактные множества?
    5. "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.
    6. запись "[math] E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})[/math]" я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)
    7. альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно [math]ends : E \rightarrow V \times V[/math], а декартово произведение у нас еще как упорядочено.
  2. Лемма о рукопожатиях
  3. Теорема о существовании простого пути в случае существования пути
    1. перенести определения в "Основные определения"
    2. форматирование в некоторых местах какое-то упоротое, думаю, это видно.
  4. Теорема о существовании простого цикла в случае существования цикла
    1. добавить интервики
    2. форматирование в некоторых местах какое-то упоротое
  5. Матрица смежности графа
    1. "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
  6. Связь степени матрицы смежности и количества путей
  7. Матрица инцидентности графа
    1. Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
  8. Циклическое пространство графа
    1. Пункт "Определение" не нужен, см. правила форматирования
    2. Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
    3. интервики
    4. "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
  9. Фундаментальные циклы графа
    1. определения "каркаса", кажется, до этого не было, а вообще это вроде то же самое, что "остов", который используется во всем остальном курсе, так что если это так, заменить.
    2. Раздел "Определение" не нужен.
  10. Дерево, эквивалентные определения
    1. Кажется, ранее не было определний [math]K_n[/math], если нет, то надо куда-нибудь их добавить и сделать на них ссылку.
  11. Дополнительный, самодополнительный граф
    1. Оформить нормально определение изоморфности графов (видимо, его надо в "Основные опредения"), и добавить на него ссылку
    2. англоязычные термины

2. Связность в графах

  1. Отношение связности, компоненты связности
    1. англоязычные термины
    2. интервики
  2. Отношение реберной двусвязности
    1. англоязычные термины
  3. Отношение вершинной двусвязности
    1. англоязычные термины
  4. Граф компонент реберной двусвязности
  5. Граф блоков-точек сочленения
    1. Капс какой-то зачем-то
  6. Точка сочленения, эквивалентные определения
    1. Цифры в начале определений не нужны, их можно в хедер определения
  7. Мост, эквивалентные определения
    1. англоязычные термины
    2. Цифры в начале определений не нужны, их можно в хедер определения
  8. k-связность
    1. англоязычные термины
  9. Теорема Менгера
    1. убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
  10. Теорема Менгера, альтернативное доказательство
  11. Вершинная, реберная связность, связь между ними и минимальной степенью вершины
    1. пункт "Определения" не нужен

3. Остовные деревья

  1. Матрица Кирхгофа
    1. Пункт "Определение" не нужен, вынести в начало статьи
    2. "простого графа" — а простой — это какой? Кинуть ссылку на определение простого графа.
    3. 0, else — так не говорят, говорят "0, otherwise"
  2. Связь матрицы Кирхгофа и матрицы инцидентности
  3. Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
  4. Количество помеченных деревьев
    1. англоязычные термины
  5. Коды Прюфера

4. Обходы графов

  1. fixed Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
    1. англоязычные термины
    2. не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести
    3. "См. Также" — зачем "также" с большой буквы?
  2. Покрытие ребер графа путями
  3. Алгоритм построения Эйлерова цикла
  4. Произвольно вычерчиваемые из заданной вершины графы
  5. fixed Гамильтоновы графы
    1. англоязычные термины
  6. Теорема Хватала
  7. Теорема Дирака
  8. Теорема Оре
  9. Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
  10. Турниры
  11. Теорема Редеи-Камиона

5. Укладки графов

  1. fixed Укладка графа на плоскости
    1. англоязычные термины
    2. думаю, здесь же можно написать, что в 3D любой граф укладывается
  2. Формула Эйлера
  3. fixed Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
    1. Дать ссылку на определения K5 и K3,3
  4. Укладка дерева
  5. Укладка графа с планарными компонентами реберной двусвязности
  6. Укладка графа с планарными компонентами вершинной двусвязности
  7. fixed Теорема Понтрягина-Куратовского
    1. Определение гомеоморфизма есть в "Укладка графа на плоскости", на него и сослаться.
    2. Формулировку теоермы надо вынести в заголовок, например.
  8. fixed Двойственный граф планарного графа
    1. англоязычные термины

6. Раскраски графов

Во всем разделе — надо англоязычные термины (их по 1-2 в каждом конспекте)

  1. fixed Раскраска графа
    1. пункт "Раскраска графа" не нужен, перенести в заголовок
    2. англоязычные термины
    3. "Хроматическим многочлен"
    4. надо бы написать, почему нам вообще интересно раскрашивать графы
  2. Двудольные графы и раскраска в 2 цвета
  3. Хроматический многочлен
  4. Формула Зыкова
  5. Формула Уитни
  6. Теорема Брукса
  7. Верхние и нижние оценки хроматического числа

7. Обход в глубину

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

8. Кратчайшие пути в графах

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

9. Построение остовных деревьев

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

10. Задача о паросочетании

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

11. Задача о максимальном потоке

  1. fixed Определение сети, потока
    1. ссылки на русскую и английскую википедию
  2. fixed Разрез, лемма о потоке через разрез
    1. англоязычные термины
    2. добавить определение минимального разреза
    3. ссылки на русскую и английскую википедию
  3. fixed Дополняющая сеть, дополняющий путь
    1. Дополняющую сеть также называют остаточной, указать это
    2. ссылки на русскую и английскую википедию
  4. fixed Лемма о сложении потоков
    1. добавить внутренних ссылок
  5. Теорема Форда-Фалкерсона
  6. Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
    1. гм, и зачем "дельта" русским словом в псевдокоде?
    2. псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.
  7. Алоритм Эдмондса-Карпа
    1. а описание алгоритма где?
    2. везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
    3. ссылки на русскую/английскую википедию
  8. Алгоритм масштабирования потока
    1. ссылки на русскую/английскую википедию
    2. ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
  9. Блокирующий поток
    1. англоязычные термины
    2. ссылки на русскую и английскую википедию
  10. Схема алгоритма Диница
    1. "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
    2. "makeGl" назвать как-нибудь нормально
    3. "algorithmDinica" тоже назвать нормально
  11. Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
    1. может, назвать остаточную сеть $G_f$, как в предыдущих конспектах?
    2. "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?
    3. В лемме в утверждении фигурирует поток $f$, но дальше про него ничего нет. Зачем он?
    4. "Мы можем применить Лемму(2" — лемму 3, наверное?
  12. !!! Алгоритм поиска блокирующего потока в ациклической сети
    1. "Жадный Алгоритм" — зачем с большой буквы алгоритм?
    2. Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации
    3. алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
  13. Метод проталкивания предпотока
    1. зачем какие-то кванторы в for?
    2. initialaze -> initialize
    3. названия функций в тексте оборачиваются в \mathrm
  14. Алгоритм "поднять-в-начало"
    1. названия функций в тексте оборачиваются в \mathrm
    2. relable -> relabel
  15. Теорема о декомпозиции
    1. кванторы в псевдокоде не нужну, написать просто not exists
  16. Теорема о декомпозиционном барьере
  17. Циркуляция потока
    1. англоязычные термины
    2. ссылки на русскую и английскую википедию
    3. раздел постановка задачи не нужен, перенести в заголовок
    4. сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
  18. Алгоритм Каргера для нахождения минимального разреза
    1. внутреннюю ссылку на мультиграф
    2. названия функций в тексте оборачиваются в \mathrm

12. Задача о потоке минимальной стоимости

  1. Поток минимальной стоимости
    1. "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)
  2. Теорема Форда-Фалкерсона о потоке минимальной стоимости
  3. Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
  4. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
  5. Использование потенциалов Джонсона при поиске потока минимальной стоимости
  6. Сведение задачи о назначениях к задаче о потоке минимальной стоимости
  7. !!! Венгерский алгоритм решения задачи о назначениях
    1. написать более подробный псевдокод
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Dgerasimov/Тикеты_по_конспектам_year2012&oldid=35256»