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

Материал из Викиконспекты
Перейти к: навигация, поиск
(6. Раскраски графов)
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 3ему терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показаны 34 промежуточные версии этого же участника)
Строка 4: Строка 4:
 
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 
# [[Лемма о рукопожатиях]]
 
# [[Лемма о рукопожатиях]]
# [[Теорема о существовании простого пути в случае существования пути]] (4)
+
# ''fixed'' [[Теорема о существовании простого пути в случае существования пути]] (4)
 
## Алгоритм и предположение зря оформлены как псевдокод
 
## Алгоритм и предположение зря оформлены как псевдокод
 
## Добавить ссылок
 
## Добавить ссылок
Строка 13: Строка 13:
 
# [[Теорема о существовании простого цикла в случае существования цикла]]
 
# [[Теорема о существовании простого цикла в случае существования цикла]]
 
# [[Матрица смежности графа]]
 
# [[Матрица смежности графа]]
# [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
+
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
 
## Добавить свойства матрицы инцидентности с доказательствами
 
## Добавить свойства матрицы инцидентности с доказательствами
 
## Добавить ссылок в источники информации
 
## Добавить ссылок в источники информации
Строка 21: Строка 21:
 
## Добавить про списки смежности и их оформить тоже в таблички
 
## Добавить про списки смежности и их оформить тоже в таблички
 
# [[Циклическое пространство графа]]
 
# [[Циклическое пространство графа]]
# [[Фундаментальные циклы графа]] (1)
+
# ''fixed'' [[Фундаментальные циклы графа]] (1)
 
## Источники информации нормально оформить
 
## Источники информации нормально оформить
 
## Подписать получше картинку
 
## Подписать получше картинку
 
## Заменить многоточия на \ldots
 
## Заменить многоточия на \ldots
 
## Отформатировать по правилам
 
## Отформатировать по правилам
# [[Дерево, эквивалентные определения]] (1)
+
# ''fixed'' [[Дерево, эквивалентные определения]] (1)
 
## Англоязычные термины
 
## Англоязычные термины
 
## Пофиксить знаки неравенств
 
## Пофиксить знаки неравенств
Строка 32: Строка 32:
 
## Оформить красиво доказательства
 
## Оформить красиво доказательства
 
# [[Алгоритмы на деревьях]]
 
# [[Алгоритмы на деревьях]]
# [[Дополнительный, самодополнительный граф]] (1)
+
# ''fixed'' [[Дополнительный, самодополнительный граф]] (1)
 
## Англоязычные термины оформить правильно
 
## Англоязычные термины оформить правильно
 
## Заменить угловые скобки на \langle и \rangle
 
## Заменить угловые скобки на \langle и \rangle
Строка 55: Строка 55:
 
# [[Граф блоков-точек сочленения]]
 
# [[Граф блоков-точек сочленения]]
 
# [[k-связность]]
 
# [[k-связность]]
# [[Теорема Менгера]] (0.5)
+
# ''fixed'' [[Теорема Менгера]] (0.5)
 
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
 
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
 
## Тире заменить на шаблон
 
## Тире заменить на шаблон
Строка 114: Строка 114:
 
<ol>
 
<ol>
 
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
 
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
<li> '''fixed''' [[Покрытие ребер графа путями]] (5)</li>
+
<li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li>
# Так и не надо определение почти связного графа {{---}} надо внести в предыдущий конспект, а здесь сделать интервики
+
# Какое-то мутное доказательства
# Знак "не принадлежит" оформить в Tex
+
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
# Что-то доказательство какое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей
+
# Какое-то мутное доказательство леммы про корректность алгоритма
# То же самое в достаточности
+
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
# Оформить правильно источники информации
 
# Категория
 
<li> ''fixed'' [[Алгоритм построения Эйлерова цикла]] (3) </li>
 
# Отформатировать псевдокод
 
# Довести до ума. Начиная с представления уже тяжко. До этого момента надо подытожить текущие доказательство, а то там много разных фактов и надо их как-то в одну пачку собрать, сказав, чего хочется достичь дальше.
 
# Категория
 
<li> '''fixed''' [[Произвольно вычерчиваемые из заданной вершины графы]] (6) </li>
 
# Англоязычные термины оформить правильно
 
# Что значит неодноэелементный?
 
# Стрелки слишком длинные
 
# На картинке ошибка {{---}} почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень
 
# Источники информации правильно оформить
 
# Хотелось бы больше пояснений в доказательстве
 
# В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить, используя в основе какой-то лес
 
# Категория
 
 
</ol>
 
</ol>
  
 
=== Гамильтоновы графы ===
 
=== Гамильтоновы графы ===
 
<ol>
 
<ol>
<li value="5"> '''fixed''' [[Гамильтоновы графы]] (6.5) </li>
+
<li value="5"> [[Гамильтоновы графы]] </li>
# Заменить дефисы на тире
+
<li> [[Теорема Хватала]] </li>
# Исправить знаки неравенств
 
# Отформатировать псевдокод
 
# Помёрджить с конспектом динамического программирования и пофиксить ошибки в обоих, если есть (должны остаться алгоритмы поиска пути/цикла, пути, минимизирующего какой-то критерий)
 
# Источники информации
 
# Категория
 
<li> ''fixed'' [[Теорема Хватала]] (0.5) </li>
 
# Исправить знаки неравенств
 
# Поставить \mid в множествах
 
# Лишние кавычки в доказательствах вокруг стрелок
 
# Убрать q.e.d
 
# Оформить правильно источники информации
 
# Категория
 
<li>[[Теорема Поша]]</li>
 
 
<li> [[Теорема Дирака]] </li>
 
<li> [[Теорема Дирака]] </li>
 
<li> [[Теорема Оре]] </li>
 
<li> [[Теорема Оре]] </li>
<li> '''fixed''' [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] (5) </li>
+
<li> [[Теорема Поша]]</li>
# Странные обозначения для графа и множеств вершин и рёбер
+
<li> [[Теорема Гуйя-Ури]] </li>
# Убрать умножение звёздочкой
+
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
# Заменить дефис на тире
+
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
# Отформатировать псевдокод
+
# Пояснить переходы в теореме
# Источники информации
+
# Внести пояснение в определение бонда
# Исправить знаки неравенств
+
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
# Категория
+
# Картинку сделать красивой
<li> '''fixed???''' [[Теорема Гринберга]] (5) </li>
+
<li> '''взяли''' [[Турниры]] (6) </li>
# Англоязычные термины оформить правильно
+
# Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
# Дефис заменить на тире
+
<li> [[Теорема Редеи-Камиона]] </li>
# Картинки криво расположены
 
# Ссылки поехали в примере
 
# Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачней
 
# Почему необходимое условие? А в обратную сторону?
 
# Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 грань
 
# Категория
 
<li> '''fixed''' [[Турниры]] (5) </li>
 
# Англоязычные термины
 
# Добавить оценку на число турниров в графе из n вершин
 
# Убрать лишние определения
 
# Оформить правильно источники информации
 
# Немного неправильно сформулировано утверждение про полустепени вершин
 
# Категория
 
12' '''!!!''' [[Турниры]] (5)
 
# Доказательства всех утверждений из конспекта (эквивалентность определений и конденсация)
 
<li> ''fixed'' [[Теорема Редеи-Камиона]] (0.5) </li>
 
# Исправить знаки неравенств
 
# Правильно оформить источники информации
 
# Категория
 
 
</ol>
 
</ol>
  
Строка 190: Строка 143:
 
# [[Укладка графа на плоскости]]
 
# [[Укладка графа на плоскости]]
 
# [[Формула Эйлера]]
 
# [[Формула Эйлера]]
# [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
+
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
 
## Исправить знаки неравенств
 
## Исправить знаки неравенств
 
## Источники информации
 
## Источники информации
Строка 205: Строка 158:
 
== 6. Раскраски графов ==
 
== 6. Раскраски графов ==
 
# [[Раскраска графа]]
 
# [[Раскраска графа]]
# [[Двудольные графы и раскраска в 2 цвета]] (3)
+
# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)
 
## Англоязычные термины
 
## Англоязычные термины
 
## Убрать определение двудольного графа и сделать интервики на основной конспект
 
## Убрать определение двудольного графа и сделать интервики на основной конспект
Строка 224: Строка 177:
  
 
== 7. Обход в глубину ==
 
== 7. Обход в глубину ==
# '''взяли''' [[Обход в глубину, цвета вершин]] (5)
+
# '''fixed''' [[Обход в глубину, цвета вершин]] (5)
 
## Англоязычные термины правильно оформить
 
## Англоязычные термины правильно оформить
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
## Переименовать конспект в Обход в глубину, DFS
 
 
## Красивую картинку с цветными вершинами
 
## Красивую картинку с цветными вершинами
 
# [[Лемма о белых путях]]
 
# [[Лемма о белых путях]]
# '''fixed''' [[Использование обхода в глубину для проверки связности]] (5)
+
# [[Использование обхода в глубину для проверки связности]]
## Отформатировать псевдокод
 
## Задачу в шаблон
 
## Добавить примеров задач, например, как по двум вершинам определять, являются ли они связанными в режиме online при добавлении рёбер
 
## Добавить источники информации, см. также
 
## Tex внутри конспекта сделать красивым
 
 
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
 
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
 
# [[Использование обхода в глубину для топологической сортировки]]
 
# [[Использование обхода в глубину для топологической сортировки]]
# ''fixed'' [[Использование обхода в глубину для поиска компонент сильной связности]] (3)
+
# [[Использование обхода в глубину для поиска компонент сильной связности]]
## Некрасивый список в доказательстве теоремы
+
# ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4)
## Отформатировать псевдокод
+
## Что-то картинки неудачно расположены
## Добавить ссылок
+
## Кривая структура у доказательства
# '''взяли''' [[Использование обхода в глубину для поиска точек сочленения]] (6)
 
## Убрать отступ в теореме
 
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 
## Источники информации красиво оформить
 
## Источники информации красиво оформить
## Добавить примеры того, когда и почему становится плохо, если функция up будет определена по-другому
+
# [[Построение компонент вершинной двусвязности]]
# ''fixed'' [[Построение компонент вершинной двусвязности]] (3)
+
# [[Использование обхода в глубину для поиска мостов]]
## Отформатировать псевдокод
+
# [[Построение компонент реберной двусвязности]]
## Красиво оформить источники
 
# ''fixed'' [[Использование обхода в глубину для поиска мостов]] (3)
 
## Заменить min на \min
 
## Отформатировать псевдокод
 
## Некрасиво оформлено утверждение маркированным списком, да и у тело утверждения тоже некрасивое
 
## Нормально оформить источники информации, добавить см. также
 
# ''fixed'' [[Построение компонент реберной двусвязности]] (3)
 
## Отформатировать псевдокод
 
## Визуализатор внести в источники информации
 
  
 
== 8. Кратчайшие пути в графах ==
 
== 8. Кратчайшие пути в графах ==
 
# [[Обход в ширину]]
 
# [[Обход в ширину]]
# ''fixed'' [[Алгоритм Форда-Беллмана]] (3)
+
# [[Алгоритм Форда-Беллмана]]
## Получшение введение, задачу в шаблон
+
# [[Алгоритм Дейкстры]]
## Интервики
+
# [[Алгоритм Флойда]]
## Отформатировать псевдокоды
+
# [[Алгоритм Джонсона]]
## for в тексте взять в mathrm
+
# [[Алгоритм Левита]]
## Заменить дефисы на тире
+
# [[Алгоритм A*]]
## Исправить знаки неравенств
 
## Оформить правильно источники информации
 
# ''fixed'' [[Алгоритм Дейкстры]] (3)
 
## Псевдокод вообще криво оформлен
 
## Исправить знаки неравенств
 
## Оформить правильно источники информации
 
## Табличку сделать красивой
 
# '''fixed''' [[Алгоритм Флойда]] (6)
 
## Оформить правильно источники информации
 
## Заменить min на \min
 
## Отформатировать правильно псевдокод
 
## Вспомнить алгоритм построение транзитивного замыкания на первом курсе
 
## Исправить в тексте знаки равенства и неравенства
 
## Оформить правильно источники информации
 
## Добавить оптимизацию с битовыми масками
 
# '''fixed''' [[Алгоритм Джонсона]] (7)
 
## Англоязычные термины
 
## Заменить дефисы на тире
 
## Зачем-то в шаблоне определение написано не определение
 
## Исправить знаки неравенств
 
## Отформатировать псевдокоды
 
## Доказательство со стрелочками красиво оформить
 
## Оформить правильно источники информации
 
## Расписать сложность других реализаций
 
# '''fixed''' [[Алгоритм Левита]] (7)
 
## Оформить правильно англоязычные термины
 
## Отформатировать псевдокод
 
## Оформить правильно источники информации
 
## Добавить пример графа, на котором алгоритм работает экспоненциальное время
 
## Категории
 
# '''fixed''' [[Алгоритм A*]] (8)
 
## что-то со второй картиночкой, там гифка, а почему-то не отображается
 
## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.
 
## какая-то тут муть написана, что в корректности, что в оптимальности
 
## а еще можно написать про случай с монотонной эвристикой
 
## Оформить правильно англоязычные термины
 
## Оформить правильно ссылки примечаниями и источники информации
 
 
# [[Алгоритм D*]]
 
# [[Алгоритм D*]]
# ''fixed'' [[Эвристики для поиска кратчайших путей]] (2)
+
# [[Эвристики для поиска кратчайших путей]]
## "Дано" криво оформлено
 
## Заменить дефисы на тире
 
## Оформить правильно источники информации и англоязычные термины
 
## Оформить правильно списки, заглавные буквы корректно расставить
 
## Ссылку на основную статью оформить правильно
 
## Таблички сделать красивыми
 
  
 
== 9. Задача о паросочетании ==
 
== 9. Задача о паросочетании ==
# ''fixed'' [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] (2-3)
+
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]  
## Добавить картинок паросочетаний различных красивых (две-три хватит)
+
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# ''fixed'' [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] (2)
 
## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое
 
## Интервики
 
## Отформатировать псевдокод
 
## Картинки заползают на заголовки, придумать что-нибудь с этим
 
## == в тексте заменить на =
 
## Оформить правильно источники информации
 
 
# [[Алгоритм Куна для поиска максимального паросочетания]]
 
# [[Алгоритм Куна для поиска максимального паросочетания]]
# ''fixed'' [[Теорема Холла]] (1.5)
+
# [[Теорема Холла]]
## добавить ссылку на английскую википедию
+
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
## Англоязычные термины
+
# [[Связь вершинного покрытия и независимого множества]]
## Дефисы на тире
+
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
## Оформить доказательство правильно и красиво
+
# [[Теорема Татта о существовании полного паросочетания]]
## Исправить знаки неравенств
 
## Константы в Tex
 
## Примечания маленькие
 
## Добавить больше ссылок, заменить на источники информации
 
# ''fixed'' [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] (1)
 
## Оформить правильно источники информации
 
## Убрать neat в определении
 
## Убрать <br>
 
## Англоязычные термины оформить правильно
 
## Пункт Определения не нужен
 
## Оформить красиво списки
 
# ''fixed'' [[Связь вершинного покрытия и независимого множества]]
 
## См. предыдущее
 
# ''fixed'' [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] (2)
 
## Англоязычные термины оформить правильно
 
## Дублируется определение совершенного паросочетания
 
## Пояснить про независимые переменные
 
## И что за детерминант от элемента матрицы, а не самой матрицы?
 
## - -> {{---}}
 
## Источники информации
 
# ''fixed'' [[Теорема Татта о существовании полного паросочетания]] (0.5)
 
## Оформить правильно англоязычные термины
 
## Оформить правильно и красиво доказательства
 
## Убрать граф из mathbb
 
## Сделать ссылку примечанием
 
## Источники информации
 
 
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
# '''fixed''' [[Декомпозиция Эдмондса-Галлаи]] (5)
+
# [[Декомпозиция Эдмондса-Галлаи]]
## Много пустых строк
+
# '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
## Пробелы перед открывающей круглой скобкой
 
## Определение нечётных компонент дублируется с конспектом из теоремы Татта
 
## Переменные в Tex
 
## Дефисы на тире
 
## Добавить доказательства теорем (хотя бы одной (ну или хотя бы ссылки примечаниями))
 
## Убрать заголовки первого уровня
 
# '''!!!''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
 
 
## Переменные и константы в Tex
 
## Переменные и константы в Tex
 
## Добавить сначала постановку задачи
 
## Добавить сначала постановку задачи
Строка 380: Строка 233:
 
== 10. Задача о максимальном потоке ==
 
== 10. Задача о максимальном потоке ==
 
# [[Определение сети, потока]]
 
# [[Определение сети, потока]]
# ''fixed'' [[Разрез, лемма о потоке через разрез]] (4)
+
# [[Разрез, лемма о потоке через разрез]]  
## Оформить правильно англоязычные термины
 
## Списки кривые
 
## Определения выделить жирным
 
## Дефисы превратить в тире
 
## Убрать ; из леммы, сделать маркированный список
 
## Исправить знаки неравенств
 
## Скобки в тексте кое-где лишние
 
## Источники информации
 
## Нарисовать красивую картинку вместо текущей
 
 
# [[Дополняющая сеть, дополняющий путь]]
 
# [[Дополняющая сеть, дополняющий путь]]
# ''fixed'' [[Лемма о сложении потоков]] (0.5)
+
# [[Лемма о сложении потоков]]
## Переименовать конспект
+
# [[Теорема Форда-Фалкерсона]]
## Убрать "Также есть..."
+
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
## Вынести названия лемм в заголовки шаблонов
+
# '''взяли''' [[Алоритм Эдмондса-Карпа]] (5)
# ''fixed'' [[Теорема Форда-Фалкерсона]] (0.5)
+
## Полностью описать пример про грибок с картинками в конспекте
## Знаки неравенств
+
# [[Алгоритм масштабирования потока]]
## Источники информации
+
# ''взяли'' [[Блокирующий поток]] (1)
# '''fixed''' [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] (5)
 
## гм, и зачем "дельта" русским словом в псевдокоде?
 
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока и отрефакторить псевдокод
 
## Константы взять в Tex
 
## Источники информации
 
## Знаки неравенств
 
## Подробней пояснить пример несходимости
 
# '''fixed''' [[Алоритм Эдмондса-Карпа]] (7)
 
## а описание алгоритма где?
 
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
 
## ссылки на русскую/английскую википедию
 
## Отформатировать псевдокод
 
## while в тексте обернуть в \mathrm
 
## Знаки неравенств
 
## Добавить про грибок в конспект
 
# ''fixed'' [[Алгоритм масштабирования потока]] (3)
 
## ссылки на русскую/английскую википедию
 
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
 
## Отформатировать псевдокод
 
## Источники информации
 
## См. также
 
## Увеличить картинки
 
# [[Блокирующий поток]] (1)
 
 
## англоязычные термины
 
## англоязычные термины
 
## ссылки на русскую и английскую википедию
 
## ссылки на русскую и английскую википедию
 
## Добавить немного общей информации
 
## Добавить немного общей информации
 
## Расположить красиво картинки, чтобы не наезжали
 
## Расположить красиво картинки, чтобы не наезжали
# '''fixed''' [[Схема алгоритма Диница]] (6)
+
# [[Схема алгоритма Диница]]
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
+
# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
## "makeGl" назвать как-нибудь нормально
 
## "algorithmDinica" тоже назвать нормально
 
## Интервики
 
## Написать более подробный псевдокод
 
# '''!!!''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
 
 
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
 
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
 
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
 
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
Строка 439: Строка 255:
 
## Знаки неравенств
 
## Знаки неравенств
 
## Источники информации
 
## Источники информации
# '''fixed''' [[Алгоритм поиска блокирующего потока в ациклической сети]] (5)
+
# [[Алгоритм поиска блокирующего потока в ациклической сети]]
## "Жадный Алгоритм" — зачем с большой буквы алгоритм?
 
## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то плохой, переписать псевдокод для этого алгоритма полностью, чтобы было приближено к реальной реализации
 
 
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
 
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# '''взяли''' [[Метод проталкивания предпотока]] (7)
+
# '''!!!''' [[Метод проталкивания предпотока]] (7)
## зачем какие-то кванторы в for?
+
## Картиночки с резервуарами!
##  initialaze -> initialize
+
## Источники информации
## названия функций в тексте оборачиваются в \mathrm или \mathtt
+
## Добавить см. также
## Англоязычные термины
+
## Дефисы заменить на тире
## Отформатировать псевдокоды
 
## Больше неформальных описаний, чтобы было понятно
 
## За картиночки с резервуарами {{---}} отдельные большие бонусы!
 
# '''fixed''' [[Алгоритм "поднять-в-начало"]] (5, но сначала лучше сделать предыдущий)
 
## названия функций в тексте оборачиваются в \mathrm или \mathtt
 
## relable -> relabel
 
## Англоязычные термины оформить правильно
 
 
## Отформатировать псевдокоды
 
## Отформатировать псевдокоды
# ''fixed'' [[Теорема о декомпозиции]] (3)
+
# [[Алгоритм "поднять-в-начало"]]
## Дефисы на тире
+
# [[Теорема о декомпозиции]]
## Переписать формулировку теоремы
+
# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)
## Отформатировать псевдокод
 
## Оформить правильно источники информации
 
# [[Теорема о декомпозиционном барьере]] (3)
 
 
## Источники информации
 
## Источники информации
 
## Пояснить,почему такие константы используются
 
## Пояснить,почему такие константы используются
 
## Увеличить дроби
 
## Увеличить дроби
 
## А что из этой теоремы следует?
 
## А что из этой теоремы следует?
# ''fixed'' [[Циркуляция потока]] (3)
+
# [[Циркуляция потока]]
## англоязычные термины
+
# [[Алгоритм Каргера для нахождения минимального разреза]]
## ссылки на русскую и английскую википедию
 
## раздел постановка задачи не нужен, перенести в заголовок, задачу можно в шаблон взять
 
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
 
## Источники информации
 
# ''fixed'' [[Алгоритм Каргера для нахождения минимального разреза]] (2)
 
## внутреннюю ссылку на мультиграф
 
## названия функций в тексте оборачиваются в \mathrm или \mathtt
 
## Англоязычные термины
 
## Отформартировать псевдокод
 
  
 
== 11. Задача о потоке минимальной стоимости ==
 
== 11. Задача о потоке минимальной стоимости ==
# '''fixed''' [[Поток минимальной стоимости]] (5)
+
# [[Поток минимальной стоимости]]
## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)
+
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
## Убрать "Определение задачи", из-под определения вынести формулировку в шаблон задача
+
# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
## Оформить правильно источники информации (и вообще всё оформить правильно)
 
## Добавить определений стоимости, свойства стоимости на обратных рёбрах, картинки нарисовать
 
# '''fixed''' [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] (0.5, вместе с алгоритмом)
 
## Исправить знаки неравенств
 
## Источники информации
 
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
 
 
## Интервики на декомпозицию
 
## Интервики на декомпозицию
 
## Знаки неравенств
 
## Знаки неравенств
 
## Источники информации
 
## Источники информации
# '''fixed''' [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] (4.5, вместе с теоремой)
+
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
## Помёрджить с теоремой Ф-Ф
 
## Отформатировать псевдокод
 
 
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
 
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
 
## Написать и оформить так, чтобы не было чуши
 
## Написать и оформить так, чтобы не было чуши
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)
+
# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)
 
## Взять задачи в шаблон
 
## Взять задачи в шаблон
 
## Оформить покрасивей и правильней
 
## Оформить покрасивей и правильней
# '''fixed''' [[Венгерский алгоритм решения задачи о назначениях]] (5)
+
# [[Венгерский алгоритм решения задачи о назначениях]]
## написать более подробный псевдокод
 
## Интервики
 
## Источники информации
 

Текущая версия на 19:15, 23 февраля 2017

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

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

  1. Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
  2. Лемма о рукопожатиях
  3. fixed Теорема о существовании простого пути в случае существования пути (4)
    1. Алгоритм и предположение зря оформлены как псевдокод
    2. Добавить ссылок
    3. Заменить названия способов доказательств на конструктивное и неконструктивное
    4. Исправить ошибку в доказательстве построением
    5. Плохо, что картинка наплывает на заголовок — переделать
    6. Добавить в формулировку теоремы, что вершинно-простой путь
  4. Теорема о существовании простого цикла в случае существования цикла
  5. Матрица смежности графа
  6. взяли Матрица инцидентности графа (4 или больше, зависит от свойств)
    1. Добавить свойства матрицы инцидентности с доказательствами
    2. Добавить ссылок в источники информации
    3. Англоязычные термины
    4. Оформить правильно источники информации
    5. Добавить См. также на матрицу смежности
    6. Добавить про списки смежности и их оформить тоже в таблички
  7. Циклическое пространство графа
  8. fixed Фундаментальные циклы графа (1)
    1. Источники информации нормально оформить
    2. Подписать получше картинку
    3. Заменить многоточия на \ldots
    4. Отформатировать по правилам
  9. fixed Дерево, эквивалентные определения (1)
    1. Англоязычные термины
    2. Пофиксить знаки неравенств
    3. Источники информации нормально оформить
    4. Оформить красиво доказательства
  10. Алгоритмы на деревьях
  11. fixed Дополнительный, самодополнительный граф (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. fixed Теорема Менгера (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. Укладки графов

  1. Укладка графа на плоскости
  2. Формула Эйлера
  3. fixed Непланарность [math]K_5[/math] и [math]K_{3,3}[/math] (0.5)
    1. Исправить знаки неравенств
    2. Источники информации
    3. Константы в Tex
  4. Укладка дерева
  5. Укладка графа с планарными компонентами реберной двусвязности
  6. Укладка графа с планарными компонентами вершинной двусвязности
  7. Теорема Понтрягина-Куратовского
  8. Род, толщина, крупность, число скрещиваний
  9. Двойственный граф планарного графа
  10. Теорема Фари
  11. Гамма-алгоритм

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

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

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

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

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

  1. Обход в ширину
  2. Алгоритм Форда-Беллмана
  3. Алгоритм Дейкстры
  4. Алгоритм Флойда
  5. Алгоритм Джонсона
  6. Алгоритм Левита
  7. Алгоритм A*
  8. Алгоритм D*
  9. Эвристики для поиска кратчайших путей

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. Разрез, лемма о потоке через разрез
  3. Дополняющая сеть, дополняющий путь
  4. Лемма о сложении потоков
  5. Теорема Форда-Фалкерсона
  6. Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
  7. взяли Алоритм Эдмондса-Карпа (5)
    1. Полностью описать пример про грибок с картинками в конспекте
  8. Алгоритм масштабирования потока
  9. взяли Блокирующий поток (1)
    1. англоязычные термины
    2. ссылки на русскую и английскую википедию
    3. Добавить немного общей информации
    4. Расположить красиво картинки, чтобы не наезжали
  10. Схема алгоритма Диница
  11. fixed Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями (6)
    1. может, назвать остаточную сеть [math]G_f[/math], как в предыдущих конспектах?
    2. "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
    3. В лемме в утверждении фигурирует поток [math]f[/math], но дальше про него ничего нет. Зачем он?
    4. "Мы можем применить Лемму(2" — лемму 3, наверное?
    5. Дефисы на тире
    6. Знаки неравенств
    7. Источники информации
  12. Алгоритм поиска блокирующего потока в ациклической сети
    1. !!! (10) алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
  13. !!! Метод проталкивания предпотока (7)
    1. Картиночки с резервуарами!
    2. Источники информации
    3. Добавить см. также
    4. Дефисы заменить на тире
    5. Отформатировать псевдокоды
  14. Алгоритм "поднять-в-начало"
  15. Теорема о декомпозиции
  16. fixed Теорема о декомпозиционном барьере (3)
    1. Источники информации
    2. Пояснить,почему такие константы используются
    3. Увеличить дроби
    4. А что из этой теоремы следует?
  17. Циркуляция потока
  18. Алгоритм Каргера для нахождения минимального разреза

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

  1. Поток минимальной стоимости
  2. Теорема Форда-Фалкерсона о потоке минимальной стоимости
  3. fixed Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети (0.5)
    1. Интервики на декомпозицию
    2. Знаки неравенств
    3. Источники информации
  4. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
  5. !!! Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
    1. Написать и оформить так, чтобы не было чуши
  6. взяли Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0.5)
    1. Взять задачи в шаблон
    2. Оформить покрасивей и правильней
  7. Венгерский алгоритм решения задачи о назначениях