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

Материал из Викиконспекты
Перейти к: навигация, поиск
(4. Обходы графов)
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 3ему терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показано 217 промежуточных версий этого же участника)
Строка 2: Строка 2:
  
 
== 1. Основные определения теории графов ==
 
== 1. Основные определения теории графов ==
# '''fixed''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
+
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
## Правильно оформить англоязычные термины
 
## "Иногда граф, построенный таким образом, называют псевдографом (pseudograph)" {{---}} кривовато написано, надо переписать
 
## Дублируется определение смежных вершин
 
## Добавить ссылок в источники информации
 
## Добавить определение полного графа
 
## Несправедливо забыли дерево в часто используемых графах; добавить другие виды графов
 
 
# [[Лемма о рукопожатиях]]
 
# [[Лемма о рукопожатиях]]
## Увеличить дроби
+
# ''fixed'' [[Теорема о существовании простого пути в случае существования пути]] (4)
## Взять константы в tex
 
## Заменить умножение на \cdot
 
## Добавить пару слов о графах с петлями и кратными рёбрами
 
# '''взяли''' [[Теорема о существовании простого пути в случае существования пути]]
 
 
## Алгоритм и предположение зря оформлены как псевдокод
 
## Алгоритм и предположение зря оформлены как псевдокод
 
## Добавить ссылок
 
## Добавить ссылок
Строка 21: Строка 11:
 
## Плохо, что картинка наплывает на заголовок {{---}} переделать
 
## Плохо, что картинка наплывает на заголовок {{---}} переделать
 
## Добавить в формулировку теоремы, что вершинно-простой путь
 
## Добавить в формулировку теоремы, что вершинно-простой путь
# '''взяли''' [[Теорема о существовании простого цикла в случае существования цикла]]
+
# [[Теорема о существовании простого цикла в случае существования цикла]]
## На самом деле, конструктивное доказательство тут не очень понятное и не совсем корректное. Сделать неконструктивное и добавить нормальные картинки
 
## Добавить в первую теорему, что граф неориентированный
 
## Добавить источники информации
 
 
# [[Матрица смежности графа]]
 
# [[Матрица смежности графа]]
## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два
+
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
## Что за помеченный граф?
 
## Добавить про что, в матрице смежности можно хранить веса рёбер
 
# [[Связь степени матрицы смежности и количества путей]]
 
## Это можно внести в прошлый конспект
 
## Добавить что-нибудь про бинарное возведение в степень
 
# '''взяли''' [[Матрица инцидентности графа]]
 
 
## Добавить свойства матрицы инцидентности с доказательствами
 
## Добавить свойства матрицы инцидентности с доказательствами
 
## Добавить ссылок в источники информации
 
## Добавить ссылок в источники информации
# '''взяли''' [[Циклическое пространство графа]]
+
## Англоязычные термины
## Пункт "Определение" не нужен, см. правила форматирования
+
## Оформить правильно источники информации
## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
+
## Добавить См. также на матрицу смежности
## интервики
+
## Добавить про списки смежности и их оформить тоже в таблички
## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
+
# [[Циклическое пространство графа]]
## Заменить тире на шаблон
+
# ''fixed'' [[Фундаментальные циклы графа]] (1)
## Добавить ссылок в источники информации
 
## Неплохо бы написать, зачем это нужно (позволяет какие-нибудь теоремы про графы доказать или что-то ещё)
 
# [[Фундаментальные циклы графа]]
 
 
## Источники информации нормально оформить
 
## Источники информации нормально оформить
# [[Дерево, эквивалентные определения]]
+
## Подписать получше картинку
 +
## Заменить многоточия на \ldots
 +
## Отформатировать по правилам
 +
# ''fixed'' [[Дерево, эквивалентные определения]] (1)
 +
## Англоязычные термины
 +
## Пофиксить знаки неравенств
 
## Источники информации нормально оформить
 
## Источники информации нормально оформить
# '''!!!''' [[Диаметр дерева]]
+
## Оформить красиво доказательства
## Переименовать в Алгоритмы на деревьях
+
# [[Алгоритмы на деревьях]]
## Добавить другие алгоритмы (если будет много содержательных, то можно будет поставить <tex> 10 </tex> баллов за конспект)
+
# ''fixed'' [[Дополнительный, самодополнительный граф]] (1)
## Отформатировать псевдокод
 
## Добавить категории, ссылки, см. также
 
## Интервики
 
## Исправить tex
 
# [[Дополнительный, самодополнительный граф]]
 
 
## Англоязычные термины оформить правильно
 
## Англоязычные термины оформить правильно
 
## Заменить угловые скобки на \langle и \rangle
 
## Заменить угловые скобки на \langle и \rangle
Строка 60: Строка 38:
 
## Добавить ссылки в источники информации
 
## Добавить ссылки в источники информации
 
## Шаблоном заменить тире
 
## Шаблоном заменить тире
 +
# [[Теоретико-множественные операции над графами]]
 +
# [[Рёберное ядро]] (2)
 +
## Добавить больше интервики в конспект
 +
## В конце теоремы в доказательстве какая-то лажа
 +
## Источники информации
 +
## Оформить следствия красиво
 +
# [[Факторизация графов]]
  
 
== 2. Связность в графах ==
 
== 2. Связность в графах ==
 
# [[Отношение связности, компоненты связности]]
 
# [[Отношение связности, компоненты связности]]
## англоязычные термины
 
## интервики
 
## Заменить тире на шаблон
 
## Добавить См. также
 
 
# [[Отношение реберной двусвязности]]
 
# [[Отношение реберной двусвязности]]
## англоязычные термины
 
 
# [[Отношение вершинной двусвязности]]
 
# [[Отношение вершинной двусвязности]]
## англоязычные термины
+
# [[Точка сочленения, эквивалентные определения]]
## Добавить ссылок
+
# [[Мост, эквивалентные определения]]
 
# [[Граф компонент реберной двусвязности]]
 
# [[Граф компонент реберной двусвязности]]
## Нормально оформить источники информации и см. также
 
## Вообще, граф G необязательно должен быть связен, можно расширить и доказать, что будет лес
 
 
# [[Граф блоков-точек сочленения]]
 
# [[Граф блоков-точек сочленения]]
## См. выше
 
## Капс какой-то зачем-то
 
# [[Точка сочленения, эквивалентные определения]]
 
## Цифры в начале определений не нужны, их можно в хедер определения
 
# [[Мост, эквивалентные определения]]
 
## англоязычные термины
 
## Цифры в начале определений не нужны, их можно в хедер определения
 
## Нормально оформить источники информации и см. также
 
 
# [[k-связность]]
 
# [[k-связность]]
## англоязычные термины
+
# ''fixed'' [[Теорема Менгера]] (0.5)
## Тире заменить на шаблон
 
## Палку вертикальную в множестве заменить на \mid
 
## Странное обозначение {{---}} \smallsetminus
 
# [[Теорема Менгера]]
 
 
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
 
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
 
## Тире заменить на шаблон
 
## Тире заменить на шаблон
 
## Можно добавить ссылок, оформить см. также по-другому
 
## Можно добавить ссылок, оформить см. также по-другому
 +
## Источники информации
 
# [[Теорема Менгера, альтернативное доказательство]]
 
# [[Теорема Менгера, альтернативное доказательство]]
## Заменить тире на шаблон
+
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
## Обращение к леммам сделать через интервики
 
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
 
## пункт "Определения" не нужен
 
## пункт "Определения" не нужен
 
## Изменить знаки неравенств в tex
 
## Изменить знаки неравенств в tex
 
## Не надо дублировать определения из другого конспекта
 
## Не надо дублировать определения из другого конспекта
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 +
## find_flow какой-то стрёмный
 +
## Источники информации
 +
## k-связность с маленькой буквы
 +
## Добавить См. также на что-нибудь разумное
 
## Добавить см. также
 
## Добавить см. также
  
 
== 3. Остовные деревья ==
 
== 3. Остовные деревья ==
# '''!!!''' [[Лемма о безопасном ребре]]
+
=== Построение остовных деревьев ===
## Англоязычные термины оформить правильно
+
<ol>
## Внести G' в определение
+
<li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li>
## Переименовать конспект
+
<li>[[Алгоритм Прима]]</li>
## Добавить пару слов о поиске остовного дерева в незвешенном графе со ссылкой на Краскала
+
<li> [[Алгоритм Краскала]] </li>
## Оформить правильно источники информации
+
<li> [[Алгоритм Борувки]] </li>
## Исправить знаки неравенств в Tex
+
<li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li>
# '''fixed''' [[Алгоритм Прима]]
+
# Доказательство красиво оформить
## Англоязычные термины правильно оформить
+
# Заменить дефис на шаблон
## Добавить интервики
+
# Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
## Отформатировать псевдокод
+
# Почему ребро uv {{---}} единственное ребро, пересекающее разрез?
## Заменить inf в табличках примера на "бесконечность"
+
# Источники информации
## Добавить отступов описанию примера
+
# Знаки неравенств
## Источники информации правильно оформить
+
# Категория
# '''взяли''' [[Алгоритм Краскала]]
+
<li> '''!!!''' [[Алгоритм двух китайцев]] (7) </li>
## Англоязычные термины правильно оформить
+
# Англоязычные термины оформить правильно
## Добавить интервики
+
# Добавить определение покрывающего дерева
## Заменить дефис на Шаблон:Тире
+
# Описать реализацию красиво
## Реализацию оформить псевдокодом
+
# Дефис заменить на тире
## Добавить отступы в описание примера
+
# Отформатировать псевдокод
## Оформить источники информации правильно
+
# Доказать, почему не более V конденсаций
## Добавить пару слов о поиске остовного дерева в незвешенном графе
+
# Источники информации оформить правильно
# '''взяли''' [[Алгоритм Борувки]]
+
# Доказать второе замечание
## Англоязычные термины правильно оформить
+
# Добавить отступы в описании примера
## Описание алгоритма оформить красиво и чуточку понятней
+
# 5ый пункт в описании алгоритма расписать чуть понятней
## Доказательство теоремы оформить красиво
+
# Категория
## Отформатировать псевдокод
+
</ol>
## Пример как-то кривовато описан
+
 
## Заменить дефис на шаблон
+
=== Свойства остовных деревьев ===
## Источники информации правильно оформить
+
<ol>
## Доказательство асимптотики добавить
+
<li value="7">[[Матрица Кирхгофа]]</li>
# '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
+
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
## Доказательство красиво оформить
+
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
## Заменить дефис на шаблон
+
<li> [[Количество помеченных деревьев]] </li>
## Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
+
<li> [[Коды Прюфера]] </li>
## Почему ребро uv {{---}} единственное ребро, пересекающее разрез?
+
</ol>
# '''!!!''' [[Алгоритм двух китайцев]]
 
## Англоязычные термины оформить правильно
 
## Добавить определение покрывающего дерева
 
## Описать реализацию красиво
 
## Дефис заменить на тире
 
## Отформатировать псевдокод
 
## Доказать, почему не более V конденсаций
 
## Источники информации оформить правильно
 
## Доказать второе замечание
 
## Добавить отступы в описании примера
 
## 5ый пункт в описании алгоритма расписать чуть понятней
 
# '''!!!''' [[Матрица Кирхгофа]]
 
## Ссылка на простой граф плохо сделана. Добавить определение в самый первый конспект и сделать на него ссылку
 
## Источники информации и см. также нормально оформить
 
## Константы взять в Tex
 
## Оформить свойства прилично
 
## Добавить ещё свойств по возможности
 
# [[Связь матрицы Кирхгофа и матрицы инцидентности]]
 
## Константы взять в Tex
 
## См. также и источники информации
 
# [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 
## Добавить ссылку на формулу Бине-Коши (примечание на википедию или интервики на конспект линала)
 
## Источники и см. также
 
## Исправить знаки неравенств
 
## Заменить тире на шаблон
 
# [[Количество помеченных деревьев]]
 
## англоязычные термины
 
# [[Коды Прюфера]]
 
## Не оформлять описание алгоритма как псевдокод
 
  
 
== 4. Обходы графов ==
 
== 4. Обходы графов ==
# [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
+
=== Эйлеровы графы ===
## Изменить название конспекта на "Эйлеровость графов"
+
<ol>
## Оформить следствие красиво
+
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
## Правильно оформить источники информации
+
<li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li>
# '''!!!''' [[Покрытие ребер графа путями]]
+
# Какое-то мутное доказательства
## Так и не надо определение почти связного графа {{---}} надо внести в предыдущий конспект, а здесь сделать интервики
+
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
## Знак "не принадлежит" оформить в Tex
+
# Какое-то мутное доказательство леммы про корректность алгоритма
## Что-то доказательство какое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей
+
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
## То же самое в достаточности
+
</ol>
## Оформить правильно источники информации
+
 
# '''!!!''' [[Алгоритм построения Эйлерова цикла]]
+
=== Гамильтоновы графы ===
## Отформатировать псевдокод
+
<ol>
## Добавить в него проверку на Эйлеровость
+
<li value="5"> [[Гамильтоновы графы]] </li>
## Можно сказать, как удалять рёбра за O(1), чтобы не вводить читателей в заблуждение
+
<li> [[Теорема Хватала]] </li>
## Источники информации
+
<li> [[Теорема Дирака]] </li>
## Хотелось бы более подробное объяснение фактов в доказательстве, а не то что "заметим", "обратим внимание"
+
<li> [[Теорема Оре]] </li>
# '''!!!''' [[Произвольно вычерчиваемые из заданной вершины графы]]
+
<li> [[Теорема Поша]]</li>
## Англоязычные термины оформить правильно
+
<li> [[Теорема Гуйя-Ури]] </li>
## Что значит неодноэелементный?
+
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
## Стрелки слишком длинные
+
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
## На картинке ошибка {{---}} почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень
+
# Пояснить переходы в теореме
## Источники информации правильно оформить
+
# Внести пояснение в определение бонда
## Хотелось бы больше пояснений в доказательстве
+
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
## В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить,используя в основе какой-то лес
+
# Картинку сделать красивой
# '''!!!''' [[Гамильтоновы графы]]
+
<li> '''взяли''' [[Турниры]] (6) </li>
## Заменить дефисы на тире
+
# Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
## Исправить знаки неравенств
+
<li> [[Теорема Редеи-Камиона]] </li>
## Отформатировать псевдокод
+
</ol>
## Помёрджить с конспектом динамического программирования
 
# [[Теорема Хватала]]
 
## Исправить знаки неравенств
 
## Поставить \mid в множествах
 
## Лишние кавычки в доказательствах вокруг стрелок
 
## Убрать q.e.d
 
## Оформить правильно источники информации
 
# ''fixed'' [[Теорема Дирака]]
 
## Заменить дефис на тире
 
## Исправить знаки неравенств
 
## max правильно написать
 
## Лучше путь P обозначить через \dots
 
## Источники информации правильно оформить
 
## Интервики
 
## Добавить вывод из теоремы Оре
 
# [[Теорема Оре]]
 
## Исправить знаки неравенств
 
## Интервики
 
## Всё в Tex оформить
 
## Источники информации правильно оформить
 
# '''!!!''' [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 
## Странные обозначения для графа и множеств вершин и рёбер
 
## Убрать умножение звёздочкой
 
## Заменить дефис на тире
 
## Отформатировать псевдокод
 
## Добавить алгоритм поиска цикла (пути) в условиях этих теорем по отдельности
 
## Источники информации
 
## Исправить знаки неравенств
 
# '''!!!''' [[Теорема Гринберга]] ''(можно получить 10 баллов за правки)''
 
## Англоязычные термины оформить правильно
 
## Дефис заменить на тире
 
## Картинки криво расположены
 
## Ссылки поехали в примере
 
## Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачней
 
## Почему необходимое условие? А в обратную сторону? А кто напишет алгоритм, то вообще молодец
 
## Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 грань
 
# '''!!!''' [[Турниры]]
 
## Англоязычные термины
 
## Добавить оценку на число турниров в графе из n вершин
 
## Убрать лишние определения
 
## Оформить правильно источники информации
 
## Немного неправильно сформулировано утверждение про полустепени вершин
 
# [[Теорема Редеи-Камиона]]
 
## Исправить знаки неравенств
 
## Правильно оформить источники информации
 
  
 
== 5. Укладки графов ==
 
== 5. Укладки графов ==
 
# [[Укладка графа на плоскости]]
 
# [[Укладка графа на плоскости]]
## Англоязычные термины правильно оформить
 
## Добавить пару ссылок на конспекты вычгеома о том, чем хороши планарные графы
 
 
# [[Формула Эйлера]]
 
# [[Формула Эйлера]]
## Исправить знаки неравенств
+
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
## Заменить литературу на источники информации
 
## Добавить ссылок
 
# [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
 
 
## Исправить знаки неравенств
 
## Исправить знаки неравенств
 
## Источники информации
 
## Источники информации
 +
## Константы в Tex
 
# [[Укладка дерева]]
 
# [[Укладка дерева]]
## Заменить sup и inf на \sup и \inf
 
## Заменить дефисы на тире
 
## Картинки адекватно расположить
 
## Англоязычные термины правильно оформить
 
## Источники информации правильно оформить, добавить примеры визуализации
 
 
# [[Укладка графа с планарными компонентами реберной двусвязности]]
 
# [[Укладка графа с планарными компонентами реберной двусвязности]]
## Заменить источники на источники информации
 
## Взять все переменные в Tex
 
 
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
## Исправить знаки неравенств
+
# [[Теорема Понтрягина-Куратовского]]
## Заменить источники на источники информации
+
# [[Род, толщина, крупность, число скрещиваний]]
# '''!!!''' [[Теорема Понтрягина-Куратовского]] (''можно получить 10 баллов за все правки''
 
## Перерисовать картинки пиксельные убогие
 
## Термины в определениях выделить жирным
 
## Англоязычные термины
 
## Вынести нумерацию в леммах в заголовок
 
## Заменить дефисы на тире
 
## Точка после многоточия некрасиво выглядит
 
## Разбор случаев a, b, c, d, u1, u2, v1, v2 криво отформатирован
 
## Картинки в разборе лучше увеличить
 
## Добавить ссылок в источники информации
 
## Добавить немного общей информации в начало конспекта
 
 
# [[Двойственный граф планарного графа]]
 
# [[Двойственный граф планарного графа]]
## Добавить пробел после "двойственным" в определении
 
## Интервики
 
## Убрать neat из определения самодвойственного графа
 
## Увеличить дроби
 
## Добавить источники информации
 
 
# [[Теорема Фари]]
 
# [[Теорема Фари]]
 +
# [[Гамма-алгоритм]]
  
 
== 6. Раскраски графов ==
 
== 6. Раскраски графов ==
# '''!!!''' [[Раскраска графа]]
+
# [[Раскраска графа]]
## Правильно оформить англоязычные термины
+
# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)
## Заменить \phi на \varphi
 
## Пункт "Хроматическое число" не нужен
 
## Заменить дефисы на тире
 
## Пояснить, что такое нулевой граф
 
## Список хроматических чисел нормально оформить
 
## Четвёртый пример заменить на двудольные графы (дерево, в частности, является таким)
 
## Оформить правильно источники информации
 
## Примечания перенести выше
 
## Кинуть интервики на неразрешимость задачи о раскраске графа
 
## Написать о связи хроматического числа и хроматического многочлена, и почему нельзя найти хроматическое число, если у нас есть такая замечательная штука, как хроматический многочлен?
 
# [[Двудольные графы и раскраска в 2 цвета]]
 
 
## Англоязычные термины
 
## Англоязычные термины
 +
## Убрать определение двудольного графа и сделать интервики на основной конспект
 
## Картинку двудольного графа перенести ниже, а то плохо смотрится
 
## Картинку двудольного графа перенести ниже, а то плохо смотрится
 
## Интервики
 
## Интервики
 
## Добавить, что можно ещё за проход в ширину проверить
 
## Добавить, что можно ещё за проход в ширину проверить
## Оформить правильно источники информации
+
## Оформить правильно источники информации и См. также
 
## Перенести см. также до источников информации, а ссылку заменить на интервики
 
## Перенести см. также до источников информации, а ссылку заменить на интервики
# '''!!!''' [[Хроматический многочлен]]
+
# [[Хроматический многочлен]]
## Англоязычные термины
+
# [[Формула Зыкова]]
## Пустой граф обозвать удачней, а примечание выделить жирным
+
# [[Формула Уитни]]
## Теорему о хроматическом многочлене красиво оформить
 
## Обозначение стягивания ребра перенести перед теоремой о цветах дерева, а лучше дерево вообще ближе к концу перенести
 
## Заменить дефисы на тире
 
## Интервики
 
## Убрать запятые и точки после многоточий в теореме о коэффициентах
 
## Добавить формулы хроматических многочленов цикла и колеса
 
## Оформить правильно источники информации
 
# '''!!!''' [[Формула Зыкова]]
 
## Определения выделить жирным
 
## Англоязычные термины правильно оформить
 
## Написать более подробное, понятное и корректное доказательство
 
## Исправить знаки неравенств
 
## Правильно оформить источники информации
 
## Добавить см. также
 
# '''!!!''' [[Формула Уитни]]
 
## Заменить дефисы на тире
 
## Исправить знаки неравенств
 
## Заменить \phi на \varphi
 
## Правильно оформить источники информации
 
## А что такое собственные и несобственный раскраски?
 
## Пояснить непонятные места в доказательстве в целом
 
## Добавить см. также
 
 
# [[Теорема Брукса]]
 
# [[Теорема Брукса]]
## Заменить дефисы на тире
 
## Интервики
 
## "на iом шаге" {{---}} пропущен дефис
 
## Исправить знаки неравенств
 
## Оформить правильно источники информации
 
## Добавить см. также
 
 
# [[Верхние и нижние оценки хроматического числа]]
 
# [[Верхние и нижние оценки хроматического числа]]
## Заменить дефисы на тире
 
## Исправить знаки неравенств
 
## Интервики
 
## Англоязычные термины
 
## Заменить max на \max
 
## Все переменные взять в Tex
 
## Увеличить дроби
 
## Оформить правильно источники информации
 
 
# [[Хроматическое число планарного графа]]
 
# [[Хроматическое число планарного графа]]
## Все константы взять в Tex
 
## Первая лемма {{---}} тривиальное следствие из теоремы Понтрягина-Куратовского
 
## Доказательство по индукции красиво оформить
 
## Заменить дефисы на тире
 
## Исправить знаки неравенств
 
## Теорема о 5-раскраске планарного графа именная {{---}} Хивуд {{---}} дать ей название
 
## Оформить правильно источники информации
 
 
# [[Многочлен Татта]]
 
# [[Многочлен Татта]]
## Заменить дефисы на тире
+
# [[Теория Рамсея]] ('''10''')
## " Уитни (Whiney rank polynomial)." {{---}} кажется, пропущено t
 
## "Показатели в формуле раногового" {{---}} зачем это в определение вносить?
 
## Интервики
 
## Оформить правильно источники информации
 
# [[Теория Рамсея]]
 
 
## Тут вообще ад какой-то
 
## Тут вообще ад какой-то
  
 
== 7. Обход в глубину ==
 
== 7. Обход в глубину ==
# [[Обход в глубину, цвета вершин]]
+
# '''fixed''' [[Обход в глубину, цвета вершин]] (5)
 
## Англоязычные термины правильно оформить
 
## Англоязычные термины правильно оформить
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 +
## Красивую картинку с цветными вершинами
 
# [[Лемма о белых путях]]
 
# [[Лемма о белых путях]]
## Добавить источников, см. также
+
# [[Использование обхода в глубину для проверки связности]]
# '''!!!''' [[Использование обхода в глубину для проверки связности]]
+
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
## Отформатировать псевдокод
+
# [[Использование обхода в глубину для топологической сортировки]]
## Зачем-то задачи, алгорим и реализация сделаны маркированным списком. Изменить структуру конспекта
 
## Добавить примеров задач, например, как по двум вершинам определять, являются ли они связанными в режиме online
 
## Добавить источники информации, см. также
 
## Tex внутри конспекта сделать красивым
 
# '''!!!''' [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
 
## Заменить тире на шаблон
 
## Отформатировать псевдокод
 
## Добавить ссылок в источники информации
 
## Пункт "реализация" какой-то несодержательный
 
## Добавить алгоритм поиска цикла в неориентированном графе, переименовав конспект
 
# '''!!!''' [[Использование обхода в глубину для топологической сортировки]]
 
## Неформальное определение написать по-человечески
 
## Отформатировать псевдокод
 
## Добавить пару о слов (или пару строк кода) о проверке графа на ацикличность, если нельзя вершины отсортировать топологически
 
## Добавить см. также, красифо оформить источники информации
 
## Добавить пример задачи, где нужна топологическая сортировка (конкретной задачи, а не примеры из введения)
 
 
# [[Использование обхода в глубину для поиска компонент сильной связности]]
 
# [[Использование обхода в глубину для поиска компонент сильной связности]]
## Некрасивый список в доказательстве теоремы
+
# ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4)
## Отформатировать псевдокод
+
## Что-то картинки неудачно расположены
## Добавить ссылок
+
## Кривая структура у доказательства
# '''!!!''' [[Использование обхода в глубину для поиска точек сочленения]]
 
## Убрать отступ в теореме
 
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 
## Источники информации красиво оформить
 
## Источники информации красиво оформить
## Добавить примеры того, когда и почему становится плохо, если функция up будет определена по-другому
 
 
# [[Построение компонент вершинной двусвязности]]
 
# [[Построение компонент вершинной двусвязности]]
## Отформатировать псевдокод
 
## Красиво оформить источники
 
 
# [[Использование обхода в глубину для поиска мостов]]
 
# [[Использование обхода в глубину для поиска мостов]]
## Заменить min на \min
 
## Отформатировать псевдокод
 
## Некрасиво оформлено утверждение маркированным списком, да и у тело утверждения тоже некрасивое
 
## Нормаоьно оформить источники информации, добавить см. также
 
 
# [[Построение компонент реберной двусвязности]]
 
# [[Построение компонент реберной двусвязности]]
## Отформатировать псевдокод
 
## Визуализатор внести в источники информации
 
  
 
== 8. Кратчайшие пути в графах ==
 
== 8. Кратчайшие пути в графах ==
# '''!!!''' [[Обход в ширину]]
+
# [[Обход в ширину]]
## Оформить правильно англоязычные термины
 
## Интервики
 
## Отформатировать псевдокод
 
## Добавить другие примеры использования бфс {{---}} рёбра 0 и 1, рёбра до k
 
## Оформить правильно источники информации
 
 
# [[Алгоритм Форда-Беллмана]]
 
# [[Алгоритм Форда-Беллмана]]
## Интервики
 
## Отформатировать псевдокоды
 
## for в тексте взять в mathrm
 
## Заменить дефисы на тире
 
## Исправить знаки неравенств
 
## Оформить правильно источники информации
 
 
# [[Алгоритм Дейкстры]]
 
# [[Алгоритм Дейкстры]]
## Псевдокод вообще криво оформлен
+
# [[Алгоритм Флойда]]
## Исправить знаки неравенств
+
# [[Алгоритм Джонсона]]
## Оформить правильно источники информации
+
# [[Алгоритм Левита]]
# '''!!!''' [[Алгоритм Левита]]
+
# [[Алгоритм A*]]
## Оформить правильно англоязычные термины
+
# [[Алгоритм D*]]
## Отформатировать псевдокод
 
## Оформить правильно источники информации
 
## Добавить пример графа, на котором алгоритм работает экспоненциальное время
 
# '''!!!''' [[Алгоритм Флойда]]
 
## Оформить правильно источники информации
 
## Заменить min на \min
 
## Отформатировать правильно псевдокод
 
## Вспомнить алгоритм построение транзитивного замыкания на первом курсе
 
## Исправить в тексте знаки равенства и неравенства
 
## Оформить правильно источники информации
 
## Добавить оптимизацию с битовыми масками
 
# '''!!!''' [[Алгоритм A*]]
 
## что-то со второй картиночкой, там гифка, а почему-то не отображается
 
## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.
 
## какая-то тут муть написана, что в корректности, что в оптимальности
 
## а еще можно написать про случай с монотонной эвристикой
 
## Оформить правильно англоязычные термины
 
## Оформить правильно ссылки примечаниями и источники информации
 
# '''!!!''' [[Алгоритм Джонсона]]
 
## Англоязычные термины
 
## Заменить дефисы на тире
 
## Зачем-то в шаблоне определение написано не определение
 
## Исправить знаки неравенств
 
## Отформатировать псевдокоды
 
## Доказательство со стрелочками красиво оформить
 
## Оформить правильно источники информации
 
 
# [[Эвристики для поиска кратчайших путей]]
 
# [[Эвристики для поиска кратчайших путей]]
## "Дано" криво оформлено
 
## Заменить дефисы на тире
 
## Оформить правильно источники информации и англоязычные термины
 
# [[Алгоритм D*]]
 
## Оформить правильно англоязычные термины
 
## Отформатировать псевдокоды
 
## Оформить правильно источники информации
 
  
== 10. Задача о паросочетании ==
+
== 9. Задача о паросочетании ==
# '''!!!''' [[Теорема о максимальном паросочетании и дополняющих цепях]]
+
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]  
## Конспект дублируется, убрать его
 
## Сделать общий конспект про паросочетания, определения и свойства, взять информацию из других конспектов
 
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое
+
# [[Алгоритм Куна для поиска максимального паросочетания]]
## Интервики
 
## Отформатировать псевдокод
 
## == в тексте заменить на =
 
## Оформить правильно источники информации
 
# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]
 
## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы
 
## код -- копипаста с емакса
 
## источники перечислять с помощью *, а не :
 
## Криво оформлено описание алгоритма
 
## В конспекте по ссылке теоремы Бержа нет этой теоремы :(
 
 
# [[Теорема Холла]]
 
# [[Теорема Холла]]
## добавить ссылку на английскую википедию
 
## Англоязычные термины
 
## Дефисы на тире
 
## Оформить доказательство правильно
 
## Исправить знаки неравенств
 
## Константы в Tex
 
## Примечания маленькие
 
## Добавить больше ссылок, заменить на источники информации
 
 
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
## Оформить правильно источники информации
 
## Убрать neat в определении
 
## Убрать <br>
 
## Англоязычные термины оформить правильно
 
## Пункт Определения не нужен
 
 
# [[Связь вершинного покрытия и независимого множества]]
 
# [[Связь вершинного покрытия и независимого множества]]
## См. предыдущее
+
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
# '''!!!''' [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
## Англоязычные термины оформить правильно
 
## Дублируется определение совершенного паросочетания
 
## Пояснить про независимые переменные
 
## И что за детерминант от элемента матрицы, а не самой матрицы?
 
## - -> {{---}}
 
## Источники информации
 
 
# [[Теорема Татта о существовании полного паросочетания]]
 
# [[Теорема Татта о существовании полного паросочетания]]
## Оформить правильно англоязычные термины
+
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## Убрать граф из mathbb
+
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
## Сделать ссылку примечанием
+
# [[Декомпозиция Эдмондса-Галлаи]]
## Источники информации
+
# '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример
 
# '''!!!''' [[Декомпозиция Эдмондса-Галлаи]]
 
## Много пустых строк
 
## Пробелы перед открывающей круглой скобкой
 
## Определение нечётных компонент дублируется с конспектом из теоремы Татта
 
## Переменные в Tex
 
## Дефисы на тире
 
## Добавить доказательства теорем (хотя бы одной)
 
## Убрать заголовки первого уровня
 
# '''!!!''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
 
 
## Переменные и константы в Tex
 
## Переменные и константы в Tex
 
## Добавить сначала постановку задачи
 
## Добавить сначала постановку задачи
Строка 531: Строка 229:
 
## Надо бы доказать все леммы
 
## Надо бы доказать все леммы
 
## Оформить правильно источники информации
 
## Оформить правильно источники информации
 +
## И вообще всё оформить надо
  
== 11. Задача о максимальном потоке ==
+
== 10. Задача о максимальном потоке ==
 
# [[Определение сети, потока]]
 
# [[Определение сети, потока]]
## Оформить правильно источники информации
+
# [[Разрез, лемма о потоке через разрез]]  
## Правильно оформить англоязычные термины
+
# [[Дополняющая сеть, дополняющий путь]]
## Интервики
 
## Исправить знаки неравенств
 
## Дефисы на тире
 
# [[Разрез, лемма о потоке через разрез]]
 
## Оформить правильно англоязычные термины
 
## Списки кривые
 
## Определения выделить жирным
 
## Дефисы превратить в тире
 
## Убрать ; из леммы, сделать маркированный список
 
## Исправить знаки неравенств
 
## Скобки в тексте кое-где лишние
 
## Источники информации
 
# '''!!!''' [[Дополняющая сеть, дополняющий путь]]
 
## Англоязычные термины правильно оформить
 
## Оформить правильно источники информации
 
## Нарисовать пример
 
 
# [[Лемма о сложении потоков]]
 
# [[Лемма о сложении потоков]]
## Дефисы на тире
 
## Знаки неравенств
 
## Убрать "Аналогичная"
 
 
# [[Теорема Форда-Фалкерсона]]
 
# [[Теорема Форда-Фалкерсона]]
## Знаки неравенств, источники информации
 
 
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
## гм, и зачем "дельта" русским словом в псевдокоде?
+
# '''взяли''' [[Алоритм Эдмондса-Карпа]] (5)
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока и отрефакторить псевдокод
+
## Полностью описать пример про грибок с картинками в конспекте
## Константы взять в Tex
 
## Источники информации
 
## Знаки неравенств
 
# '''!!!''' [[Алоритм Эдмондса-Карпа]]
 
## а описание алгоритма где?
 
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
 
## ссылки на русскую/английскую википедию
 
## Отформатировать псевдокод
 
## while в тексте обернуть в \mathrm
 
## Знаки неравенств
 
## Добавить про грибок в конспект
 
 
# [[Алгоритм масштабирования потока]]
 
# [[Алгоритм масштабирования потока]]
## ссылки на русскую/английскую википедию
+
# ''взяли'' [[Блокирующий поток]] (1)
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
 
## Отформатировать псевдокод
 
# [[Блокирующий поток]]
 
 
## англоязычные термины
 
## англоязычные термины
 
## ссылки на русскую и английскую википедию
 
## ссылки на русскую и английскую википедию
 
## Добавить немного общей информации
 
## Добавить немного общей информации
# '''!!!''' [[Схема алгоритма Диница]]
+
## Расположить красиво картинки, чтобы не наезжали
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
+
# [[Схема алгоритма Диница]]
## "makeGl" назвать как-нибудь нормально
+
# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
## "algorithmDinica" тоже назвать нормально
 
## Интервики
 
## Написать более подробный псевдокод
 
# '''!!!''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 
 
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
 
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?
+
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
 
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
 
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
 
## "Мы можем применить Лемму(2" — лемму 3, наверное?
 
## "Мы можем применить Лемму(2" — лемму 3, наверное?
## Дефисы на тире, знаки неравенств, источники информации
+
## Дефисы на тире
# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]
+
## Знаки неравенств
## "Жадный Алгоритм" — зачем с большой буквы алгоритм?
+
## Источники информации
## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то плохой, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации
+
# [[Алгоритм поиска блокирующего потока в ациклической сети]]
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
+
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
# [[Метод проталкивания предпотока]]
+
# '''!!!''' [[Метод проталкивания предпотока]] (7)
## зачем какие-то кванторы в for?
+
## Картиночки с резервуарами!
## initialaze -> initialize
+
## Источники информации
## названия функций в тексте оборачиваются в \mathrm или \mathtt
+
## Добавить см. также
## Англоязычные термины
+
## Дефисы заменить на тире
 
## Отформатировать псевдокоды
 
## Отформатировать псевдокоды
 
# [[Алгоритм "поднять-в-начало"]]
 
# [[Алгоритм "поднять-в-начало"]]
## названия функций в тексте оборачиваются в \mathrm или \mathtt
 
## relable -> relabel
 
## Англоязычные термины оформить правильно
 
## Отформатировать псевдокоды
 
 
# [[Теорема о декомпозиции]]
 
# [[Теорема о декомпозиции]]
## кванторы в псевдокоде не нужну, написать просто not exists, и вообще отформатировать псевдокод
+
# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)
## Дефисы на тире
 
## Переписать формулировку теоремы
 
## Отформатировать псевдокод
 
## Оформить правильно источники информации
 
# [[Теорема о декомпозиционном барьере]]
 
 
## Источники информации
 
## Источники информации
 
## Пояснить,почему такие константы используются
 
## Пояснить,почему такие константы используются
 +
## Увеличить дроби
 +
## А что из этой теоремы следует?
 
# [[Циркуляция потока]]
 
# [[Циркуляция потока]]
## англоязычные термины
 
## ссылки на русскую и английскую википедию
 
## раздел постановка задачи не нужен, перенести в заголовок, задачу можно в шаблон взять
 
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
 
## Источники информации
 
 
# [[Алгоритм Каргера для нахождения минимального разреза]]
 
# [[Алгоритм Каргера для нахождения минимального разреза]]
## внутреннюю ссылку на мультиграф
 
## названия функций в тексте оборачиваются в \mathrm или \mathtt
 
## Англоязычные термины
 
## Отформартировать псевдокод
 
  
== 12. Задача о потоке минимальной стоимости ==
+
== 11. Задача о потоке минимальной стоимости ==
# '''!!!''' [[Поток минимальной стоимости]]
+
# [[Поток минимальной стоимости]]
## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)
 
## Убрать "Определение задачи", из-под определения вынести формулировку в шаблон задача
 
## Оформить правильно источники информации
 
## Добавить определений стоимости, свойства стоимости на обратных рёбрах, картинки нарисовать
 
 
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
 
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
## Исправить знаки неравенств
+
# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
## Источники информации
 
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
 
 
## Интервики на декомпозицию
 
## Интервики на декомпозицию
 
## Знаки неравенств
 
## Знаки неравенств
# '''!!!''' [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
+
## Источники информации
## Помёрджить с теоремой Ф-Ф
+
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
## Отформатировать псевдокод
+
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
+
## Написать и оформить так, чтобы не было чуши
## Определение выделить жирным
+
# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.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. Венгерский алгоритм решения задачи о назначениях