Просмотр исходного текста страницы Участник:Shersh/Тикеты к 3ему терму

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.

== 1. Основные определения теории графов ==
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
# ''fixed'' [[Лемма о рукопожатиях]] (1)
## Увеличить дроби
## Взять константы в tex
## Заменить умножение на \cdot
## Добавить пару слов о графах с петлями и кратными рёбрами
## Заменить источники на источники информации
# ''взяли'' [[Теорема о существовании простого пути в случае существования пути]] (4)
## Алгоритм и предположение зря оформлены как псевдокод
## Добавить ссылок
## Заменить названия способов доказательств на конструктивное и неконструктивное
## Исправить ошибку в доказательстве построением
## Плохо, что картинка наплывает на заголовок {{---}} переделать
## Добавить в формулировку теоремы, что вершинно-простой путь
# [[Теорема о существовании простого цикла в случае существования цикла]]
# ''fixed'' [[Матрица смежности графа]] (3) ''вместе со следующим''
## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два
## Что за помеченный граф?
## Добавить про что, в матрице смежности можно хранить веса рёбер
## Оформить правильно источники информации
## Добавить оценку на память матрицы смежности и привести примеры, когда эффективно её использовать, а когда нет
# ''взяли'' [[Связь степени матрицы смежности и количества путей]] ''вместе с предыдущим''
## Это можно внести в прошлый конспект
## Добавить что-нибудь про бинарное возведение в степень
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Добавить свойства матрицы инцидентности с доказательствами
## Добавить ссылок в источники информации
## Англоязычные термины
## Оформить правильно источники информации
## Добавить См. также на матрицу смежности
## Добавить про списки смежности и их оформить тоже в таблички
# [[Циклическое пространство графа]]
# ''взяли'' [[Фундаментальные циклы графа]] (0.5)
## Источники информации нормально оформить
## Подписать получше картинку
## Заменить многоточия на \ldots
# ''взяли'' [[Дерево, эквивалентные определения]] (0.5)
## Англоязычные термины
## Пофиксить знаки неравенств
## Источники информации нормально оформить
# [[Алгоритмы на деревьях]]
# ''взяли'' [[Дополнительный, самодополнительный граф]] (1)
## Англоязычные термины оформить правильно
## Заменить угловые скобки на \langle и \rangle
## Интервики
## Добавить ссылки в источники информации
## Шаблоном заменить тире
# [[Теоретико-множественные операции над графами]]

== 2. Связность в графах ==
# ''fixed'' [[Отношение связности, компоненты связности]] (0.5)
## англоязычные термины
## интервики
## Заменить тире на шаблон
## Добавить См. также
# ''fixed'' [[Отношение реберной двусвязности]] (0.5)
## англоязычные термины
## Оформить правильно источники информации
## Перенести из См. также визуализатор в источники информации
# [[Отношение вершинной двусвязности]] (0.5)
## англоязычные термины
## Добавить ссылок
## Оформить правильно источники информации
# ''взяли'' [[Точка сочленения, эквивалентные определения]] (0.5)
## Англоязычные термины
## Цифры в начале определений не нужны, их можно в хедер определения
## Оформить пункты в теореме маркированным списком через #
## Источники информации
# [[Мост, эквивалентные определения]] (0.5)
## См. выше
# [[Граф компонент реберной двусвязности]] (0.5)
## Нормально оформить источники информации и см. также
## Англоязычные термины
## Избавить от a) и б) в доказательстве
# [[Граф блоков-точек сочленения]] (0.5)
## См. выше
## Капс какой-то зачем-то
# ''взяли'' [[k-связность]] (0.5)
## англоязычные термины
## Тире заменить на шаблон
## Дефисы в определениях ровно поставить
## Палку вертикальную в множестве заменить на \mid
## Странное обозначение {{---}} \smallsetminus
## Источники информации
# ''взяли'' [[Теорема Менгера]] (0.5)
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
## Тире заменить на шаблон
## Можно добавить ссылок, оформить см. также по-другому
## Источники информации
# [[Теорема Менгера, альтернативное доказательство]] (0.5)
## Заменить тире на шаблон
## Обращение к леммам сделать через интервики
## См. также на оригинальное доказательство
## Источники информации
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## пункт "Определения" не нужен
## Изменить знаки неравенств в tex
## Не надо дублировать определения из другого конспекта
## Отформатировать псевдокод
## find_flow какой-то стрёмный
## Источники информации
## k-связность с маленькой буквы
## Добавить См. также на что-нибудь разумное
## Добавить см. также

== 3. Остовные деревья ==
=== Построение остовных деревьев ===
<ol>
<li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li>
<li>[[Алгоритм Прима]]</li>
<li> [[Алгоритм Краскала]] </li>
<li> '''fixed''' [[Алгоритм Борувки]] (5) </li>
# Описание алгоритма оформить красиво и чуточку понятней
# Доказательство теоремы оформить красиво
# Переделать доказательства с учётом возможного равенства рёбер
# Отформатировать псевдокод
# Пример как-то кривовато описан (особенно это разделение на компоненты связности)
# Заменить дефис на шаблон
# Источники информации правильно оформить
# Категория
<li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li>
# Доказательство красиво оформить
# Заменить дефис на шаблон
# Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
# Почему ребро uv {{---}} единственное ребро, пересекающее разрез?
# Источники информации
# Знаки неравенств
# Категория
<li> '''!!!''' [[Алгоритм двух китайцев]] (6) </li>
# Англоязычные термины оформить правильно
# Добавить определение покрывающего дерева
# Описать реализацию красиво
# Дефис заменить на тире
# Отформатировать псевдокод
# Доказать, почему не более V конденсаций
# Источники информации оформить правильно
# Доказать второе замечание
# Добавить отступы в описании примера
# 5ый пункт в описании алгоритма расписать чуть понятней
# Категория
</ol>

=== Свойства остовных деревьев ===
<ol>
<li value="7">[[Матрица Кирхгофа]]</li>
<li> ''взяли'' [[Связь матрицы Кирхгофа и матрицы инцидентности]] (0.5)</li>
# Англоязычные термины
# Константы взять в Tex
# См. также и источники информации
# Категория
<li> ''взяли'' [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] (0.5)</li>
# Добавить ссылку на формулу Бине-Коши (примечание на википедию или интервики на конспект линала)
# Источники и см. также
# Исправить знаки неравенств
# Заменить тире на шаблон
# Категория
<li> ''взяли'' [[Количество помеченных деревьев]] (0.5)</li>
# Англоязычные термины
# Первый пункт не нужен
# Категория
# Оформить доказательство красиво
# См. также и источники информации
# = в Tex
<li> ''взяли'' [[Коды Прюфера]] (0.5)</li>
# Не оформлять описание алгоритма как псевдокод
# Англоязычные термины
# Категория
# См. также и Источники информации
</ol>

== 4. Обходы графов ==
=== Эйлеровы графы ===
<ol>
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> '''!!!''' [[Покрытие ребер графа путями]] (5)</li>
# Так и не надо определение почти связного графа {{---}} надо внести в предыдущий конспект, а здесь сделать интервики
# Знак "не принадлежит" оформить в Tex
# Что-то доказательство какое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей
# То же самое в достаточности
# Оформить правильно источники информации
# Категория
<li> [[Алгоритм построения Эйлерова цикла]] (3) </li>
# Отформатировать псевдокод
# Довести до ума. Начиная с представления уже тяжко. До этого момента надо подытожить текущие доказательство, а то там много разных фактов и надо их как-то в одну пачку собрать, сказав, чего хочется достичь дальше.
# Категория
<li> '''!!!''' [[Произвольно вычерчиваемые из заданной вершины графы]] (6) </li>
# Англоязычные термины оформить правильно
# Что значит неодноэелементный?
# Стрелки слишком длинные
# На картинке ошибка {{---}} почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень
# Источники информации правильно оформить
# Хотелось бы больше пояснений в доказательстве
# В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить, используя в основе какой-то лес
# Категория
</ol>

=== Гамильтоновы графы ===
<ol>
<li value="5"> '''взяли''' [[Гамильтоновы графы]] (6.5) </li>
# Заменить дефисы на тире
# Исправить знаки неравенств
# Отформатировать псевдокод
# Помёрджить с конспектом динамического программирования и пофиксить ошибки в обоих, если есть (должны остаться алгоритмы поиска пути/цикла, пути, минимизирующего какой-то критерий)
# Источники информации
# Категория
<li> ''взяли'' [[Теорема Хватала]] (0.5) </li>
# Исправить знаки неравенств
# Поставить \mid в множествах
# Лишние кавычки в доказательствах вокруг стрелок
# Убрать q.e.d
# Оформить правильно источники информации
# Категория
<li>[[Теорема Поша]]</li>
<li> [[Теорема Дирака]] </li>
<li> [[Теорема Оре]] </li>
<li> '''взяли''' [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] (5) </li>
# Странные обозначения для графа и множеств вершин и рёбер
# Убрать умножение звёздочкой
# Заменить дефис на тире
# Отформатировать псевдокод
# Источники информации
# Исправить знаки неравенств
# Категория
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Англоязычные термины оформить правильно
# Дефис заменить на тире
# Картинки криво расположены
# Ссылки поехали в примере
# Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачней
# Почему необходимое условие? А в обратную сторону?
# Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 грань
# Категория
<li> '''взяли''' [[Турниры]] (5) </li>
# Англоязычные термины
# Добавить оценку на число турниров в графе из n вершин
# Убрать лишние определения
# Оформить правильно источники информации
# Немного неправильно сформулировано утверждение про полустепени вершин
# Категория
<li> ''взяли'' [[Теорема Редеи-Камиона]] (0.5) </li>
# Исправить знаки неравенств
# Правильно оформить источники информации
# Категория
</ol>

== 5. Укладки графов ==
# ''взяли'' [[Укладка графа на плоскости]] (0.5)
## Англоязычные термины правильно оформить
## Добавить пару ссылок на конспекты вычгеома о том, чем хороши планарные графы
## Источники информации
# ''fixed'' [[Формула Эйлера]] (0.5)
## Исправить знаки неравенств
## Заменить литературу на источники информации
## Добавить ссылок
# [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
## Исправить знаки неравенств
## Источники информации
## Константы в Tex
# ''взяли'' [[Укладка дерева]] (1)
## Заменить sup и inf на \sup и \inf
## Заменить дефисы на тире
## Картинки адекватно расположить
## Англоязычные термины правильно оформить
## Зачем в начале замечание про грань?
## Увеличить дроби
# ''взяли'' [[Укладка графа с планарными компонентами реберной двусвязности]] (0.5)
## Заменить источники на источники информации
## Взять все переменные в Tex
## Добавить См. также
## Интервики на мост
# ''взяли'' [[Укладка графа с планарными компонентами вершинной двусвязности]] (0.5)
## Исправить знаки неравенств
## Заменить источники на источники информации
## deg заменить на \deg
# [[Теорема Понтрягина-Куратовского]]
# [[Двойственный граф планарного графа]] (1)
## Добавить пробел после "двойственным" в определении
## Интервики
## Убрать neat из определения самодвойственного графа
## Увеличить дроби
## Добавить источники информации
## Интервики на мост, планарные графы
## Добавить См. также
# [[Теорема Фари]]

== 6. Раскраски графов ==
# '''!!!''' [[Раскраска графа]] (6)
## Правильно оформить англоязычные термины
## Заменить \phi на \varphi
## Пункт "Хроматическое число" не нужен
## Заменить дефисы на тире
## Пояснить, что такое нулевой граф
## Список хроматических чисел нормально оформить
## Четвёртый пример заменить на двудольные графы (дерево, в частности, является таким)
## Оформить правильно источники информации
## Примечания перенести выше
## Кинуть интервики на неразрешимость задачи о раскраске графа
## Написать о связи хроматического числа и хроматического многочлена, и почему нельзя найти хроматическое число, если у нас есть такая замечательная штука, как хроматический многочлен?
# [[Двудольные графы и раскраска в 2 цвета]] (3)
## Англоязычные термины
## Убрать определение двудольного графа и сделать интервики на основной конспект
## Картинку двудольного графа перенести ниже, а то плохо смотрится
## Интервики
## Добавить, что можно ещё за проход в ширину проверить
## Оформить правильно источники информации и См. также
## Перенести см. также до источников информации, а ссылку заменить на интервики
# [[Хроматический многочлен]]
# '''!!!''' [[Формула Зыкова]] (6)
## Определения выделить жирным
## Англоязычные термины правильно оформить
## Написать более подробное, понятное и корректное доказательство
## Исправить знаки неравенств
## Правильно оформить источники информации
## Добавить см. также
# '''!!!''' [[Формула Уитни]] (6)
## Заменить дефисы на тире
## Исправить знаки неравенств
## Заменить \phi на \varphi
## Правильно оформить источники информации
## А что такое собственные и несобственный раскраски?
## Пояснить непонятные места в доказательстве вцелом
## Добавить см. также
# [[Теорема Брукса]] (0.5)
## Заменить дефисы на тире
## Интервики
## "на iом шаге" {{---}} пропущен дефис
## Исправить знаки неравенств
## Оформить правильно источники информации
## Добавить см. также
# ''взяли'' [[Верхние и нижние оценки хроматического числа]] (1)
## Заменить дефисы на тире
## Исправить знаки неравенств
## Интервики
## Англоязычные термины
## Заменить max на \max
## Все переменные взять в Tex
## Увеличить дроби
## Оформить правильно источники информации и см. также
# [[Хроматическое число планарного графа]] (3)
## Все константы взять в Tex
## Доказательство по индукции красиво оформить
## Заменить дефисы на тире
## Исправить знаки неравенств
## Теорема о 5-раскраске планарного графа именная {{---}} Хивуд {{---}} дать ей название
## Оформить правильно источники информации
## Заменить многоточия на \ldots
## Разместить картинки друг под другом
# [[Многочлен Татта]] (0.5)
## Англоязычные термины
## Заменить дефисы на тире
## " Уитни (Whiney rank polynomial)." {{---}} кажется, пропущено t
## "Показатели в формуле раногового" {{---}} зачем это в определение вносить?
## Интервики
## Оформить правильно источники информации
# [[Теория Рамсея]] ('''??''')
## Тут вообще ад какой-то

== 7. Обход в глубину ==
# '''взяли''' [[Обход в глубину, цвета вершин]] (5)
## Англоязычные термины правильно оформить
## Отформатировать псевдокод
## Переименовать конспект в Обход в глубину, DFS
## Красивую картинку с цветными вершинами
# [[Лемма о белых путях]]
# '''fixed''' [[Использование обхода в глубину для проверки связности]] (5)
## Отформатировать псевдокод
## Задачу в шаблон
## Добавить примеров задач, например, как по двум вершинам определять, являются ли они связанными в режиме online при добавлении рёбер
## Добавить источники информации, см. также
## Tex внутри конспекта сделать красивым
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
# [[Использование обхода в глубину для топологической сортировки]]
# [[Использование обхода в глубину для поиска компонент сильной связности]] (3)
## Некрасивый список в доказательстве теоремы
## Отформатировать псевдокод
## Добавить ссылок
# '''!!!''' [[Использование обхода в глубину для поиска точек сочленения]] (6)
## Убрать отступ в теореме
## Отформатировать псевдокод
## Источники информации красиво оформить
## Добавить примеры того, когда и почему становится плохо, если функция up будет определена по-другому
# [[Построение компонент вершинной двусвязности]] (3)
## Отформатировать псевдокод
## Красиво оформить источники
# [[Использование обхода в глубину для поиска мостов]] (3)
## Заменить min на \min
## Отформатировать псевдокод
## Некрасиво оформлено утверждение маркированным списком, да и у тело утверждения тоже некрасивое
## Нормаоьно оформить источники информации, добавить см. также
# [[Построение компонент реберной двусвязности]] (3)
## Отформатировать псевдокод
## Визуализатор внести в источники информации

== 8. Кратчайшие пути в графах ==
# [[Обход в ширину]]
# [[Алгоритм Форда-Беллмана]] (3)
## Получшение введение, задачу в шаблон
## Интервики
## Отформатировать псевдокоды
## for в тексте взять в mathrm
## Заменить дефисы на тире
## Исправить знаки неравенств
## Оформить правильно источники информации
# [[Алгоритм Дейкстры]] (3)
## Псевдокод вообще криво оформлен
## Исправить знаки неравенств
## Оформить правильно источники информации
## Табличку сделать красивой
# '''!!!''' [[Алгоритм Флойда]] (6)
## Оформить правильно источники информации
## Заменить min на \min
## Отформатировать правильно псевдокод
## Вспомнить алгоритм построение транзитивного замыкания на первом курсе
## Исправить в тексте знаки равенства и неравенства
## Оформить правильно источники информации
## Добавить оптимизацию с битовыми масками
# '''!!!''' [[Алгоритм Джонсона]] (7)
## Англоязычные термины
## Заменить дефисы на тире
## Зачем-то в шаблоне определение написано не определение
## Исправить знаки неравенств
## Отформатировать псевдокоды
## Доказательство со стрелочками красиво оформить
## Оформить правильно источники информации
## Расписать сложность других реализаций
# '''взяли''' [[Алгоритм Левита]] (7)
## Оформить правильно англоязычные термины
## Отформатировать псевдокод
## Оформить правильно источники информации
## Добавить пример графа, на котором алгоритм работает экспоненциальное время
## Категории
# '''!!!''' [[Алгоритм A*]] (8)
## что-то со второй картиночкой, там гифка, а почему-то не отображается
## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.
## какая-то тут муть написана, что в корректности, что в оптимальности
## а еще можно написать про случай с монотонной эвристикой
## Оформить правильно англоязычные термины
## Оформить правильно ссылки примечаниями и источники информации
# [[Алгоритм D*]]
# [[Эвристики для поиска кратчайших путей]] (2)
## "Дано" криво оформлено
## Заменить дефисы на тире
## Оформить правильно источники информации и англоязычные термины
## Оформить правильно списки, заглавные буквы корректно расставить
## Ссылку на основную статью оформить правильно
## Таблички сделать красивыми

== 9. Задача о паросочетании ==
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] (2-3)
## Добавить картинок паросочетаний различных красивых (две-три хватит)
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] (2)
## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое
## Интервики
## Отформатировать псевдокод
## Картинки заползают на заголовки, придумать что-нибудь с этим
## == в тексте заменить на =
## Оформить правильно источники информации
# [[Алгоритм Куна для поиска максимального паросочетания]]
# [[Теорема Холла]] (1.5)
## добавить ссылку на английскую википедию
## Англоязычные термины
## Дефисы на тире
## Оформить доказательство правильно и красиво
## Исправить знаки неравенств
## Константы в Tex
## Примечания маленькие
## Добавить больше ссылок, заменить на источники информации
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] (1)
## Оформить правильно источники информации
## Убрать neat в определении
## Убрать <br> 
## Англоязычные термины оформить правильно
## Пункт Определения не нужен
## Оформить красиво списки
# [[Связь вершинного покрытия и независимого множества]]
## См. предыдущее
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] (2)
## Англоязычные термины оформить правильно
## Дублируется определение совершенного паросочетания
## Пояснить про независимые переменные
## И что за детерминант от элемента матрицы, а не самой матрицы?
## - -> {{---}}
## Источники информации
# [[Теорема Татта о существовании полного паросочетания]] (0.5)
## Оформить правильно англоязычные термины
## Оформить правильно и красиво доказательства
## Убрать граф из mathbb
## Сделать ссылку примечанием
## Источники информации
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
# '''!!!''' [[Декомпозиция Эдмондса-Галлаи]] (5)
## Много пустых строк
## Пробелы перед открывающей круглой скобкой
## Определение нечётных компонент дублируется с конспектом из теоремы Татта
## Переменные в Tex
## Дефисы на тире
## Добавить доказательства теорем (хотя бы одной (ну или хотя бы ссылки примечаниями))
## Убрать заголовки первого уровня
# '''!!!''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
## Переменные и константы в Tex
## Добавить сначала постановку задачи
## Кривая ссылка на паросочетание
## Дефисы на тире
## Определения выделять жирным
## Отформатировать псевдокоды
## Зачем-то списки в доказательствах лемм использованы
## Битая ссылка на соседей
## Надо бы доказать все леммы
## Оформить правильно источники информации
## И вообще всё оформить надо

== 10. Задача о максимальном потоке (проверяется) ==
# ''fixed'' [[Определение сети, потока]]
## Оформить правильно источники информации
## Правильно оформить англоязычные термины
## Интервики
## Исправить знаки неравенств
## Дефисы на тире
# '''!!!''' [[Разрез, лемма о потоке через разрез]]
## Оформить правильно англоязычные термины
## Списки кривые
## Определения выделить жирным
## Дефисы превратить в тире
## Убрать ; из леммы, сделать маркированный список
## Исправить знаки неравенств
## Скобки в тексте кое-где лишние
## Источники информации 
## Нарисовать красивую картинку вместо текущей
# '''fixed''' [[Дополняющая сеть, дополняющий путь]]
## Англоязычные термины правильно оформить
## Оформить правильно источники информации
## Нарисовать пример
# ''fixed'' [[Лемма о сложении потоков]]
## Дефисы на тире
## Знаки неравенств
## Убрать "Аналогичная"
# [[Теорема Форда-Фалкерсона]]
## Знаки неравенств, источники информации
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
## гм, и зачем "дельта" русским словом в псевдокоде?
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока и отрефакторить псевдокод
## Константы взять в Tex
## Источники информации
## Знаки неравенств
# '''!!!''' [[Алоритм Эдмондса-Карпа]]
## а описание алгоритма где?
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
## ссылки на русскую/английскую википедию
## Отформатировать псевдокод
## while в тексте обернуть в \mathrm
## Знаки неравенств
## Добавить про грибок в конспект
# [[Алгоритм масштабирования потока]]
## ссылки на русскую/английскую википедию
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
## Отформатировать псевдокод
# [[Блокирующий поток]]
## англоязычные термины
## ссылки на русскую и английскую википедию
## Добавить немного общей информации
# '''взяли''' [[Схема алгоритма Диница]]
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
## "makeGl" назвать как-нибудь нормально
## "algorithmDinica" тоже назвать нормально
## Интервики
## Написать более подробный псевдокод
# '''!!!''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
## "Мы можем применить Лемму(2" — лемму 3, наверное?
## Дефисы на тире, знаки неравенств, источники информации
# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]
## "Жадный Алгоритм" — зачем с большой буквы алгоритм?
## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то плохой, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# [[Метод проталкивания предпотока]]
## зачем какие-то кванторы в for?
##  initialaze -> initialize
## названия функций в тексте оборачиваются в \mathrm или \mathtt
## Англоязычные термины
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]
## названия функций в тексте оборачиваются в \mathrm или \mathtt
## relable -> relabel
## Англоязычные термины оформить правильно
## Отформатировать псевдокоды
# [[Теорема о декомпозиции]]
## кванторы в псевдокоде не нужну, написать просто not exists, и вообще отформатировать псевдокод
## Дефисы на тире
## Переписать формулировку теоремы
## Отформатировать псевдокод
## Оформить правильно источники информации
# [[Теорема о декомпозиционном барьере]]
## Источники информации
## Пояснить,почему такие константы используются
# [[Циркуляция потока]]
## англоязычные термины
## ссылки на русскую и английскую википедию
## раздел постановка задачи не нужен, перенести в заголовок, задачу можно в шаблон взять
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
## Источники информации
# [[Алгоритм Каргера для нахождения минимального разреза]]
## внутреннюю ссылку на мультиграф
## названия функций в тексте оборачиваются в \mathrm или \mathtt
## Англоязычные термины
## Отформартировать псевдокод

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