Изменения

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

== 86. Кратчайшие пути в графах ==# [[Обход в ширину]]5## исправить речевые ошибки в описании## поправить тех## 0-1 bfs переписать## нормально сформулировать доказательство 1ого утверждения## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")## добавить "см. также" # [[Алгоритм Форда-Беллмана]]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 не хватает скобок## описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся## добавить "см. также"# [[Эвристики для поиска кратчайших путей]]0.5## поправить тех## вряд ли 16MB памяти в таблице про Европу

== 97. Задача о паросочетании ==# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]

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

== 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