Изменения

# '''fixed''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]## Правильно оформить англоязычные термины## "Иногда граф, построенный таким образом, называют псевдографом (pseudograph)" {{---}} кривовато написано, надо переписать## Дублируется определение смежных вершин## Добавить ссылок в источники информации## Добавить определение полного графа## Несправедливо забыли дерево в часто используемых графах; добавить другие виды графов

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

# '''взяли''' [[Теорема о существовании простого цикла в случае существования цикла]]## На самом деле, конструктивное доказательство тут не очень понятное и не совсем корректное. Сделать неконструктивное и добавить нормальные картинки## Добавить в первую теорему, что граф неориентированный## Добавить источники информации

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

# '''взяли''' [[Циклическое пространство графа]]## Пункт "Определение" не нужен, см. правила форматированияАнглоязычные термины## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)Оформить правильно источники информации## интервики## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературеДобавить См.## Заменить тире также на шаблонматрицу смежности## Добавить ссылок про списки смежности и их оформить тоже в источники информациитаблички## Неплохо бы написать, зачем это нужно (позволяет какие-нибудь теоремы про графы доказать или что-то ещё)[[Циклическое пространство графа]]# ''fixed'' [[Фундаментальные циклы графа]](1)

# # Подписать получше картинку## Заменить многоточия на \ldots## Отформатировать по правилам# ''fixed'' [[Дерево, эквивалентные определения]](1)## Англоязычные термины## Пофиксить знаки неравенств

# '''!!!''' # Оформить красиво доказательства# [[Диаметр дерева]]## Переименовать в Алгоритмы на деревьях]]## Добавить другие алгоритмы (если будет много содержательных, то можно будет поставить <tex> 10 </tex> баллов за конспект)## Отформатировать псевдокод## Добавить категории, ссылки, см. также## Интервики## Исправить tex# ''fixed'' [[Дополнительный, самодополнительный граф]](1)

## англоязычные термины[[Точка сочленения, эквивалентные определения]]## Добавить ссылок[[Мост, эквивалентные определения]]

## англоязычные термины## Тире заменить на шаблон## Палку вертикальную в множестве заменить на \mid## Странное обозначение {{---}} \smallsetminus# ''fixed'' [[Теорема Менгера]](0.5)

## Заменить тире на шаблон## Обращение к леммам сделать через интервики# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]](1.5)

# '''!!!''' === Построение остовных деревьев ===<ol><li value="1">[[Лемма Остовные деревья: определения, лемма о безопасном ребре]]</li>## Англоязычные термины оформить правильно## Внести G' в определение## Переименовать конспект## Добавить пару слов о поиске остовного дерева в незвешенном графе со ссылкой на Краскала## Оформить правильно источники информации## Исправить знаки неравенств в Tex# '''fixed''' <li>[[Алгоритм Прима]]</li>## Англоязычные термины правильно оформить## Добавить интервики## Отформатировать псевдокод## Заменить inf в табличках примера на "бесконечность"## Добавить отступов описанию примера## Источники информации правильно оформить# '''взяли''' <li> [[Алгоритм Краскала]]</li>## Англоязычные термины правильно оформить## Добавить интервики## Заменить дефис на Шаблон:Тире## Реализацию оформить псевдокодом## Добавить отступы в описание примера## Оформить источники информации правильно## Добавить пару слов о поиске остовного дерева в незвешенном графе# '''взяли''' <li> [[Алгоритм Борувки]]</li>## Англоязычные термины правильно оформить## Описание алгоритма оформить красиво и чуточку понятней## Доказательство теоремы оформить красиво## Отформатировать псевдокод## Пример как-то кривовато описан## Заменить дефис на шаблон## Источники информации правильно оформить## Доказательство асимптотики добавить# <li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]](5) </li>## Доказательство красиво оформить## Заменить дефис на шаблон## Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт## Почему ребро uv {{---}} единственное ребро, пересекающее разрез?# Источники информации# Знаки неравенств# Категория<li> '''!!!''' [[Алгоритм двух китайцев]](7) </li>## Англоязычные термины оформить правильно## Добавить определение покрывающего дерева## Описать реализацию красиво## Дефис заменить на тире## Отформатировать псевдокод## Доказать, почему не более V конденсаций## Источники информации оформить правильно## Доказать второе замечание## Добавить отступы в описании примера## 5ый пункт в описании алгоритма расписать чуть понятней# '''!!!''' Категория</ol> === Свойства остовных деревьев ===<ol><li value="7">[[Матрица Кирхгофа]]</li>## Ссылка на простой граф плохо сделана. Добавить определение в самый первый конспект и сделать на него ссылку## Источники информации и см. также нормально оформить## Константы взять в Tex## Оформить свойства прилично## Добавить ещё свойств по возможности# <li> [[Связь матрицы Кирхгофа и матрицы инцидентности]]</li>## Константы взять в Tex## См. также и источники информации# <li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]</li>## Добавить ссылку на формулу Бине-Коши (примечание на википедию или интервики на конспект линала)## Источники и см. также## Исправить знаки неравенств## Заменить тире на шаблон# <li> [[Количество помеченных деревьев]]</li>## англоязычные термины# <li> [[Коды Прюфера]]</li>## Не оформлять описание алгоритма как псевдокод</ol>

# === Эйлеровы графы ===<ol><li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>## Изменить название конспекта на "Эйлеровость графов"## Оформить следствие красиво## Правильно оформить источники информации# '<li> ''!!!'взяли'' [[Покрытие ребер графа путями]](3)</li>## Так и не надо определение почти связного графа {{---}} надо внести в предыдущий конспект, а здесь сделать интервики## Знак "не принадлежит" оформить в Tex## ЧтоКакое-то доказательство какое-то неочевидное. Надо пояснить, почему Эйлеров цикл распадётся на N путей## То же самое в достаточностимутное доказательства## Оформить правильно источники информации# '''!!!''' <li> [[Алгоритм построения Эйлерова цикла]]## Отформатировать псевдокод## Добавить в него проверку на Эйлеровость## Можно сказать, как удалять рёбра за O(12), чтобы не вводить читателей в заблуждение</li>## Источники информации## Хотелось бы более подробное объяснение фактов в доказательстве, а не Какое-то что "заметим", "обратим внимание"мутное доказательство леммы про корректность алгоритма# '''!!!''' <li> [[Произвольно вычерчиваемые из заданной вершины графы]]</li>## Англоязычные термины оформить правильно</ol>## Что значит неодноэелементный?## Стрелки слишком длинные=== Гамильтоновы графы ===## На картинке ошибка {{---}} почему-то не соединена средняя вершина в дереве, хотя она имеет нечётную степень<ol>## Источники информации правильно оформить## Хотелось бы больше пояснений в доказательстве## В строении не очевидно, что каждый произвольно вычерчиваемый граф можно построить,используя в основе какой-то лес# '''!!!''' <li value="5"> [[Гамильтоновы графы]]</li>## Заменить дефисы на тире## Исправить знаки неравенств## Отформатировать псевдокод## Помёрджить с конспектом динамического программирования# <li> [[Теорема Хватала]]</li>## Исправить знаки неравенств## Поставить \mid в множествах## Лишние кавычки в доказательствах вокруг стрелок## Убрать q.e.d## Оформить правильно источники информации# ''fixed'' <li> [[Теорема Дирака]]</li>## Заменить дефис на тире## Исправить знаки неравенств## max правильно написать## Лучше путь P обозначить через \dots## Источники информации правильно оформить## Интервики## Добавить вывод из теоремы <li> [[Теорема Оре]] </li># <li> [[Теорема ОреПоша]]</li>## Исправить знаки неравенств## Интервики## Всё в Tex оформить<li> [[Теорема Гуйя-Ури]] </li>## Источники информации правильно оформить# '''!!!''' <li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]</li>## Странные обозначения для графа и множеств вершин и рёбер## Убрать умножение звёздочкой## Заменить дефис на тире## Отформатировать псевдокод## Добавить алгоритм поиска цикла (пути) в условиях этих теорем по отдельности## Источники информации## Исправить знаки неравенств# <li> '''!!!''' [[Теорема Гринберга]](5) </li>## Англоязычные термины оформить правильно## Дефис заменить на тиреПояснить переходы в теореме## Картинки криво расположены## Ссылки поехали Внести пояснение в примереопределение бонда## Добавить подзаголовок "Пример" или "Использование теоремы", а лучше что-то поудачней## Почему необходимое условие? А И зачем нужно доказывать отсутствие гамильтонова бонда в обратную сторонуграфе?## Пояснить, что такое R и R'. Иначе непонятно в теореме, почему область R разбита на e + 1 граньКартинку сделать красивой# <li> '''!!!взяли''' [[Турниры]](6) </li>## Англоязычные термины## Добавить оценку на число турниров в графе Доказательства всех утверждений из n вершинконспекта (эквивалентность утверждений и конденсация)## Убрать лишние определения## Оформить правильно источники информации## Немного неправильно сформулировано утверждение про полустепени вершин# <li> [[Теорема Редеи-Камиона]]</li>## Исправить знаки неравенств## Правильно оформить источники информации</ol>

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

## Исправить знаки неравенств## Заменить источники на источники информации# '''!!!''' [[Теорема Понтрягина-Куратовского]] (''можно получить 10 баллов за все правки''## Перерисовать картинки пиксельные убогие## Термины в определениях выделить жирным## Англоязычные термины## Вынести нумерацию в леммах в заголовок## Заменить дефисы на тире## Точка после многоточия некрасиво выглядит## Разбор случаев a[[Род, bтолщина, cкрупность, d, u1, u2, v1, v2 криво отформатирован## Картинки в разборе лучше увеличить## Добавить ссылок в источники информации## Добавить немного общей информации в начало конспектачисло скрещиваний]]

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

## Оформить правильно источники информациии См. также

# '''!!!''' [[Хроматический многочлен]]## Англоязычные термины## Пустой граф обозвать удачней, а примечание выделить жирным## Теорему о хроматическом многочлене красиво оформить## Обозначение стягивания ребра перенести перед теоремой о цветах дерева, а лучше дерево вообще ближе к концу перенести## Заменить дефисы на тире## Интервики## Убрать запятые и точки после многоточий в теореме о коэффициентах## Добавить формулы хроматических многочленов цикла и колеса## Оформить правильно источники информации# '''!!!''' [[Формула Зыкова]]## Определения выделить жирным## Англоязычные термины правильно оформить## Написать более подробное, понятное и корректное доказательство## Исправить знаки неравенств## Правильно оформить источники информации## Добавить см. также# '''!!!''' [[Формула Уитни]]## Заменить дефисы на тире## Исправить знаки неравенств## Заменить \phi на \varphi## Правильно оформить источники информации## А что такое собственные и несобственный раскраски?## Пояснить непонятные места в доказательстве в целом## Добавить см. также

## Заменить дефисы на тире## " Уитни (Whiney rank polynomial)." {{---}} кажется, пропущено t## "Показатели в формуле раногового" {{---}} зачем это в определение вносить?## Интервики## Оформить правильно источники информации# [[Теория Рамсея]]('''10''')

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

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

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

# '''!!!''' [[Обход в ширину]]## Оформить правильно англоязычные термины## Интервики## Отформатировать псевдокод## Добавить другие примеры использования бфс {{---}} рёбра 0 и 1, рёбра до k## Оформить правильно источники информации

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

== 109. Задача о паросочетании ==# '''!!!''' [[Теорема Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]## Конспект дублируется, убрать его## Сделать общий конспект про паросочетания, определения и свойства, взять информацию из других конспектов

## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое## Интервики## Отформатировать псевдокод## == в тексте заменить на =## Оформить правильно источники информации# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы## код -- копипаста с емакса## источники перечислять с помощью *, а не :## Криво оформлено описание алгоритма## В конспекте по ссылке теоремы Бержа нет этой теоремы :(

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

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

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

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

## гм, и зачем "дельта" русским словом в псевдокоде?## псевдокод сейчас не вполне понятен — какой-то 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)

== 1211. Задача о потоке минимальной стоимости ==# '''!!!''' [[Поток минимальной стоимости]]## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)## Убрать "Определение задачи", из-под определения вынести формулировку в шаблон задача## Оформить правильно источники информации## Добавить определений стоимости, свойства стоимости на обратных рёбрах, картинки нарисовать

## Исправить знаки неравенств## Источники информации# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]](0.5)

# '''!!!''' # Источники информации# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]## Помёрджить с теоремой Ф-Ф## Отформатировать псевдокод# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]## Определение выделить жирным(5)## Написать более подробный псевдокоди оформить так, чтобы не было чуши# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]](0.5)

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