Изменения

# ''fixed'' [[Лемма о рукопожатиях]] (1)## Увеличить дроби## Взять константы в tex## Заменить умножение на \cdot## Добавить пару слов о графах с петлями и кратными рёбрами## Заменить источники на источники информации# ''взялиfixed'' [[Теорема о существовании простого пути в случае существования пути]] (4)

# ''fixed'' [[Матрица смежности графа]] (3) ''вместе со следующим''## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два## Что за помеченный граф?## Добавить про что, в матрице смежности можно хранить веса рёбер## Оформить правильно источники информации## Добавить оценку на память матрицы смежности и привести примеры, когда эффективно её использовать, а когда нет# ''взяли'' [[Связь степени матрицы смежности и количества путей]] ''вместе с предыдущим''## Это можно внести в прошлый конспект## Добавить что-нибудь про бинарное возведение в степень

# ''взялиfixed'' [[Фундаментальные циклы графа]] (0.51)

## Отформатировать по правилам# ''взялиfixed'' [[Дерево, эквивалентные определения]] (0.51)

# ''взялиfixed'' [[Дополнительный, самодополнительный граф]] (1)

# ''fixed'' [[Отношение связности, компоненты связности]] (0.5)## англоязычные термины## интервики## Заменить тире на шаблон## Добавить См. также# ''fixed'' [[Отношение реберной двусвязности]] (0.5)## англоязычные термины## Оформить правильно источники информации## Перенести из См. также визуализатор в источники информации# [[Отношение вершинной двусвязности]] (0.5)## англоязычные термины## Добавить ссылок## Оформить правильно источники информации# ''взяли'' [[Точка сочленения, эквивалентные определения]] (0.5)## Англоязычные термины## Цифры в начале определений не нужны, их можно в хедер определения## Оформить пункты в теореме маркированным списком через ### Источники информации# [[Мост, эквивалентные определения]] (0.5)## См. выше# [[Граф компонент реберной двусвязности]] (0.5)## Нормально оформить источники информации и см. также## Англоязычные термины## Избавить от a) и б) в доказательстве# [[Граф блоков-точек сочленения]] (0.5)## См. выше## Капс какой-то зачем-то# ''взяли'' [[k-связность]] (0.5)## англоязычные термины## Тире заменить на шаблон## Дефисы в определениях ровно поставить## Палку вертикальную в множестве заменить на \mid## Странное обозначение {{---}} \smallsetminus## Источники информации# ''взялиfixed'' [[Теорема Менгера]] (0.5)

# [[Теорема Менгера, альтернативное доказательство]] (0.5)## Заменить тире на шаблон## Обращение к леммам сделать через интервики## См. также на оригинальное доказательство## Источники информации

<li> '''fixed''' [[Алгоритм Борувки]] (5) </li># Описание алгоритма оформить красиво и чуточку понятней# Доказательство теоремы оформить красиво# Переделать доказательства с учётом возможного равенства рёбер# Отформатировать псевдокод# Пример как-то кривовато описан (особенно это разделение на компоненты связности)# Заменить дефис на шаблон# Источники информации правильно оформить# Категория

<li> '''!!!''' [[Алгоритм двух китайцев]] (67) </li>

<li> ''взяли'' [[Связь матрицы Кирхгофа и матрицы инцидентности]] (0.5)</li># Англоязычные термины# Константы взять в Tex# См. также и источники информации# Категория<li> ''взяли'' [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] (0.5)</li># Добавить ссылку на формулу Бине-Коши (примечание на википедию или интервики на конспект линала)# Источники и см. также# Исправить знаки неравенств# Заменить тире на шаблон# Категория<li> ''взяли'' [[Количество помеченных деревьев]] (0.5)</li># Англоязычные термины# Первый пункт не нужен# Категория# Оформить доказательство красиво# См. также и источники информации# = в Tex<li> ''взяли'' [[Коды Прюфера]] (0.5)</li># Не оформлять описание алгоритма как псевдокод# Англоязычные термины# Категория# См. также и Источники информации

<li> '''!!!'взяли'' [[Покрытие ребер графа путями]] (53)</li># Так и не надо определение почти связного графа {{---}} надо внести в предыдущий конспект, а здесь сделать интервики# Знак "не принадлежит" оформить в Tex# ЧтоКакое-то доказательство какое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей# То же самое в достаточности# Оформить правильно источники информации# Категориямутное доказательства<li> [[Алгоритм построения Эйлерова цикла]] (32) </li># Отформатировать псевдокод# Довести до ума. Начиная с представления уже тяжко. До этого момента надо подытожить текущие доказательство, а то там много разных фактов и надо их какКакое-то в одну пачку собрать, сказав, чего хочется достичь дальше.# Категориямутное доказательство леммы про корректность алгоритма<li> '''!!!''' [[Произвольно вычерчиваемые из заданной вершины графы]] (6) </li># Англоязычные термины оформить правильно# Что значит неодноэелементный?# Стрелки слишком длинные# На картинке ошибка {{---}} почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень# Источники информации правильно оформить# Хотелось бы больше пояснений в доказательстве# В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить, используя в основе какой-то лес# Категория

<li value="5"> '''взяли''' [[Гамильтоновы графы]] (6.5) </li># Заменить дефисы на тире# Исправить знаки неравенств# Отформатировать псевдокод# Помёрджить с конспектом динамического программирования и пофиксить ошибки в обоих, если есть (должны остаться алгоритмы поиска пути/цикла, пути, минимизирующего какой-то критерий)# Источники информации# Категория<li> ''взяли'' [[Теорема Хватала]] (0.5) </li># Исправить знаки неравенств# Поставить \mid в множествах# Лишние кавычки в доказательствах вокруг стрелок# Убрать q.e.d# Оформить правильно источники информации# Категория<li>[[Теорема Поша]]</li>

<li> '''взяли''' [[Теорема Поша]]</li><li> [[Теорема Гуйя-Ури]] </li><li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] (5) </li># Странные обозначения для графа и множеств вершин и рёбер# Убрать умножение звёздочкой# Заменить дефис на тире# Отформатировать псевдокод# Источники информации# Исправить знаки неравенств# Категория

# Англоязычные термины оформить правильно# Дефис заменить на тире# Картинки криво расположеныПояснить переходы в теореме# Ссылки поехали Внести пояснение в примере# Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачнейопределение бонда# Почему необходимое условие? А И зачем нужно доказывать отсутствие гамильтонова бонда в обратную сторонуграфе?# Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 грань# КатегорияКартинку сделать красивой<li> '''взяли''' [[Турниры]] (56) </li># Англоязычные термины# Добавить оценку на число турниров в графе Доказательства всех утверждений из n вершин# Убрать лишние определения# Оформить правильно источники информации# Немного неправильно сформулировано утверждение про полустепени вершин# Категорияконспекта (эквивалентность утверждений и конденсация)<li> ''взяли'' [[Теорема Редеи-Камиона]] (0.5) </li># Исправить знаки неравенств# Правильно оформить источники информации# Категория

# ''взяли'' [[Укладка графа на плоскости]] (0.5)## Англоязычные термины правильно оформить## Добавить пару ссылок на конспекты вычгеома о том, чем хороши планарные графы## Источники информации# ''fixed'' [[Формула Эйлера]] (0.5)## Исправить знаки неравенств## Заменить литературу на источники информации## Добавить ссылок# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)

# ''взяли'' [[Укладка дерева]] (1)## Заменить sup и inf на \sup и \inf## Заменить дефисы на тире## Картинки адекватно расположить## Англоязычные термины правильно оформить## Зачем в начале замечание про грань?## Увеличить дроби# ''взяли'' [[Укладка графа с планарными компонентами реберной двусвязности]] (0.5)## Заменить источники на источники информации## Взять все переменные в Tex## Добавить См. также## Интервики на мост# ''взяли'' [[Укладка графа с планарными компонентами вершинной двусвязности]] (0.5)## Исправить знаки неравенств## Заменить источники на источники информации## deg заменить на \deg

# [[Род, толщина, крупность, число скрещиваний]]# [[Двойственный граф планарного графа]] (1)## Добавить пробел после "двойственным" в определении## Интервики## Убрать neat из определения самодвойственного графа## Увеличить дроби## Добавить источники информации## Интервики на мост, планарные графы## Добавить См. также

# '''!!!''' [[Раскраска графа]] (6)## Правильно оформить англоязычные термины## Заменить \phi на \varphi## Пункт "Хроматическое число" не нужен## Заменить дефисы на тире## Пояснить, что такое нулевой граф## Список хроматических чисел нормально оформить## Четвёртый пример заменить на двудольные графы (дерево, в частности, является таким)## Оформить правильно источники информации## Примечания перенести выше## Кинуть интервики на неразрешимость задачи о раскраске графа## Написать о связи хроматического числа и хроматического многочлена, и почему нельзя найти хроматическое число, если у нас есть такая замечательная штука, как хроматический многочлен?# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)

# '''!!!''' [[Формула Зыкова]] (6)## Определения выделить жирным## Англоязычные термины правильно оформить## Написать более подробное, понятное и корректное доказательство## Исправить знаки неравенств## Правильно оформить источники информации## Добавить см. также# '''!!!''' [[Формула Уитни]] (6)## Заменить дефисы на тире## Исправить знаки неравенств## Заменить \phi на \varphi## Правильно оформить источники информации## А что такое собственные и несобственный раскраски?## Пояснить непонятные места в доказательстве вцелом## Добавить см. также# [[Теорема Брукса]] (0.5)## Заменить дефисы на тире## Интервики## "на iом шаге" {{---}} пропущен дефис## Исправить знаки неравенств## Оформить правильно источники информации## Добавить см. также# [[Верхние и нижние оценки хроматического числа]] (1)## Заменить дефисы на тире## Исправить знаки неравенств## Интервики## Англоязычные термины## Заменить max на \max## Все переменные взять в Tex## Увеличить дроби## Оформить правильно источники информации и см. также# [[Хроматическое число планарного графа]] (3)## Все константы взять в Tex## Доказательство по индукции красиво оформить## Заменить дефисы на тире## Исправить знаки неравенств## Теорема о 5-раскраске планарного графа именная {{---}} Хивуд {{---}} дать ей название## Оформить правильно источники информации## Заменить многоточия на \ldots## Разместить картинки друг под другом# [[Многочлен Татта]] (0.5)## Англоязычные термины## Заменить дефисы на тире## " Уитни (Whiney rank polynomial)." {{---}} кажется, пропущено t## "Показатели в формуле раногового" {{---}} зачем это в определение вносить?## Интервики## Оформить правильно источники информации# [[Теория Рамсея]] ('''??10''')

# '''взялиfixed''' [[Обход в глубину, цвета вершин]] (5)

# '''fixed''' [[Использование обхода в глубину для проверки связности]] (5)## Отформатировать псевдокод## Задачу в шаблон## Добавить примеров задач, например, как по двум вершинам определять, являются ли они связанными в режиме online при добавлении рёбер## Добавить источники информации, см. также## Tex внутри конспекта сделать красивым

# [[Использование обхода в глубину для поиска компонент сильной связности]] (3)## Некрасивый список в доказательстве теоремы## Отформатировать псевдокод## Добавить ссылок# '''!!!'fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (64)## Убрать отступ в теоремеЧто-то картинки неудачно расположены## Кривая структура у доказательства

## Добавить примеры того, когда и почему становится плохо, если функция up будет определена по-другому# [[Построение компонент вершинной двусвязности]] (3)## Отформатировать псевдокод## Красиво оформить источники# [[Использование обхода в глубину для поиска мостов]] (3)## Заменить min на \min## Отформатировать псевдокод## Некрасиво оформлено утверждение маркированным списком, да и у тело утверждения тоже некрасивое## Нормаоьно оформить источники информации, добавить см. также# [[Построение компонент реберной двусвязности]] (3)## Отформатировать псевдокод## Визуализатор внести в источники информации

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

# [[Эвристики для поиска кратчайших путей]] (2)## "Дано" криво оформлено## Заменить дефисы на тире## Оформить правильно источники информации и англоязычные термины## Оформить правильно списки, заглавные буквы корректно расставить## Ссылку на основную статью оформить правильно## Таблички сделать красивыми

# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] (2-3)## Добавить картинок паросочетаний различных красивых (две-три хватит)# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] (2)## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое## Интервики## Отформатировать псевдокод## Картинки заползают на заголовки, придумать что-нибудь с этим## == в тексте заменить на =## Оформить правильно источники информации

# [[Теорема Холла]] (1.5)## добавить ссылку на английскую википедию## Англоязычные термины## Дефисы на тире## Оформить доказательство правильно и красиво## Исправить знаки неравенств## Константы в Tex## Примечания маленькие## Добавить больше ссылок, заменить на источники информации# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] (1)## Оформить правильно источники информации## Убрать neat в определении## Убрать <br> ## Англоязычные термины оформить правильно## Пункт Определения не нужен## Оформить красиво списки

## См. предыдущее# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] (2)## Англоязычные термины оформить правильно## Дублируется определение совершенного паросочетания## Пояснить про независимые переменные## И что за детерминант от элемента матрицы, а не самой матрицы?## - -> {{---}}## Источники информации# [[Теорема Татта о существовании полного паросочетания]] (0.5)## Оформить правильно англоязычные термины## Оформить правильно и красиво доказательства## Убрать граф из mathbb## Сделать ссылку примечанием## Источники информации

# '''!!!''' [[Декомпозиция Эдмондса-Галлаи]] (5)## Много пустых строк## Пробелы перед открывающей круглой скобкой## Определение нечётных компонент дублируется с конспектом из теоремы Татта## Переменные в Tex## Дефисы на тире## Добавить доказательства теорем (хотя бы одной (ну или хотя бы ссылки примечаниями))## Убрать заголовки первого уровня# '''!!!взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''

== 10. Задача о максимальном потоке (проверяется) ==# ''fixed'' [[Определение сети, потока]]## Оформить правильно источники информации## Правильно оформить англоязычные термины## Интервики## Исправить знаки неравенств## Дефисы на тире# '''!!!''' [[Разрез, лемма о потоке через разрез]]## Оформить правильно англоязычные термины## Списки кривые## Определения выделить жирным## Дефисы превратить в тире## Убрать ; из леммы, сделать маркированный список## Исправить знаки неравенств## Скобки в тексте кое-где лишние## Источники информации ## Нарисовать красивую картинку вместо текущей# '''fixed''' [[Дополняющая сеть, дополняющий путь]]## Англоязычные термины правильно оформить## Оформить правильно источники информации## Нарисовать пример# ''fixed'' [[Лемма о сложении потоков]]## Дефисы на тире## Знаки неравенств## Убрать "Аналогичная"

## гм, и зачем "дельта" русским словом в псевдокоде?## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока и отрефакторить псевдокод## Константы взять в Tex## Источники информации## Знаки неравенств# '''!!!взяли''' [[Алоритм Эдмондса-Карпа]](5)## а описание алгоритма где?## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?## ссылки на русскую/английскую википедию## Отформатировать псевдокод## while в тексте обернуть в \mathrm## Знаки неравенств## Добавить Полностью описать пример про грибок с картинками в конспектконспекте

## ссылки на русскую/английскую википедию## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.## Отформатировать псевдокод# ''взяли'' [[Блокирующий поток]](1)

# '''взяли''' # Расположить красиво картинки, чтобы не наезжали# [[Схема алгоритма Диница]]## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте## "makeGl" назвать как-нибудь нормально## "algorithmDinica" тоже назвать нормально## Интервики## Написать более подробный псевдокод# '''!!!fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]](6)

## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоличто ли?

## Дефисы на тире, знаки ## Знаки неравенств, источники ## Источники информации# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]## "Жадный Алгоритм" — зачем с большой буквы алгоритм?## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то плохой, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении# '''!!!''' [[Метод проталкивания предпотока]](7)## зачем какие-то кванторы в for?Картиночки с резервуарами!## initialaze -> initializeИсточники информации## названия функций в тексте оборачиваются в \mathrm или \mathttДобавить см. также## Англоязычные терминыДефисы заменить на тире

## кванторы в псевдокоде не нужну, написать просто not exists, и вообще отформатировать псевдокод## Дефисы на тире## Переписать формулировку теоремы## Отформатировать псевдокод## Оформить правильно источники информации# ''fixed'' [[Теорема о декомпозиционном барьере]](3)

# '''!!!''' [[Поток минимальной стоимости]] (5)## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)## Убрать "Определение задачи", из-под определения вынести формулировку в шаблон задача## Оформить правильно источники информации (и вообще всё оформить правильно)## Добавить определений стоимости, свойства стоимости на обратных рёбрах, картинки нарисовать# '''!!!''' [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] (0.5, вместе с алгоритмом)## Исправить знаки неравенств## Источники информации# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)

# '''!!!''' [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] (4.5, вместе с теоремой)## Помёрджить с теоремой Ф-Ф## Отформатировать псевдокод

# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)

# '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]] (5)## написать более подробный псевдокод## Интервики## Источники информации