Изменения

== 1. Основные определения теории графов ==# [[Основные определения теории графов|Основные определения: графТикеты индексируются как "X-Y", реброгде X — номер раздела, вершина, степень, петля, путь, цикл]]# [[Лемма о рукопожатиях]]# [[Теорема о существовании простого пути в случае существования пути]] # [[Теорема о существовании простого цикла в случае существования цикла]]# [[Матрица смежности графа]]# [[Матрица инцидентности графа]] Y — номер конспекта внутри раздела (4 ''или больше, зависит от свойств'')## Добавить свойства матрицы инцидентности с доказательствами## Источники -> Источники информации## Добавить про списки смежности и их оформить тоже в таблички# [[Циклическое пространство графа]]# [[Фундаментальные циклы графа]] # [[Деревонапример, эквивалентные определения]] # [[Алгоритмы на деревьях]]# [[Дополнительный, самодополнительный граф]] # [[Теоретико-множественные операции над графами]]# [[Рёберное ядро]] (2)## Добавить больше интервики в конспект## В конце теоремы в доказательстве какая-то лажа## Источники информации## Оформить следствия красиво# [[Факторизация графов]] == 2. Связность Алгоритм A* из раздела Кратчайшие пути в графах ==# [[Отношение связности, компоненты связности]]# [[Отношение реберной двусвязности]]# [[Отношение вершинной двусвязности]]# [[Точка сочленения, эквивалентные определения]]# [[Мост, эквивалентные определения]]# [[Граф компонент реберной двусвязности]]# [[Граф блоковимеет тикет 5-точек сочленения]]# [[k-связность]]# [[Теорема Менгера]] # [[Теорема Менгера, альтернативное доказательство]]# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.57)## пункт "Определения" не нужен## Изменить знаки неравенств в tex## Не надо дублировать определения из другого конспекта## Отформатировать псевдокод## find_flow какой-то стрёмный## Источники информации## k-связность с маленькой буквы## Добавить См. также на что-нибудь разумное## Добавить см. также

== 31. Остовные деревья ==

<li> [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li># Доказательство красиво оформить# Заменить дефис на шаблон# Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт# Почему ребро uv {{---}} единственное ребро, пересекающее разрез?# Источники информации# Знаки неравенств# Категория

=== Свойства остовных деревьев =2 Связность в графах ==<ol># [[Отношение связности, компоненты связности]]# [[Отношение реберной двусвязности]]# [[Отношение вершинной двусвязности]]# [[Точка сочленения, эквивалентные определения]] 4<li value="## разобраться с доказательством теоремы из 7">пунктов# [[Мост, эквивалентные определения]]# [[Граф компонент реберной двусвязности]]# [[Граф блоков-точек сочленения]]# [[Матрица Кирхгофаk-связность]]</li><li> # [[Связь матрицы Кирхгофа и матрицы инцидентностиТеорема Менгера]] </li><li> # [[Подсчет числа остовных деревьев с помощью матрицы КирхгофаТеорема Менгера, альтернативное доказательство]] </li><li> # [[Количество помеченных деревьевВершинная, реберная связность, связь между ними и минимальной степенью вершины]] </li><li> # [[Коды ПрюфераЗадача о динамической связности оффлайн]] </litex>^\star</oltex># [[Задача о динамической связности]] == Обходы графов ===== 3 Эйлеровы графы ===

== 4. Обходы графов ===== Эйлеровы графы ===<ol><li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li><li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li># Какое-то мутное доказательства<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>## Какое-то мутное доказательство леммы про корректность алгоритма<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li></ol>

=== Гамильтоновы 4 Гамильтовы графы ===<ol><li value="52"> [[Гамильтоновы графы]] </li><li> [[Теорема Хватала]] </li><li> [[Теорема Дирака]] </li><li> [[Теорема Оре]] </li><li> [[Теорема Поша]]</li><li> [[Теорема Гуйя-Ури]] </li>

== 5. Укладки графов Обход в глубину ==# [[Укладка графа на плоскостиОбход в глубину, цвета вершин]]1## поправить тех (цифры и аргументы функций)## разделить функции в псевдокоде## убрать из названия конспекта "цвета вершин"## Заменить "NILL" на что-то более подходящее# [[Формула ЭйлераЛемма о белых путях]]1# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] # поправить тех (0.5названия функций)## Исправить знаки неравенствдобавить "см. также"## Источники информации"...есть как белые, так и черные, и серые вершины" - бред## Константы в Texисточники информации# [[Укладка дереваИспользование обхода в глубину для проверки связности]]2## СНМ не к месту## источники информации# [[Укладка графа с планарными компонентами реберной двусвязностиИспользование обхода в глубину для поиска цикла]] 3## добавить реализацию для неориентированного графа# [[Укладка графа с планарными компонентами вершинной двусвязностиИспользование обхода в глубину для топологической сортировки]]3## поправить теорему в "постановке задачи"## поправить тех для dfs-ов## поправить тех в псевдокоде## описать в псевдокоде ans, visited## пример отнести к применениям# [[Теорема Понтрягина-КуратовскогоИспользование обхода в глубину для поиска компонент сильной связности]]2## тех для чисел## максимально перевести объяснения в коде на русском в псевдокод## "см. также"# [[Род, толщина, крупность, число скрещиванийИспользование обхода в глубину для поиска точек сочленения]]2## разделить функции в псевдокоде## добавить комментарии к псевдокоду# [[Двойственный граф планарного графаПостроение компонент вершинной двусвязности]]0.5## поправить тех (для "dfs", "paint")# [[Теорема ФариИспользование обхода в глубину для поиска мостов]]1## шаблон "задача"## 2 одинаковых "enter(x)" в описании ret(v)## "enter" и "ret" (как функции) - в \mathrm# [[Гамма-алгоритмПостроение компонент реберной двусвязности]]0.5## поправить тех для "dfs", "paint"

== 6. Раскраски графов Кратчайшие пути в графах ==# [[Раскраска графаОбход в ширину]]5## исправить речевые ошибки в описании## поправить тех## 0-1 bfs переписать## нормально сформулировать доказательство 1ого утверждения## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")## добавить "см. также" # ''fixed'' [[Двудольные графы и раскраска в 2 цветаАлгоритм Форда-Беллмана]] (3)6## поправить тех для чисел## Англоязычные терминыиз s достижимы циклы отрицательного веса <tex>\nRightarrow</tex> не существует кратчайших путей## Убрать определение двудольного графа весь конспект бессвязный - не ясно что к чему и сделать интервики на основной конспекткак относится. Нормально структурировать## Картинку двудольного графа перенести ниже, а то плохо смотритсясделать доказательство первой леммы более содержательным## Интервикипункт "Псевдокод" - бред почти полностью## Добавитьиногда w(x, y), что можно ещё за проход иногда w(xy) - исправить; обычно написано в ширину проверитьневерном порядке## Оформить правильно источники информации и См. такжесистематизировать комментарии в псевдокоде (добавить, сделать содержательными)## Перенести добавить "см. также до источников информации, а ссылку заменить на интервики"# [[Хроматический многочленАлгоритм Дейкстры]]0.5## в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи ## добавить "см. также"# [[Формула ЗыковаАлгоритм Флойда]]1.5# # поправить нерабочий тех## переписать, чтобы индексация d была везде через "[[Формула Уитни]]"## комментарии в псевдокоде несодержательны# [[Теорема БруксаАлгоритм Джонсона]]0.5## поправить псевдокод# [[Верхние и нижние оценки хроматического числаАлгоритм Левита]]3## избавиться от тернарного оператора## поправить тех min## формализовать (хотя бы частично) доказательство лемм (возможно, добавить еще)## про реализацию через дек внести ясность## утверждение о сложности обернуть в соответствующих шаблон# [[Хроматическое число планарного графаАлгоритм A*]]5## теорема доказана не полностью# [[Многочлен ТаттаАлгоритм D*]]4## ссылки на доказательства заменить на доказательства## использование g(s) до ее определения## описание g(s) очень мутное## "исходящие" и "входящие" вершины - правильно назвать## в определении rhs не хватает скобок## описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся## добавить "см. также"# [[Теория РамсеяЭвристики для поиска кратчайших путей]] ('''10''')0.5## поправить тех## Тут вообще ад какой-товряд ли 16MB памяти в таблице про Европу

== 7. Обход в глубину ==# [[Обход в глубину, цвета вершин]] # [[Лемма о белых путях]]# [[Использование обхода в глубину для проверки связности]]# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]# [[Использование обхода в глубину для топологической сортировки]]# [[Использование обхода в глубину для поиска компонент сильной связности]]# [[Использование обхода в глубину для поиска точек сочленения]]# [[Построение компонент вершинной двусвязности]]# [[Использование обхода в глубину для поиска мостов]]# [[Построение компонент реберной двусвязности]] == 8. Кратчайшие пути в графах ==# [[Обход в ширину]]# [[Алгоритм Форда-Беллмана]]# [[Алгоритм Дейкстры]]# [[Алгоритм Флойда]]# [[Алгоритм Джонсона]]# [[Алгоритм Левита]]# [[Алгоритм A*]]# [[Алгоритм D*]]# [[Эвристики для поиска кратчайших путей]] == 9. Задача о паросочетании ==# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]

# [[Алгоритм Куна для поиска максимального паросочетания]]0.5# [[Теорема Холла]]# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]# [[Связь вершинного покрытия и независимого множества]]# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]# [[Теорема Татта о существовании полного паросочетания]]поправить тех у "dfs"# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)

== 108. Задача о максимальном потоке ==# [[Определение сети, потока]]0.5## добавить "см. также"# [[Разрез, лемма о потоке через разрез]] 0.5## добавить "см. также"## поправить тех для чисел # [[Дополняющая сеть, дополняющий путь]]0.5## добавить "см. также"# [[Лемма о сложении потоков]]0.5## добавить "см. также"# [[Теорема Форда-Фалкерсона]]0.5## исправить "\text{in}"# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]0.5## нормально расположить картинки# '''взяли''' [[Алоритм Алгоритм Эдмондса-Карпа]] (0.5)## Полностью описать пример про грибок с картинками в конспектеДобавить см также

# ''взяли'' [[Блокирующий поток]] (10,5)## англоязычные термины## ссылки на русскую и английскую википедию

## Расположить красиво картинки, чтобы не наезжалиИнтервики# [[Схема алгоритма Диница]]0.5## добавить "см. также"## поправить тех# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?## "Мы можем применить Лемму(2" — лемму 3, наверное?## Дефисы на тире## Знаки неравенств## Источники информации# [[Алгоритм поиска блокирующего потока в ациклической сети]](10)## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении# '''!!!''' [[Метод проталкивания предпотока]] (7)

# [[Алгоритм "поднять-в-начало"]]2## <tex>O(V^3)</tex> не сравнимо с <tex>O(V^2E)</tex>## поправить тех# [[Теорема о декомпозиции]]0.5## добавить "см. также"## поправить "-" в псевдокоде# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)1## Источники информацииоформить следствие## Пояснить,почему такие константы используются[[Циркуляция потока]] 0.5## Увеличить дробипоправить тех## А что из этой теоремы следует?# [[Циркуляция потока]]добавить "см. также"# [[Алгоритм Каргера для нахождения минимального разреза]]3## поправить сигму в определении веса разреза и определение множества там же## поправить псевдокод (если возможно)## поправить комментарий в псевдокоде ## теорема не утверждает "что вероятность получить правильный ответ ... очень мала". Нормально сформулировать## <tex>e^{count⋅(−\frac{2}{n^2})}=e^{−2ln(n)}</tex> - это как вообще?## <tex>\log</tex> можно использовать без базы только в оценках <tex>O(...)</tex>## заменить "/" на "\frac"## добавить "см. также"

== 119. Задача о потоке минимальной стоимости ==# [[Поток минимальной стоимости]]3## исправить замечания из обсуждения статьи<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]перенаправляется на "Поиск потока мин.стоимости...", который ниже есть --> # ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)## Интервики на декомпозицию## Знаки неравенствдобавить "см. также"## Источники информациипоправить тех сигм# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]0.5## поправить тех "G"# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)

# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.,5)## Взять задачи в шаблонДобавить см также## Оформить покрасивей и правильнейИсточники информации оформить нормально# [[Венгерский алгоритм решения задачи о назначениях]]0.5## поправить тех## сделать wikitable