Участник:Shersh/Тикеты к 3ему терму

Материал из Викиконспекты
< Участник:Shersh
Версия от 19:08, 22 сентября 2016; Shersh (обсуждение | вклад) (→‎9. Задача о паросочетании)
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

  1. Матрица Кирхгофа
  2. Связь матрицы Кирхгофа и матрицы инцидентности
  3. Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
  4. Количество помеченных деревьев
  5. Коды Прюфера

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

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

  1. Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
  2. Покрытие ребер графа путями (3)
    1. Какое-то мутное доказательства
  3. Алгоритм построения Эйлерова цикла (2)
    1. Какое-то мутное доказательство леммы про корректность алгоритма
  4. Произвольно вычерчиваемые из заданной вершины графы

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

  1. Гамильтоновы графы
  2. Теорема Хватала
  3. Теорема Дирака
  4. Теорема Оре
  5. Теорема Поша
  6. Теорема Гуйя-Ури
  7. Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
  8. !!! Теорема Гринберга (5)
    1. Пояснить переходы в теореме
    2. Внести пояснение в определение бонда
    3. И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
    4. Картинку сделать красивой
  9. !!! Турниры (6)
    1. Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
  10. Теорема Редеи-Камиона

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

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

  1. Раскраска графа
  2. взяли Двудольные графы и раскраска в 2 цвета (3)
    1. Англоязычные термины
    2. Убрать определение двудольного графа и сделать интервики на основной конспект
    3. Картинку двудольного графа перенести ниже, а то плохо смотрится
    4. Интервики
    5. Добавить, что можно ещё за проход в ширину проверить
    6. Оформить правильно источники информации и См. также
    7. Перенести см. также до источников информации, а ссылку заменить на интервики
  3. Хроматический многочлен
  4. Формула Зыкова
  5. Формула Уитни
  6. Теорема Брукса
  7. Верхние и нижние оценки хроматического числа
  8. Хроматическое число планарного графа
  9. Многочлен Татта
  10. Теория Рамсея (10)
    1. Тут вообще ад какой-то

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

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

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

  1. Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
  2. Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
  3. Алгоритм Куна для поиска максимального паросочетания
  4. Теорема Холла
  5. Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
  6. Связь вершинного покрытия и независимого множества
  7. Матрица Татта и связь с размером максимального паросочетания в двудольном графе
  8. Теорема Татта о существовании полного паросочетания
  9. !!! Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
    1. как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
  10. Декомпозиция Эдмондса-Галлаи
  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. fixed Алгоритм поиска блокирующего потока в ациклической сети (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=55424»