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

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

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

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

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

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

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

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

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

1. Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
   1. Изменить название конспекта на "Эйлеровость графов"
   2. Оформить следствие красиво
   3. Правильно оформить источники информации
2. !!! Покрытие ребер графа путями
   1. Так и не надо определение почти связного графа — надо внести в предыдущий конспект, а здесь сделать интервики
   2. Знак "не принадлежит" оформить в Tex
   3. Что-то доказательство какое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей
   4. То же самое в достаточности
   5. Оформить правильно источники информации
3. !!! Алгоритм построения Эйлерова цикла
   1. Отформатировать псевдокод
   2. Добавить в него проверку на Эйлеровость
   3. Можно сказать, как удалять рёбра за O(1), чтобы не вводить читателей в заблуждение
   4. Источники информации
   5. Хотелось бы более подробное объяснение фактов в доказательстве, а не то что "заметим", "обратим внимание"
4. !!! Произвольно вычерчиваемые из заданной вершины графы
   1. Англоязычные термины оформить правильно
   2. Что значит неодноэелементный?
   3. Стрелки слишком длинные
   4. На картинке ошибка — почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень
   5. Источники информации правильно оформить
   6. Хотелось бы больше пояснений в доказательстве
   7. В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить,используя в основе какой-то лес
5. !!! Гамильтоновы графы
   1. Заменить дефисы на тире
   2. Исправить знаки неравенств
   3. Отформатировать псевдокод
   4. Помёрджить с конспектом динамического программирования
6. Теорема Хватала
   1. Исправить знаки неравенств
   2. Поставить \mid в множествах
   3. Лишние кавычки в доказательствах вокруг стрелок
   4. Убрать q.e.d
   5. Оформить правильно источники информации
7. Теорема Дирака
   1. Заменить дефис на тире
   2. Исправить знаки неравенств
   3. max правильно написать
   4. Лучше путь P обозначить через \dots
   5. Источники информации правильно оформить
   6. Интервики
   7. Добавить вывод из теоремы Оре
8. Теорема Оре
   1. Исправить знаки неравенств
   2. Интервики
   3. Всё в Tex оформить
   4. Источники информации правильно оформить
9. !!! Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
   1. Странные обозначения для графа и множеств вершин и рёбер
   2. Убрать умножение звёздочкой
   3. Заменить дефис на тире
   4. Отформатировать псевдокод
   5. Добавить алгоритм поиска цикла (пути) в условиях этих теорем по отдельности
   6. Источники информации
   7. Исправить знаки неравенств
10. !!! Теорема Гринберга (можно получить 10 баллов за правки)
    1. Англоязычные термины оформить правильно
    2. Дефис заменить на тире
    3. Картинки криво расположены
    4. Ссылки поехали в примере
    5. Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачней
    6. Почему необходимое условие? А в обратную сторону? А кто напишет алгоритм, то вообще молодец
    7. Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 грань
11. !!! Турниры
    1. Англоязычные термины
    2. Добавить оценку на число турниров в графе из n вершин
    3. Убрать лишние определения
    4. Оформить правильно источники информации
    5. Немного неправильно сформулировано утверждение про полустепени вершин
12. Теорема Редеи-Камиона
    1. Исправить знаки неравенств
    2. Правильно оформить источники информации

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

1. Укладка графа на плоскости
   1. Англоязычные термины правильно оформить
   2. Добавить пару ссылок на конспекты вычгеома о том, чем хороши планарные графы
2. Формула Эйлера
   1. Исправить знаки неравенств
   2. Заменить литературу на источники информации
   3. Добавить ссылок
3. Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
   1. Исправить знаки неравенств
   2. Источники информации
4. Укладка дерева
   1. Заменить sup и inf на \sup и \inf
   2. Заменить дефисы на тире
   3. Картинки адекватно расположить
   4. Англоязычные термины правильно оформить
   5. Источники информации правильно оформить, добавить примеры визуализации
5. Укладка графа с планарными компонентами реберной двусвязности
   1. Заменить источники на источники информации
   2. Взять все переменные в Tex
6. Укладка графа с планарными компонентами вершинной двусвязности
   1. Исправить знаки неравенств
   2. Заменить источники на источники информации
7. !!! Теорема Понтрягина-Куратовского (можно получить 10 баллов за все правки
   1. Перерисовать картинки пиксельные убогие
   2. Термины в определениях выделить жирным
   3. Англоязычные термины
   4. Вынести нумерацию в леммах в заголовок
   5. Заменить дефисы на тире
   6. Точка после многоточия некрасиво выглядит
   7. Разбор случаев a, b, c, d, u1, u2, v1, v2 криво отформатирован
   8. Картинки в разборе лучше увеличить
   9. Добавить ссылок в источники информации
   10. Добавить немного общей информации в начало конспекта
8. Двойственный граф планарного графа
   1. Добавить пробел после "двойственным" в определении
   2. Интервики
   3. Убрать neat из определения самодвойственного графа
   4. Увеличить дроби
   5. Добавить источники информации
9. Теорема Фари

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

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

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

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

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

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

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

в процессе проверки 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. написать более подробный псевдокод