Участник:Shersh/Тикеты к 3ему терму — различия между версиями
Shersh (обсуждение | вклад) (→в процессе проверки 5. Укладки графов) |
Shersh (обсуждение | вклад) м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 3ему терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))) |
||
| (не показано 228 промежуточных версий этого же участника) | |||
| Строка 2: | Строка 2: | ||
== 1. Основные определения теории графов == | == 1. Основные определения теории графов == | ||
| − | # | + | # [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Лемма о рукопожатиях]] | # [[Лемма о рукопожатиях]] | ||
| − | # | + | # ''fixed'' [[Теорема о существовании простого пути в случае существования пути]] (4) |
| − | |||
| − | |||
| − | |||
| − | |||
## Алгоритм и предположение зря оформлены как псевдокод | ## Алгоритм и предположение зря оформлены как псевдокод | ||
## Добавить ссылок | ## Добавить ссылок | ||
| Строка 21: | Строка 11: | ||
## Плохо, что картинка наплывает на заголовок {{---}} переделать | ## Плохо, что картинка наплывает на заголовок {{---}} переделать | ||
## Добавить в формулировку теоремы, что вершинно-простой путь | ## Добавить в формулировку теоремы, что вершинно-простой путь | ||
| − | # | + | # [[Теорема о существовании простого цикла в случае существования цикла]] |
| − | |||
| − | |||
| − | |||
# [[Матрица смежности графа]] | # [[Матрица смежности графа]] | ||
| − | # | + | # ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'') |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## Добавить свойства матрицы инцидентности с доказательствами | ## Добавить свойства матрицы инцидентности с доказательствами | ||
## Добавить ссылок в источники информации | ## Добавить ссылок в источники информации | ||
| − | + | ## Англоязычные термины | |
| − | ## | + | ## Оформить правильно источники информации |
| − | ## | + | ## Добавить См. также на матрицу смежности |
| − | ## | + | ## Добавить про списки смежности и их оформить тоже в таблички |
| − | + | # [[Циклическое пространство графа]] | |
| − | + | # ''fixed'' [[Фундаментальные циклы графа]] (1) | |
| − | ## Добавить | ||
| − | # | ||
| − | # [[Фундаментальные циклы графа]] | ||
## Источники информации нормально оформить | ## Источники информации нормально оформить | ||
| − | # [[Дерево, эквивалентные определения]] | + | ## Подписать получше картинку |
| + | ## Заменить многоточия на \ldots | ||
| + | ## Отформатировать по правилам | ||
| + | # ''fixed'' [[Дерево, эквивалентные определения]] (1) | ||
| + | ## Англоязычные термины | ||
| + | ## Пофиксить знаки неравенств | ||
## Источники информации нормально оформить | ## Источники информации нормально оформить | ||
| − | # | + | ## Оформить красиво доказательства |
| − | + | # [[Алгоритмы на деревьях]] | |
| − | # | + | # ''fixed'' [[Дополнительный, самодополнительный граф]] (1) |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## Англоязычные термины оформить правильно | ## Англоязычные термины оформить правильно | ||
## Заменить угловые скобки на \langle и \rangle | ## Заменить угловые скобки на \langle и \rangle | ||
| Строка 60: | Строка 38: | ||
## Добавить ссылки в источники информации | ## Добавить ссылки в источники информации | ||
## Шаблоном заменить тире | ## Шаблоном заменить тире | ||
| + | # [[Теоретико-множественные операции над графами]] | ||
| + | # [[Рёберное ядро]] (2) | ||
| + | ## Добавить больше интервики в конспект | ||
| + | ## В конце теоремы в доказательстве какая-то лажа | ||
| + | ## Источники информации | ||
| + | ## Оформить следствия красиво | ||
| + | # [[Факторизация графов]] | ||
== 2. Связность в графах == | == 2. Связность в графах == | ||
# [[Отношение связности, компоненты связности]] | # [[Отношение связности, компоненты связности]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Отношение реберной двусвязности]] | # [[Отношение реберной двусвязности]] | ||
| − | |||
# [[Отношение вершинной двусвязности]] | # [[Отношение вершинной двусвязности]] | ||
| − | # | + | # [[Точка сочленения, эквивалентные определения]] |
| − | # | + | # [[Мост, эквивалентные определения]] |
# [[Граф компонент реберной двусвязности]] | # [[Граф компонент реберной двусвязности]] | ||
| − | |||
| − | |||
# [[Граф блоков-точек сочленения]] | # [[Граф блоков-точек сочленения]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[k-связность]] | # [[k-связность]] | ||
| − | # | + | # ''fixed'' [[Теорема Менгера]] (0.5) |
| − | |||
| − | |||
| − | |||
| − | |||
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами | ## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами | ||
## Тире заменить на шаблон | ## Тире заменить на шаблон | ||
## Можно добавить ссылок, оформить см. также по-другому | ## Можно добавить ссылок, оформить см. также по-другому | ||
| + | ## Источники информации | ||
# [[Теорема Менгера, альтернативное доказательство]] | # [[Теорема Менгера, альтернативное доказательство]] | ||
| − | + | # [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5) | |
| − | |||
| − | # [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | ||
## пункт "Определения" не нужен | ## пункт "Определения" не нужен | ||
## Изменить знаки неравенств в tex | ## Изменить знаки неравенств в tex | ||
## Не надо дублировать определения из другого конспекта | ## Не надо дублировать определения из другого конспекта | ||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
| + | ## find_flow какой-то стрёмный | ||
| + | ## Источники информации | ||
| + | ## k-связность с маленькой буквы | ||
| + | ## Добавить См. также на что-нибудь разумное | ||
## Добавить см. также | ## Добавить см. также | ||
== 3. Остовные деревья == | == 3. Остовные деревья == | ||
| − | + | === Построение остовных деревьев === | |
| − | + | <ol> | |
| − | + | <li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li> | |
| − | + | <li>[[Алгоритм Прима]]</li> | |
| − | + | <li> [[Алгоритм Краскала]] </li> | |
| − | + | <li> [[Алгоритм Борувки]] </li> | |
| − | + | <li> '''!!!''' [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li> | |
| − | + | # Доказательство красиво оформить | |
| − | + | # Заменить дефис на шаблон | |
| − | + | # Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт | |
| − | + | # Почему ребро uv {{---}} единственное ребро, пересекающее разрез? | |
| − | + | # Источники информации | |
| − | + | # Знаки неравенств | |
| − | + | # Категория | |
| − | + | <li> '''!!!''' [[Алгоритм двух китайцев]] (7) </li> | |
| − | + | # Англоязычные термины оформить правильно | |
| − | + | # Добавить определение покрывающего дерева | |
| − | + | # Описать реализацию красиво | |
| − | + | # Дефис заменить на тире | |
| − | + | # Отформатировать псевдокод | |
| − | + | # Доказать, почему не более V конденсаций | |
| − | + | # Источники информации оформить правильно | |
| − | + | # Доказать второе замечание | |
| − | + | # Добавить отступы в описании примера | |
| − | + | # 5ый пункт в описании алгоритма расписать чуть понятней | |
| − | + | # Категория | |
| − | + | </ol> | |
| − | + | ||
| − | + | === Свойства остовных деревьев === | |
| − | + | <ol> | |
| − | + | <li value="7">[[Матрица Кирхгофа]]</li> | |
| − | + | <li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li> | |
| − | + | <li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li> | |
| − | + | <li> [[Количество помеченных деревьев]] </li> | |
| − | + | <li> [[Коды Прюфера]] </li> | |
| − | + | </ol> | |
| − | # '''!!!''' [[Алгоритм двух китайцев]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== 4. Обходы графов == | == 4. Обходы графов == | ||
| − | + | === Эйлеровы графы === | |
| − | + | <ol> | |
| − | + | <li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li> | |
| − | + | <li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li> | |
| − | + | # Какое-то мутное доказательства | |
| − | # | + | <li> [[Алгоритм построения Эйлерова цикла]] (2) </li> |
| − | + | # Какое-то мутное доказательство леммы про корректность алгоритма | |
| − | + | <li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li> | |
| − | + | </ol> | |
| − | + | ||
| − | + | === Гамильтоновы графы === | |
| − | + | <ol> | |
| − | + | <li value="5"> [[Гамильтоновы графы]] </li> | |
| − | + | <li> [[Теорема Хватала]] </li> | |
| − | # | + | <li> [[Теорема Дирака]] </li> |
| − | + | <li> [[Теорема Оре]] </li> | |
| − | + | <li> [[Теорема Поша]]</li> | |
| − | + | <li> [[Теорема Гуйя-Ури]] </li> | |
| − | + | <li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li> | |
| − | + | <li> '''!!!''' [[Теорема Гринберга]] (5) </li> | |
| − | + | # Пояснить переходы в теореме | |
| − | + | # Внести пояснение в определение бонда | |
| − | + | # И зачем нужно доказывать отсутствие гамильтонова бонда в графе? | |
| − | + | # Картинку сделать красивой | |
| − | + | <li> '''взяли''' [[Турниры]] (6) </li> | |
| − | + | # Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация) | |
| − | + | <li> [[Теорема Редеи-Камиона]] </li> | |
| − | + | </ol> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | # | ||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | # | ||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== 5. Укладки графов == | == 5. Укладки графов == | ||
# [[Укладка графа на плоскости]] | # [[Укладка графа на плоскости]] | ||
| − | |||
| − | |||
# [[Формула Эйлера]] | # [[Формула Эйлера]] | ||
| − | # | + | # ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5) |
| − | |||
| − | |||
| − | |||
## Исправить знаки неравенств | ## Исправить знаки неравенств | ||
## Источники информации | ## Источники информации | ||
| + | ## Константы в Tex | ||
# [[Укладка дерева]] | # [[Укладка дерева]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Укладка графа с планарными компонентами реберной двусвязности]] | # [[Укладка графа с планарными компонентами реберной двусвязности]] | ||
| − | |||
| − | |||
# [[Укладка графа с планарными компонентами вершинной двусвязности]] | # [[Укладка графа с планарными компонентами вершинной двусвязности]] | ||
| − | # | + | # [[Теорема Понтрягина-Куратовского]] |
| − | + | # [[Род, толщина, крупность, число скрещиваний]] | |
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Двойственный граф планарного графа]] | # [[Двойственный граф планарного графа]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Теорема Фари]] | # [[Теорема Фари]] | ||
| + | # [[Гамма-алгоритм]] | ||
| − | == | + | == 6. Раскраски графов == |
| − | + | # [[Раскраска графа]] | |
| − | # ''fixed'' [[ | + | # ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3) |
| − | ## | + | ## Англоязычные термины |
| − | ## | + | ## Убрать определение двудольного графа и сделать интервики на основной конспект |
| − | ## | + | ## Картинку двудольного графа перенести ниже, а то плохо смотрится |
| − | ## | + | ## Интервики |
| − | # | + | ## Добавить, что можно ещё за проход в ширину проверить |
| + | ## Оформить правильно источники информации и См. также | ||
| + | ## Перенести см. также до источников информации, а ссылку заменить на интервики | ||
# [[Хроматический многочлен]] | # [[Хроматический многочлен]] | ||
# [[Формула Зыкова]] | # [[Формула Зыкова]] | ||
| Строка 300: | Строка 171: | ||
# [[Теорема Брукса]] | # [[Теорема Брукса]] | ||
# [[Верхние и нижние оценки хроматического числа]] | # [[Верхние и нижние оценки хроматического числа]] | ||
| + | # [[Хроматическое число планарного графа]] | ||
| + | # [[Многочлен Татта]] | ||
| + | # [[Теория Рамсея]] ('''10''') | ||
| + | ## Тут вообще ад какой-то | ||
== 7. Обход в глубину == | == 7. Обход в глубину == | ||
| − | # [[Обход в глубину, цвета вершин]] | + | # '''fixed''' [[Обход в глубину, цвета вершин]] (5) |
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
| + | ## Красивую картинку с цветными вершинами | ||
# [[Лемма о белых путях]] | # [[Лемма о белых путях]] | ||
| − | # | + | # [[Использование обхода в глубину для проверки связности]] |
| − | + | # [[Использование обхода в глубину для поиска цикла в ориентированном графе]] | |
| − | # | + | # [[Использование обхода в глубину для топологической сортировки]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Использование обхода в глубину для поиска компонент сильной связности]] | # [[Использование обхода в глубину для поиска компонент сильной связности]] | ||
| − | # | + | # ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4) |
| − | + | ## Что-то картинки неудачно расположены | |
| − | + | ## Кривая структура у доказательства | |
| − | |||
| − | ## | ||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
## Источники информации красиво оформить | ## Источники информации красиво оформить | ||
| − | |||
# [[Построение компонент вершинной двусвязности]] | # [[Построение компонент вершинной двусвязности]] | ||
| − | |||
| − | |||
# [[Использование обхода в глубину для поиска мостов]] | # [[Использование обхода в глубину для поиска мостов]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Построение компонент реберной двусвязности]] | # [[Построение компонент реберной двусвязности]] | ||
| − | |||
| − | |||
| − | == | + | == 8. Кратчайшие пути в графах == |
# [[Обход в ширину]] | # [[Обход в ширину]] | ||
# [[Алгоритм Форда-Беллмана]] | # [[Алгоритм Форда-Беллмана]] | ||
# [[Алгоритм Дейкстры]] | # [[Алгоритм Дейкстры]] | ||
| − | |||
# [[Алгоритм Флойда]] | # [[Алгоритм Флойда]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Алгоритм Джонсона]] | # [[Алгоритм Джонсона]] | ||
| + | # [[Алгоритм Левита]] | ||
| + | # [[Алгоритм A*]] | ||
| + | # [[Алгоритм D*]] | ||
| + | # [[Эвристики для поиска кратчайших путей]] | ||
| − | == | + | == 9. Задача о паросочетании == |
| − | # [[ | + | # [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] |
| − | |||
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | # [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | ||
| − | # | + | # [[Алгоритм Куна для поиска максимального паросочетания]] |
| − | |||
| − | |||
| − | |||
| − | |||
# [[Теорема Холла]] | # [[Теорема Холла]] | ||
| − | |||
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] | # [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] | ||
| − | |||
# [[Связь вершинного покрытия и независимого множества]] | # [[Связь вершинного покрытия и независимого множества]] | ||
| − | |||
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | # [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | ||
| − | # '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | + | # [[Теорема Татта о существовании полного паросочетания]] |
| − | ## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример | + | # '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7) |
| + | ## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками | ||
| + | # [[Декомпозиция Эдмондса-Галлаи]] | ||
| + | # '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)'' | ||
| + | ## Переменные и константы в Tex | ||
| + | ## Добавить сначала постановку задачи | ||
| + | ## Кривая ссылка на паросочетание | ||
| + | ## Дефисы на тире | ||
| + | ## Определения выделять жирным | ||
| + | ## Отформатировать псевдокоды | ||
| + | ## Зачем-то списки в доказательствах лемм использованы | ||
| + | ## Битая ссылка на соседей | ||
| + | ## Надо бы доказать все леммы | ||
| + | ## Оформить правильно источники информации | ||
| + | ## И вообще всё оформить надо | ||
| − | == | + | == 10. Задача о максимальном потоке == |
| − | # | + | # [[Определение сети, потока]] |
| − | # | + | # [[Разрез, лемма о потоке через разрез]] |
| − | + | # [[Дополняющая сеть, дополняющий путь]] | |
| − | # | + | # [[Лемма о сложении потоков]] |
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
# [[Теорема Форда-Фалкерсона]] | # [[Теорема Форда-Фалкерсона]] | ||
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | # [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | ||
| − | # | + | # '''взяли''' [[Алоритм Эдмондса-Карпа]] (5) |
| − | + | ## Полностью описать пример про грибок с картинками в конспекте | |
| − | |||
| − | ## | ||
| − | |||
| − | |||
# [[Алгоритм масштабирования потока]] | # [[Алгоритм масштабирования потока]] | ||
| − | # | + | # ''взяли'' [[Блокирующий поток]] (1) |
| − | |||
| − | |||
## англоязычные термины | ## англоязычные термины | ||
## ссылки на русскую и английскую википедию | ## ссылки на русскую и английскую википедию | ||
| + | ## Добавить немного общей информации | ||
| + | ## Расположить красиво картинки, чтобы не наезжали | ||
# [[Схема алгоритма Диница]] | # [[Схема алгоритма Диница]] | ||
| − | # | + | # '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6) |
| − | + | ## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах? | |
| − | + | ## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли? | |
| − | + | ## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он? | |
| − | ## может, назвать остаточную сеть | ||
| − | ## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и | ||
| − | ## В лемме в утверждении фигурирует поток | ||
## "Мы можем применить Лемму(2" — лемму 3, наверное? | ## "Мы можем применить Лемму(2" — лемму 3, наверное? | ||
| − | # | + | ## Дефисы на тире |
| − | ## | + | ## Знаки неравенств |
| − | + | ## Источники информации | |
| − | + | # [[Алгоритм поиска блокирующего потока в ациклической сети]] | |
| − | # [[Метод проталкивания предпотока]] | + | ## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении |
| − | ## | + | # '''!!!''' [[Метод проталкивания предпотока]] (7) |
| − | ## | + | ## Картиночки с резервуарами! |
| − | ## | + | ## Источники информации |
| + | ## Добавить см. также | ||
| + | ## Дефисы заменить на тире | ||
| + | ## Отформатировать псевдокоды | ||
# [[Алгоритм "поднять-в-начало"]] | # [[Алгоритм "поднять-в-начало"]] | ||
| − | |||
| − | |||
# [[Теорема о декомпозиции]] | # [[Теорема о декомпозиции]] | ||
| − | # | + | # ''fixed'' [[Теорема о декомпозиционном барьере]] (3) |
| − | + | ## Источники информации | |
| + | ## Пояснить,почему такие константы используются | ||
| + | ## Увеличить дроби | ||
| + | ## А что из этой теоремы следует? | ||
# [[Циркуляция потока]] | # [[Циркуляция потока]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Алгоритм Каргера для нахождения минимального разреза]] | # [[Алгоритм Каргера для нахождения минимального разреза]] | ||
| − | |||
| − | |||
| − | == | + | == 11. Задача о потоке минимальной стоимости == |
# [[Поток минимальной стоимости]] | # [[Поток минимальной стоимости]] | ||
| − | |||
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | ||
| − | # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] | + | # ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5) |
| + | ## Интервики на декомпозицию | ||
| + | ## Знаки неравенств | ||
| + | ## Источники информации | ||
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] | # [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] | ||
| − | # [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] | + | # '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5) |
| − | # [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] | + | ## Написать и оформить так, чтобы не было чуши |
| − | # | + | # ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5) |
| − | + | ## Взять задачи в шаблон | |
| + | ## Оформить покрасивей и правильней | ||
| + | # [[Венгерский алгоритм решения задачи о назначениях]] | ||
Текущая версия на 19:15, 23 февраля 2017
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
Содержание
- 1 1. Основные определения теории графов
- 2 2. Связность в графах
- 3 3. Остовные деревья
- 4 4. Обходы графов
- 5 5. Укладки графов
- 6 6. Раскраски графов
- 7 7. Обход в глубину
- 8 8. Кратчайшие пути в графах
- 9 9. Задача о паросочетании
- 10 10. Задача о максимальном потоке
- 11 11. Задача о потоке минимальной стоимости
1. Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- fixed Теорема о существовании простого пути в случае существования пути (4)
- Алгоритм и предположение зря оформлены как псевдокод
- Добавить ссылок
- Заменить названия способов доказательств на конструктивное и неконструктивное
- Исправить ошибку в доказательстве построением
- Плохо, что картинка наплывает на заголовок — переделать
- Добавить в формулировку теоремы, что вершинно-простой путь
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- взяли Матрица инцидентности графа (4 или больше, зависит от свойств)
- Добавить свойства матрицы инцидентности с доказательствами
- Добавить ссылок в источники информации
- Англоязычные термины
- Оформить правильно источники информации
- Добавить См. также на матрицу смежности
- Добавить про списки смежности и их оформить тоже в таблички
- Циклическое пространство графа
- fixed Фундаментальные циклы графа (1)
- Источники информации нормально оформить
- Подписать получше картинку
- Заменить многоточия на \ldots
- Отформатировать по правилам
- fixed Дерево, эквивалентные определения (1)
- Англоязычные термины
- Пофиксить знаки неравенств
- Источники информации нормально оформить
- Оформить красиво доказательства
- Алгоритмы на деревьях
- fixed Дополнительный, самодополнительный граф (1)
- Англоязычные термины оформить правильно
- Заменить угловые скобки на \langle и \rangle
- Интервики
- Добавить ссылки в источники информации
- Шаблоном заменить тире
- Теоретико-множественные операции над графами
- Рёберное ядро (2)
- Добавить больше интервики в конспект
- В конце теоремы в доказательстве какая-то лажа
- Источники информации
- Оформить следствия красиво
- Факторизация графов
2. Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- fixed Теорема Менгера (0.5)
- убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
- Тире заменить на шаблон
- Можно добавить ссылок, оформить см. также по-другому
- Источники информации
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины (1.5)
- пункт "Определения" не нужен
- Изменить знаки неравенств в tex
- Не надо дублировать определения из другого конспекта
- Отформатировать псевдокод
- find_flow какой-то стрёмный
- Источники информации
- k-связность с маленькой буквы
- Добавить См. также на что-нибудь разумное
- Добавить см. также
3. Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- !!! Теорема Тарьяна (критерий минимальности остовного дерева) (5)
- Доказательство красиво оформить
- Заменить дефис на шаблон
- Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
- Почему ребро uv — единственное ребро, пересекающее разрез?
- Источники информации
- Знаки неравенств
- Категория
- !!! Алгоритм двух китайцев (7)
- Англоязычные термины оформить правильно
- Добавить определение покрывающего дерева
- Описать реализацию красиво
- Дефис заменить на тире
- Отформатировать псевдокод
- Доказать, почему не более V конденсаций
- Источники информации оформить правильно
- Доказать второе замечание
- Добавить отступы в описании примера
- 5ый пункт в описании алгоритма расписать чуть понятней
- Категория
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
4. Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- взяли Покрытие ребер графа путями (3)
- Какое-то мутное доказательства
- Алгоритм построения Эйлерова цикла (2)
- Какое-то мутное доказательство леммы про корректность алгоритма
- Произвольно вычерчиваемые из заданной вершины графы
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Теорема Поша
- Теорема Гуйя-Ури
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- !!! Теорема Гринберга (5)
- Пояснить переходы в теореме
- Внести пояснение в определение бонда
- И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
- Картинку сделать красивой
- взяли Турниры (6)
- Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
- Теорема Редеи-Камиона
5. Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- fixed Непланарность и (0.5)
- Исправить знаки неравенств
- Источники информации
- Константы в Tex
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Род, толщина, крупность, число скрещиваний
- Двойственный граф планарного графа
- Теорема Фари
- Гамма-алгоритм
6. Раскраски графов
- Раскраска графа
- fixed Двудольные графы и раскраска в 2 цвета (3)
- Англоязычные термины
- Убрать определение двудольного графа и сделать интервики на основной конспект
- Картинку двудольного графа перенести ниже, а то плохо смотрится
- Интервики
- Добавить, что можно ещё за проход в ширину проверить
- Оформить правильно источники информации и См. также
- Перенести см. также до источников информации, а ссылку заменить на интервики
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Верхние и нижние оценки хроматического числа
- Хроматическое число планарного графа
- Многочлен Татта
- Теория Рамсея (10)
- Тут вообще ад какой-то
7. Обход в глубину
- fixed Обход в глубину, цвета вершин (5)
- Англоязычные термины правильно оформить
- Отформатировать псевдокод
- Красивую картинку с цветными вершинами
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- fixed Использование обхода в глубину для поиска точек сочленения (4)
- Что-то картинки неудачно расположены
- Кривая структура у доказательства
- Отформатировать псевдокод
- Источники информации красиво оформить
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
8. Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
9. Задача о паросочетании
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Теорема Татта о существовании полного паросочетания
- !!! Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
- как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
- Декомпозиция Эдмондса-Галлаи
- взяли Задача об устойчивом паросочетании (все правки стоят 10 баллов)
- Переменные и константы в Tex
- Добавить сначала постановку задачи
- Кривая ссылка на паросочетание
- Дефисы на тире
- Определения выделять жирным
- Отформатировать псевдокоды
- Зачем-то списки в доказательствах лемм использованы
- Битая ссылка на соседей
- Надо бы доказать все леммы
- Оформить правильно источники информации
- И вообще всё оформить надо
10. Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- взяли Алоритм Эдмондса-Карпа (5)
- Полностью описать пример про грибок с картинками в конспекте
- Алгоритм масштабирования потока
- взяли Блокирующий поток (1)
- англоязычные термины
- ссылки на русскую и английскую википедию
- Добавить немного общей информации
- Расположить красиво картинки, чтобы не наезжали
- Схема алгоритма Диница
- fixed Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями (6)
- может, назвать остаточную сеть , как в предыдущих конспектах?
- "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
- В лемме в утверждении фигурирует поток , но дальше про него ничего нет. Зачем он?
- "Мы можем применить Лемму(2" — лемму 3, наверное?
- Дефисы на тире
- Знаки неравенств
- Источники информации
- Алгоритм поиска блокирующего потока в ациклической сети
- !!! (10) алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
- !!! Метод проталкивания предпотока (7)
- Картиночки с резервуарами!
- Источники информации
- Добавить см. также
- Дефисы заменить на тире
- Отформатировать псевдокоды
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- fixed Теорема о декомпозиционном барьере (3)
- Источники информации
- Пояснить,почему такие константы используются
- Увеличить дроби
- А что из этой теоремы следует?
- Циркуляция потока
- Алгоритм Каргера для нахождения минимального разреза
11. Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- fixed Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети (0.5)
- Интервики на декомпозицию
- Знаки неравенств
- Источники информации
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- !!! Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
- Написать и оформить так, чтобы не было чуши
- взяли Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0.5)
- Взять задачи в шаблон
- Оформить покрасивей и правильней
- Венгерский алгоритм решения задачи о назначениях
