== 1. Основные определения теории графов ==
# '''взяли''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]## moar англоязычных терминов## "Мультиграф с петлями принято называть псевдографом. " — при этом понятие мультиграфа встречается позже. Нехорошо, разобраться все же с правильными порядком и правильными определениями## Из определения орграфа с beg и end никак не следует, что там не может быть петель (кто мешает сделать beg e = v, end e = v?).## "некоторые абстрактные множества." — а что такое неабстрактные множества?## "V — конечное множество вершин" — при этом далее в каком-то конспекте есть пример для бесконечного графа. Не надо заставлять граф быть конечным, лучше написать отдельно, что называется конечным графом.## запись "<tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex>" я вообще не очень понимаю. Если вы понимаете, объясните мне, иначе напишите нормально :)## альтернативное определение неориентированного графа мне не нравится, потому что прямо перед ним мы говорим, что ребро — неупорядоченная пара, а потом внезапно <tex>ends : E \rightarrow V \times V</tex>, а декартово произведение у нас еще как упорядочено.
# [[Лемма о рукопожатиях]]
# [[Теорема о существовании простого пути в случае существования пути]]
## перенести определения в "Основные определения"
## форматирование в некоторых местах какое-то упоротое, думаю, это видно.
# [[Теорема о существовании простого цикла в случае существования цикла]]
## добавить интервики
## форматирование в некоторых местах какое-то упоротое
# [[Матрица смежности графа]]
## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два.
# [[Связь степени матрицы смежности и количества путей]]
# [[Матрица инцидентности графа]]
## Определение инцидентности вроде есть в "Основных определениях", если нет — перенести его туда
# [[Циклическое пространство графа]]
## Пункт "Определение" не нужен, см. правила форматирования
## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
## интервики
## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
# [[Фундаментальные циклы графа]]
## определения "каркаса", кажется, до этого не было, а вообще это вроде то же самое, что "остов", который используется во всем остальном курсе, так что если это так, заменить.
## Раздел "Определение" не нужен.
# [[Дерево, эквивалентные определения]]
## Кажется, ранее не было определний <tex>K_n</tex>, если нет, то надо куда-нибудь их добавить и сделать на них ссылку.
# [[Дополнительный, самодополнительный граф]]
## Оформить нормально определение изоморфности графов (видимо, его надо в "Основные опредения"), и добавить на него ссылку
## англоязычные термины
== 2. Связность в графах ==
# [[Отношение связности, компоненты связности]]
## англоязычные термины
## интервики
# [[Отношение реберной двусвязности]]
## англоязычные термины
# [[Отношение вершинной двусвязности]]
## англоязычные термины
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
## Капс какой-то зачем-то
# [[Точка сочленения, эквивалентные определения]]
## Цифры в начале определений не нужны, их можно в хедер определения
# [[Мост, эквивалентные определения]]
## англоязычные термины
## Цифры в начале определений не нужны, их можно в хедер определения
# [[k-связность]]
## англоязычные термины
# [[Теорема Менгера]]
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
## пункт "Определения" не нужен
== 3. Остовные деревья ==
* # [[Матрица Кирхгофа]]* ## Пункт "Определение" не нужен, вынести в начало статьи## "простого графа" — а простой — это какой? Кинуть ссылку на определение простого графа.## 0, else — так не говорят, говорят "0, otherwise"# [[Связь матрицы Кирхгофа и матрицы инцидентности]]* # [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]* # [[Количество помеченных деревьев]]* ## англоязычные термины# [[Коды Прюфера]]
== 4. Обходы графов ==
* # '''fixed''' [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]* ## англоязычные термины## не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести## "См. Также" — зачем "также" с большой буквы?# [[Покрытие ребер графа путями]]* # [[Алгоритм построения Эйлерова цикла]]* # [[Произвольно вычерчиваемые из заданной вершины графы]]* # '''fixed''' [[Гамильтоновы графы]]* ## англоязычные термины# [[Теорема Хватала]]* # [[Теорема Дирака]]* # [[Теорема Оре]]* # [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]* # [[Турниры]]* # [[Теорема Редеи-Камиона]]
== 5. Укладки графов ==
* # ''fixed'' [[Укладка графа на плоскости]]* ## англоязычные термины## думаю, здесь же можно написать, что в 3D любой граф укладывается# [[Формула Эйлера]]* # ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]* ## Дать ссылку на определения K5 и K3,3# [[Укладка дерева]]* # [[Укладка графа с планарными компонентами реберной двусвязности]]* # [[Укладка графа с планарными компонентами вершинной двусвязности]]* # ''fixed'' [[Теорема Понтрягина-Куратовского]]* ## Определение гомеоморфизма есть в "Укладка графа на плоскости", на него и сослаться.## Формулировку теоермы надо вынести в заголовок, например.# ''fixed'' [[Двойственный граф планарного графа]]## англоязычные термины
== 6. Раскраски графов ==
* Во всем разделе — надо англоязычные термины (их по 1-2 в каждом конспекте)# ''fixed'' [[Раскраска графа]]* ## пункт "Раскраска графа" не нужен, перенести в заголовок## англоязычные термины## "Хроматическим многочлен"## надо бы написать, почему нам вообще интересно раскрашивать графы# [[Двудольные графы и раскраска в 2 цвета]]* [[Хроматический многочлен]]** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]* [[Формула Зыкова]]* # [[Формула Уитни]]* # [[Теорема Брукса]]* # [[Верхние и нижние оценки хроматического числа]]
== 7. Обход в глубину ==
* # [[Обход в глубину, цвета вершин]]* # [[Лемма о белых путях]]* # [[Использование обхода в глубину для проверки связности]]* # [[Использование обхода в глубину для поиска цикла в ориентированном графе]]* # [[Использование обхода в глубину для топологической сортировки]]* # [[Использование обхода в глубину для поиска компонент сильной связности]]* # [[Использование обхода в глубину для поиска точек сочленения]]* # [[Построение компонент вершинной двусвязности]]* # [[Использование обхода в глубину для поиска мостов]]* # [[Построение компонент реберной двусвязности]]
== 8. Кратчайшие пути в графах ==
* # [[Обход в ширину]]* # [[Алгоритм Форда-Беллмана]]* # [[Алгоритм Дейкстры]]* # [[Алгоритм Левита]] '''(в процессе редактирования)'''# [[Алгоритм Флойда]]* # '''!!!''' [[Алгоритм A*]]* ## что-то со второй картиночкой, там гифка, а почему-то не отображается## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.## какая-то тут муть написана, что в корректности, что в оптимальности## а еще можно написать про случай с монотонной эвристикой# [[Алгоритм Джонсона]]
== 9. Построение остовных деревьев ==
* # [[Лемма о безопасном ребре]]* # [[Алгоритм Прима]]* # [[Алгоритм Краскала]]* # [[Алгоритм Борувки]]* # [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]* # [[Алгоритм двух китайцев]]
== 10. Задача о паросочетании ==
* # [[Теорема о максимальном паросочетании и дополняющих цепях]]* ## англоязычные термины# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]* ## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы## код -- копипаста с емакса## источники перечислять с помощью * , а не :# [[Теорема Холла]]* ## добавить ссылку на английскую википедию# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]## перечислять ссылки через * # [[Связь вершинного покрытия и независимого множества]]## источники перечислять с помощью * , 1. 2.# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]* # '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример
== 11. Задача о максимальном потоке ==
* # ''fixed'' [[Определение сети, потока]]* ## ссылки на русскую и английскую википедию# ''fixed'' [[Разрез, лемма о потоке через разрез]]* ## англоязычные термины## добавить определение минимального разреза## ссылки на русскую и английскую википедию# ''fixed'' [[Дополняющая сеть, дополняющий путь]]* ## Дополняющую сеть также называют остаточной, указать это## ссылки на русскую и английскую википедию# ''fixed'' [[Лемма о сложении потоков]]* ## добавить внутренних ссылок# [[Теорема Форда-Фалкерсона]]* # [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]* ## гм, и зачем "дельта" русским словом в псевдокоде?## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.# [[Алоритм Эдмондса-Карпа]]* ## а описание алгоритма где?## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?## ссылки на русскую/английскую википедию# [[Алгоритм масштабирования потока]]* ## ссылки на русскую/английскую википедию## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.# [[Блокирующий поток]]* ## англоязычные термины## ссылки на русскую и английскую википедию# [[Схема алгоритма Диница]]* ## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте## "makeGl" назвать как-нибудь нормально## "algorithmDinica" тоже назвать нормально# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]* ## может, назвать остаточную сеть $G_f$, как в предыдущих конспектах?## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?## В лемме в утверждении фигурирует поток $f$, но дальше про него ничего нет. Зачем он?## "Мы можем применить Лемму(2" — лемму 3, наверное?# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]* ## "Жадный Алгоритм" — зачем с большой буквы алгоритм?## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении# [[Метод проталкивания предпотока]]* ## зачем какие-то кванторы в for?## initialaze -> initialize## названия функций в тексте оборачиваются в \mathrm# [[Алгоритм "поднять-в-начало"]]* ## названия функций в тексте оборачиваются в \mathrm## relable -> relabel# [[Теорема о декомпозиции]]* ## кванторы в псевдокоде не нужну, написать просто not exists# [[Теорема о декомпозиционном барьере]]* # [[Циркуляция потока]]* ## англоязычные термины## ссылки на русскую и английскую википедию## раздел постановка задачи не нужен, перенести в заголовок## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами# [[Алгоритм Каргера для нахождения минимального разреза]]## внутреннюю ссылку на мультиграф## названия функций в тексте оборачиваются в \mathrm
== 12. Задача о потоке минимальной стоимости ==
* # [[Поток минимальной стоимости]]* ## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]* # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]* # [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]* # [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]* # [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]* # '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]]## написать более подробный псевдокод
