Участник:Shersh/Тикеты к 3ему терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Гамильтоновы графы)
(→‎Эйлеровы графы)
Строка 187: Строка 187:
 
# Довести до ума. Начиная с представления уже тяжко. До этого момента надо подытожить текущие доказательство, а то там много разных фактов и надо их как-то в одну пачку собрать, сказав, чего хочется достичь дальше.
 
# Довести до ума. Начиная с представления уже тяжко. До этого момента надо подытожить текущие доказательство, а то там много разных фактов и надо их как-то в одну пачку собрать, сказав, чего хочется достичь дальше.
 
# Категория
 
# Категория
−
<li> '''!!!''' [[Произвольно вычерчиваемые из заданной вершины графы]] (6) </li>
+
<li> '''взяли''' [[Произвольно вычерчиваемые из заданной вершины графы]] (6) </li>
 
# Англоязычные термины оформить правильно
 
# Англоязычные термины оформить правильно
 
# Что значит неодноэелементный?
 
# Что значит неодноэелементный?

Версия 15:28, 28 января 2016

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

1. Основные определения теории графов

  1. Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
  2. fixed Лемма о рукопожатиях (1)
    1. Увеличить дроби
    2. Взять константы в tex
    3. Заменить умножение на \cdot
    4. Добавить пару слов о графах с петлями и кратными рёбрами
    5. Заменить источники на источники информации
  3. взяли Теорема о существовании простого пути в случае существования пути (4)
    1. Алгоритм и предположение зря оформлены как псевдокод
    2. Добавить ссылок
    3. Заменить названия способов доказательств на конструктивное и неконструктивное
    4. Исправить ошибку в доказательстве построением
    5. Плохо, что картинка наплывает на заголовок — переделать
    6. Добавить в формулировку теоремы, что вершинно-простой путь
  4. Теорема о существовании простого цикла в случае существования цикла
  5. fixed Матрица смежности графа (3) вместе со следующим
    1. "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два
    2. Что за помеченный граф?
    3. Добавить про что, в матрице смежности можно хранить веса рёбер
    4. Оформить правильно источники информации
    5. Добавить оценку на память матрицы смежности и привести примеры, когда эффективно её использовать, а когда нет
  6. взяли Связь степени матрицы смежности и количества путей вместе с предыдущим
    1. Это можно внести в прошлый конспект
    2. Добавить что-нибудь про бинарное возведение в степень
  7. взяли Матрица инцидентности графа (4 или больше, зависит от свойств)
    1. Добавить свойства матрицы инцидентности с доказательствами
    2. Добавить ссылок в источники информации
    3. Англоязычные термины
    4. Оформить правильно источники информации
    5. Добавить См. также на матрицу смежности
    6. Добавить про списки смежности и их оформить тоже в таблички
  8. Циклическое пространство графа
  9. взяли Фундаментальные циклы графа (0.5)
    1. Источники информации нормально оформить
    2. Подписать получше картинку
    3. Заменить многоточия на \ldots
  10. взяли Дерево, эквивалентные определения (0.5)
    1. Англоязычные термины
    2. Пофиксить знаки неравенств
    3. Источники информации нормально оформить
  11. Алгоритмы на деревьях
  12. взяли Дополнительный, самодополнительный граф (1)
    1. Англоязычные термины оформить правильно
    2. Заменить угловые скобки на \langle и \rangle
    3. Интервики
    4. Добавить ссылки в источники информации
    5. Шаблоном заменить тире
  13. Теоретико-множественные операции над графами

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

  1. fixed Отношение связности, компоненты связности (0.5)
    1. англоязычные термины
    2. интервики
    3. Заменить тире на шаблон
    4. Добавить См. также
  2. fixed Отношение реберной двусвязности (0.5)
    1. англоязычные термины
    2. Оформить правильно источники информации
    3. Перенести из См. также визуализатор в источники информации
  3. fixed Отношение вершинной двусвязности (0.5)
    1. англоязычные термины
    2. Добавить ссылок
    3. Оформить правильно источники информации
  4. fixed Точка сочленения, эквивалентные определения (0.5)
    1. Англоязычные термины
    2. Цифры в начале определений не нужны, их можно в заголовок определения
    3. Оформить пункты в теореме маркированным списком через #
    4. Источники информации
  5. fixed Мост, эквивалентные определения (0.5)
    1. См. выше
  6. fixed Граф компонент реберной двусвязности (0.5)
    1. Нормально оформить источники информации и см. также
    2. Англоязычные термины
    3. Избавить от a) и б) в доказательстве
  7. fixed Граф блоков-точек сочленения (0.5)
    1. См. выше
    2. Капс какой-то зачем-то
  8. fixed k-связность (0.5)
    1. англоязычные термины
    2. Тире заменить на шаблон
    3. Дефисы в определениях ровно поставить
    4. Палку вертикальную в множестве заменить на \mid
    5. Странное обозначение — \smallsetminus
    6. Источники информации
  9. Теорема Менгера (0.5)
    1. убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
    2. Тире заменить на шаблон
    3. Можно добавить ссылок, оформить см. также по-другому
    4. Источники информации
  10. fixed Теорема Менгера, альтернативное доказательство (0.5)
    1. Заменить тире на шаблон
    2. Обращение к леммам сделать через интервики
    3. См. также на оригинальное доказательство
    4. Источники информации
  11. Вершинная, реберная связность, связь между ними и минимальной степенью вершины (1.5)
    1. пункт "Определения" не нужен
    2. Изменить знаки неравенств в tex
    3. Не надо дублировать определения из другого конспекта
    4. Отформатировать псевдокод
    5. find_flow какой-то стрёмный
    6. Источники информации
    7. k-связность с маленькой буквы
    8. Добавить См. также на что-нибудь разумное
    9. Добавить см. также

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

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

  1. Остовные деревья: определения, лемма о безопасном ребре
  2. Алгоритм Прима
  3. Алгоритм Краскала
  4. fixed Алгоритм Борувки (5)
    1. Описание алгоритма оформить красиво и чуточку понятней
    2. Доказательство теоремы оформить красиво
    3. Переделать доказательства с учётом возможного равенства рёбер
    4. Отформатировать псевдокод
    5. Пример как-то кривовато описан (особенно это разделение на компоненты связности)
    6. Заменить дефис на шаблон
    7. Источники информации правильно оформить
    8. Категория
  5. !!! Теорема Тарьяна (критерий минимальности остовного дерева) (5)
    1. Доказательство красиво оформить
    2. Заменить дефис на шаблон
    3. Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
    4. Почему ребро uv — единственное ребро, пересекающее разрез?
    5. Источники информации
    6. Знаки неравенств
    7. Категория
  6. !!! Алгоритм двух китайцев (6)
    1. Англоязычные термины оформить правильно
    2. Добавить определение покрывающего дерева
    3. Описать реализацию красиво
    4. Дефис заменить на тире
    5. Отформатировать псевдокод
    6. Доказать, почему не более V конденсаций
    7. Источники информации оформить правильно
    8. Доказать второе замечание
    9. Добавить отступы в описании примера
    10. 5ый пункт в описании алгоритма расписать чуть понятней
    11. Категория

Свойства остовных деревьев

  1. Матрица Кирхгофа
  2. fixed Связь матрицы Кирхгофа и матрицы инцидентности (0.5)
    1. Англоязычные термины
    2. Константы взять в Tex
    3. См. также и источники информации
    4. Категория
  3. fixed Подсчет числа остовных деревьев с помощью матрицы Кирхгофа (0.5)
    1. Добавить ссылку на формулу Бине-Коши (примечание на википедию или интервики на конспект линала)
    2. Источники и см. также
    3. Исправить знаки неравенств
    4. Заменить тире на шаблон
    5. Категория
  4. fixed Количество помеченных деревьев (0.5)
    1. Англоязычные термины
    2. Первый пункт не нужен
    3. Категория
    4. Оформить доказательство красиво
    5. См. также и источники информации
    6. = в Tex
  5. fixed Коды Прюфера (0.5)
    1. Не оформлять описание алгоритма как псевдокод
    2. Англоязычные термины
    3. Категория
    4. См. также и Источники информации

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

Эйлеровы графы

  1. Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
  2. fixed Покрытие ребер графа путями (5)
    1. Так и не надо определение почти связного графа — надо внести в предыдущий конспект, а здесь сделать интервики
    2. Знак "не принадлежит" оформить в Tex
    3. Что-то доказательство какое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей
    4. То же самое в достаточности
    5. Оформить правильно источники информации
    6. Категория
  3. fixed Алгоритм построения Эйлерова цикла (3)
    1. Отформатировать псевдокод
    2. Довести до ума. Начиная с представления уже тяжко. До этого момента надо подытожить текущие доказательство, а то там много разных фактов и надо их как-то в одну пачку собрать, сказав, чего хочется достичь дальше.
    3. Категория
  4. взяли Произвольно вычерчиваемые из заданной вершины графы (6)
    1. Англоязычные термины оформить правильно
    2. Что значит неодноэелементный?
    3. Стрелки слишком длинные
    4. На картинке ошибка — почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень
    5. Источники информации правильно оформить
    6. Хотелось бы больше пояснений в доказательстве
    7. В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить, используя в основе какой-то лес
    8. Категория

Гамильтоновы графы

  1. fixed Гамильтоновы графы (6.5)
    1. Заменить дефисы на тире
    2. Исправить знаки неравенств
    3. Отформатировать псевдокод
    4. Помёрджить с конспектом динамического программирования и пофиксить ошибки в обоих, если есть (должны остаться алгоритмы поиска пути/цикла, пути, минимизирующего какой-то критерий)
    5. Источники информации
    6. Категория
  2. fixed Теорема Хватала (0.5)
    1. Исправить знаки неравенств
    2. Поставить \mid в множествах
    3. Лишние кавычки в доказательствах вокруг стрелок
    4. Убрать q.e.d
    5. Оформить правильно источники информации
    6. Категория
  3. Теорема Поша
  4. Теорема Дирака
  5. Теорема Оре
  6. fixed Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре (5)
    1. Странные обозначения для графа и множеств вершин и рёбер
    2. Убрать умножение звёздочкой
    3. Заменить дефис на тире
    4. Отформатировать псевдокод
    5. Источники информации
    6. Исправить знаки неравенств
    7. Категория
  7. взяли Теорема Гринберга (5)
    1. Англоязычные термины оформить правильно
    2. Дефис заменить на тире
    3. Картинки криво расположены
    4. Ссылки поехали в примере
    5. Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачней
    6. Почему необходимое условие? А в обратную сторону?
    7. Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 грань
    8. Категория
  8. fixed Турниры (5)
    1. Англоязычные термины
    2. Добавить оценку на число турниров в графе из n вершин
    3. Убрать лишние определения
    4. Оформить правильно источники информации
    5. Немного неправильно сформулировано утверждение про полустепени вершин
    6. Категория

    12' !!! Турниры (5)

    1. Доказательства всех утверждений из конспекта (эквивалентность определений и конденсация)
  9. fixed Теорема Редеи-Камиона (0.5)
    1. Исправить знаки неравенств
    2. Правильно оформить источники информации
    3. Категория

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

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

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

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

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

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

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

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

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

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

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

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

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

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