Участник:Shersh/Тикеты к 3ему терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎10. Задача о паросочетании)
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 3ему терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показано 245 промежуточных версий этого же участника)
Строка 2: Строка 2:
  
 
== 1. Основные определения теории графов ==
 
== 1. Основные определения теории графов ==
−
# '''!!!''' [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
+
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
−
## Правильно оформить англоязычные термины
 
−
## "Иногда граф, построенный таким образом, называют псевдографом (pseudograph)" {{---}} кривовато написано, надо переписать
 
−
## Дублируется определение смежных вершин
 
−
## Добавить ссылок в источники информации
 
−
## Добавить определение полного графа
 
−
## Несправедливо забыли дерево в часто используемых графах; добавить другие виды графов
 
 
# [[Лемма о рукопожатиях]]
 
# [[Лемма о рукопожатиях]]
−
## Увеличить дроби
+
# ''fixed'' [[Теорема о существовании простого пути в случае существования пути]] (4)
−
## Взять константы в tex
 
−
## Заменить умножение на \cdot
 
−
## Добавить пару слов о графах с петлями и кратными рёбрами
 
−
# '''!!!''' [[Теорема о существовании простого пути в случае существования пути]]
 
 
## Алгоритм и предположение зря оформлены как псевдокод
 
## Алгоритм и предположение зря оформлены как псевдокод
 
## Добавить ссылок
 
## Добавить ссылок
Строка 21: Строка 11:
 
## Плохо, что картинка наплывает на заголовок {{---}} переделать
 
## Плохо, что картинка наплывает на заголовок {{---}} переделать
 
## Добавить в формулировку теоремы, что вершинно-простой путь
 
## Добавить в формулировку теоремы, что вершинно-простой путь
−
# '''!!!''' [[Теорема о существовании простого цикла в случае существования цикла]]
+
# [[Теорема о существовании простого цикла в случае существования цикла]]
−
## На самом деле, конструктивное доказательство тут не очень понятное и не совсем корректное. Сделать неконструктивное и добавить нормальные картинки
 
−
## Добавить в первую теорему, что граф неориентированный
 
 
# [[Матрица смежности графа]]
 
# [[Матрица смежности графа]]
−
## "Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей. " — зачем объединять эти свойства, можно разнести на два
+
# ''взяли'' [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
−
## Что за помеченный граф?
 
−
## Добавить про что, в матрице смежности можно хранить веса рёбер
 
−
# [[Связь степени матрицы смежности и количества путей]]
 
−
## Это можно внести в прошлый конспект
 
−
## Добавить что-нибудь про бинарное возведение в степень
 
−
# '''!!!''' [[Матрица инцидентности графа]]
 
 
## Добавить свойства матрицы инцидентности с доказательствами
 
## Добавить свойства матрицы инцидентности с доказательствами
 
## Добавить ссылок в источники информации
 
## Добавить ссылок в источники информации
−
# '''!!!''' [[Циклическое пространство графа]]
+
## Англоязычные термины
−
## Пункт "Определение" не нужен, см. правила форматирования
+
## Оформить правильно источники информации
−
## Ker, dim, Rang надо запихать в \operatorname, а также кинуть ссылку на определение ядра оператора (в матане/функате на конспектах точно есть)
+
## Добавить См. также на матрицу смежности
−
## интервики
+
## Добавить про списки смежности и их оформить тоже в таблички
−
## "Литература (формулировки другие) " — "формулировки другие" относится к конкретному источнику, а не ко всей литературе.
+
# [[Циклическое пространство графа]]
−
## Заменить тире на шаблон
+
# ''fixed'' [[Фундаментальные циклы графа]] (1)
−
## Добавить ссылок в источники информации
+
## Источники информации нормально оформить
−
## Неплохо бы написать, зачем это нужно (позволяет какие-нибудь теоремы про графы доказать или что-то ещё)
+
## Подписать получше картинку
−
# [[Фундаментальные циклы графа]]
+
## Заменить многоточия на \ldots
−
# [[Дерево, эквивалентные определения]]
+
## Отформатировать по правилам
−
# '''!!!''' [[Диаметр дерева]]
+
# ''fixed'' [[Дерево, эквивалентные определения]] (1)
−
## Переименовать в Алгоритмы на деревьях
+
## Англоязычные термины
−
## Добавить другие алгоритмы (если будет много содержательных, то можно будет поставить <tex> 10 </tex> баллов за конспект)
+
## Пофиксить знаки неравенств
−
## Отформатировать псевдокод
+
## Источники информации нормально оформить
−
## Добавить категории, ссылки, см. также
+
## Оформить красиво доказательства
−
## Интервики
+
# [[Алгоритмы на деревьях]]
−
## Исправить tex
+
# ''fixed'' [[Дополнительный, самодополнительный граф]] (1)
−
# [[Дополнительный, самодополнительный граф]]
 
 
## Англоязычные термины оформить правильно
 
## Англоязычные термины оформить правильно
 
## Заменить угловые скобки на \langle и \rangle
 
## Заменить угловые скобки на \langle и \rangle
Строка 57: Строка 38:
 
## Добавить ссылки в источники информации
 
## Добавить ссылки в источники информации
 
## Шаблоном заменить тире
 
## Шаблоном заменить тире
 +
# [[Теоретико-множественные операции над графами]]
 +
# [[Рёберное ядро]] (2)
 +
## Добавить больше интервики в конспект
 +
## В конце теоремы в доказательстве какая-то лажа
 +
## Источники информации
 +
## Оформить следствия красиво
 +
# [[Факторизация графов]]
  
 
== 2. Связность в графах ==
 
== 2. Связность в графах ==
 
# [[Отношение связности, компоненты связности]]
 
# [[Отношение связности, компоненты связности]]
−
## англоязычные термины
 
−
## интервики
 
−
## Заменить тире на шаблон
 
−
## Добавить См. также
 
 
# [[Отношение реберной двусвязности]]
 
# [[Отношение реберной двусвязности]]
−
## англоязычные термины
 
 
# [[Отношение вершинной двусвязности]]
 
# [[Отношение вершинной двусвязности]]
−
## англоязычные термины
+
# [[Точка сочленения, эквивалентные определения]]
−
## Добавить ссылок
+
# [[Мост, эквивалентные определения]]
 
# [[Граф компонент реберной двусвязности]]
 
# [[Граф компонент реберной двусвязности]]
−
## Нормально оформить источники информации и см. также
 
−
## Вообще, граф G необязательно должен быть связен, можно расширить и доказать, что будет лес
 
 
# [[Граф блоков-точек сочленения]]
 
# [[Граф блоков-точек сочленения]]
−
## См. выше
 
−
## Капс какой-то зачем-то
 
−
# [[Точка сочленения, эквивалентные определения]]
 
−
## Цифры в начале определений не нужны, их можно в хедер определения
 
−
# [[Мост, эквивалентные определения]]
 
−
## англоязычные термины
 
−
## Цифры в начале определений не нужны, их можно в хедер определения
 
−
## Нормально оформить источники информации и см. также
 
 
# [[k-связность]]
 
# [[k-связность]]
−
## англоязычные термины
+
# ''fixed'' [[Теорема Менгера]] (0.5)
−
## Тире заменить на шаблон
 
−
## Палку вертикальную в множестве заменить на \mid
 
−
## Странное обозначение {{---}} \smallsetminus
 
−
# [[Теорема Менгера]]
 
 
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
 
## убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
 
## Тире заменить на шаблон
 
## Тире заменить на шаблон
 
## Можно добавить ссылок, оформить см. также по-другому
 
## Можно добавить ссылок, оформить см. также по-другому
 +
## Источники информации
 
# [[Теорема Менгера, альтернативное доказательство]]
 
# [[Теорема Менгера, альтернативное доказательство]]
−
## Заменить тире на шаблон
+
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
−
## Обращение к леммам сделать через интервики
 
−
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
 
## пункт "Определения" не нужен
 
## пункт "Определения" не нужен
 
## Изменить знаки неравенств в tex
 
## Изменить знаки неравенств в tex
 
## Не надо дублировать определения из другого конспекта
 
## Не надо дублировать определения из другого конспекта
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 +
## find_flow какой-то стрёмный
 +
## Источники информации
 +
## k-связность с маленькой буквы
 +
## Добавить См. также на что-нибудь разумное
 
## Добавить см. также
 
## Добавить см. также
  
 
== 3. Остовные деревья ==
 
== 3. Остовные деревья ==
−
# [[Матрица Кирхгофа]]
+
=== Построение остовных деревьев ===
−
## Ссылка на простой граф плохо сделана. Добавить определение в самый первый конспект и сделать на него ссылку
+
<ol>
−
## Источники информации и см. также нормально оформить
+
<li value="1">[[Остовные деревья: определения, лемма о безопасном ребре]]</li>
−
# [[Связь матрицы Кирхгофа и матрицы инцидентности]]
+
<li>[[Алгоритм Прима]]</li>
−
## Константы взять в tex
+
<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. Обходы графов ==
 +
=== Эйлеровы графы ===
 +
<ol>
 +
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
 +
<li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li>
 +
# Какое-то мутное доказательства
 +
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
 +
# Какое-то мутное доказательство леммы про корректность алгоритма
 +
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
 +
</ol>
  
−
== в процессе проверки 4. Обходы графов ==
+
=== Гамильтоновы графы ===
−
# '''fixed''' [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
+
<ol>
−
## англоязычные термины
+
<li value="5"> [[Гамильтоновы графы]] </li>
−
## не нужно по параграфу для каждого определения, либо сделать "Основные определения", либо вообще все в заголовок вынести
+
<li> [[Теорема Хватала]] </li>
−
## "См. Также" — зачем "также" с большой буквы?
+
<li> [[Теорема Дирака]] </li>
−
# [[Покрытие ребер графа путями]]
+
<li> [[Теорема Оре]] </li>
−
# [[Алгоритм построения Эйлерова цикла]]
+
<li> [[Теорема Поша]]</li>
−
# [[Произвольно вычерчиваемые из заданной вершины графы]]
+
<li> [[Теорема Гуйя-Ури]] </li>
−
# '''fixed''' [[Гамильтоновы графы]]
+
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
−
## англоязычные термины
+
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
−
# [[Теорема Хватала]]
+
# Пояснить переходы в теореме
−
# [[Теорема Дирака]]
+
# Внести пояснение в определение бонда
−
# [[Теорема Оре]]
+
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
−
# [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
+
# Картинку сделать красивой
−
# [[Турниры]]
+
<li> '''взяли''' [[Турниры]] (6) </li>
−
# [[Теорема Редеи-Камиона]]
+
# Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
 +
<li> [[Теорема Редеи-Камиона]] </li>
 +
</ol>
  
−
== в процессе проверки 5. Укладки графов ==
+
== 5. Укладки графов ==
−
# ''fixed'' [[Укладка графа на плоскости]]
+
# [[Укладка графа на плоскости]]
−
## англоязычные термины
 
−
## думаю, здесь же можно написать, что в 3D любой граф укладывается
 
 
# [[Формула Эйлера]]
 
# [[Формула Эйлера]]
−
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
+
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
−
## Дать ссылку на определения K5 и K3,3
+
## Исправить знаки неравенств
 +
## Источники информации
 +
## Константы в Tex
 
# [[Укладка дерева]]
 
# [[Укладка дерева]]
 
# [[Укладка графа с планарными компонентами реберной двусвязности]]
 
# [[Укладка графа с планарными компонентами реберной двусвязности]]
 
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
−
# ''fixed'' [[Теорема Понтрягина-Куратовского]]
+
# [[Теорема Понтрягина-Куратовского]]
−
## Определение гомеоморфизма есть в "Укладка графа на плоскости", на него и сослаться.
+
# [[Род, толщина, крупность, число скрещиваний]]
−
## Формулировку теоермы надо вынести в заголовок, например.
+
# [[Двойственный граф планарного графа]]
−
# ''fixed'' [[Двойственный граф планарного графа]]
+
# [[Теорема Фари]]
−
## англоязычные термины
+
# [[Гамма-алгоритм]]
  
−
== в процессе проверки 6. Раскраски графов ==
+
== 6. Раскраски графов ==
−
Во всем разделе — надо англоязычные термины (их по 1-2 в каждом конспекте)
+
# [[Раскраска графа]]
−
# ''fixed'' [[Раскраска графа]]
+
# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)
−
## пункт "Раскраска графа" не нужен, перенести в заголовок
+
## Англоязычные термины
−
## англоязычные термины
+
## Убрать определение двудольного графа и сделать интервики на основной конспект
−
## "Хроматическим многочлен"
+
## Картинку двудольного графа перенести ниже, а то плохо смотрится
−
## надо бы написать, почему нам вообще интересно раскрашивать графы
+
## Интервики
−
# [[Двудольные графы и раскраска в 2 цвета]]
+
## Добавить, что можно ещё за проход в ширину проверить
 +
## Оформить правильно источники информации и См. также
 +
## Перенести см. также до источников информации, а ссылку заменить на интервики
 
# [[Хроматический многочлен]]
 
# [[Хроматический многочлен]]
 
# [[Формула Зыкова]]
 
# [[Формула Зыкова]]
Строка 163: Строка 171:
 
# [[Теорема Брукса]]
 
# [[Теорема Брукса]]
 
# [[Верхние и нижние оценки хроматического числа]]
 
# [[Верхние и нижние оценки хроматического числа]]
 +
# [[Хроматическое число планарного графа]]
 +
# [[Многочлен Татта]]
 +
# [[Теория Рамсея]] ('''10''')
 +
## Тут вообще ад какой-то
  
−
== '''в процессе проверки''' 7. Обход в глубину ==
+
== 7. Обход в глубину ==
−
# [[Обход в глубину, цвета вершин]]
+
# '''fixed''' [[Обход в глубину, цвета вершин]] (5)
 +
## Англоязычные термины правильно оформить
 +
## Отформатировать псевдокод
 +
## Красивую картинку с цветными вершинами
 
# [[Лемма о белых путях]]
 
# [[Лемма о белых путях]]
 
# [[Использование обхода в глубину для проверки связности]]
 
# [[Использование обхода в глубину для проверки связности]]
Строка 171: Строка 186:
 
# [[Использование обхода в глубину для топологической сортировки]]
 
# [[Использование обхода в глубину для топологической сортировки]]
 
# [[Использование обхода в глубину для поиска компонент сильной связности]]
 
# [[Использование обхода в глубину для поиска компонент сильной связности]]
−
# [[Использование обхода в глубину для поиска точек сочленения]]
+
# ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4)
 +
## Что-то картинки неудачно расположены
 +
## Кривая структура у доказательства
 +
## Отформатировать псевдокод
 +
## Источники информации красиво оформить
 
# [[Построение компонент вершинной двусвязности]]
 
# [[Построение компонент вершинной двусвязности]]
 
# [[Использование обхода в глубину для поиска мостов]]
 
# [[Использование обхода в глубину для поиска мостов]]
 
# [[Построение компонент реберной двусвязности]]
 
# [[Построение компонент реберной двусвязности]]
  
−
== '''в процессе проверки''' 8. Кратчайшие пути в графах ==
+
== 8. Кратчайшие пути в графах ==
 
# [[Обход в ширину]]
 
# [[Обход в ширину]]
 
# [[Алгоритм Форда-Беллмана]]
 
# [[Алгоритм Форда-Беллмана]]
 
# [[Алгоритм Дейкстры]]
 
# [[Алгоритм Дейкстры]]
−
# [[Алгоритм Левита]] '''(в процессе редактирования)'''
 
 
# [[Алгоритм Флойда]]
 
# [[Алгоритм Флойда]]
−
# '''!!!''' [[Алгоритм A*]]
 
−
## что-то со второй картиночкой, там гифка, а почему-то не отображается
 
−
## псевдокод — практически копипаста из википедии, правда непонятно, что с этим делать. Я уверен, например, что никто (я тоже) не знает, что такое tentative.
 
−
## какая-то тут муть написана, что в корректности, что в оптимальности
 
−
## а еще можно написать про случай с монотонной эвристикой
 
 
# [[Алгоритм Джонсона]]
 
# [[Алгоритм Джонсона]]
 +
# [[Алгоритм Левита]]
 +
# [[Алгоритм A*]]
 +
# [[Алгоритм D*]]
 +
# [[Эвристики для поиска кратчайших путей]]
  
−
== '''в процессе проверки''' 9. Построение остовных деревьев ==
+
== 9. Задача о паросочетании ==
−
# [[Лемма о безопасном ребре]]
+
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]  
−
# [[Алгоритм Прима]]
 
−
# [[Алгоритм Краскала]]
 
−
# [[Алгоритм Борувки]]
 
−
# [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
−
# [[Алгоритм двух китайцев]]
 
−
 
 
−
== '''в процессе проверки''' 10. Задача о паросочетании ==
 
−
# [[Теорема о максимальном паросочетании и дополняющих цепях]]
 
−
## англоязычные термины
 
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
−
## что-то тут какие-то по мелочи баги, предлоги иногда пропущены и все такое
+
# [[Алгоритм Куна для поиска максимального паросочетания]]
−
# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]
 
−
## зачем-то в разделах "алгоритм" и "время работы" какие-то дурацкие отступы
 
−
## код -- копипаста с емакса
 
−
## источники перечислять с помощью *, а не :
 
 
# [[Теорема Холла]]
 
# [[Теорема Холла]]
−
## добавить ссылку на английскую википедию
 
 
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
−
## перечислять ссылки через *
 
 
# [[Связь вершинного покрытия и независимого множества]]
 
# [[Связь вершинного покрытия и независимого множества]]
−
## источники перечислять с помощью *, 1. 2.
 
 
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
−
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
+
# [[Теорема Татта о существовании полного паросочетания]]
−
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример
+
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 +
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
 +
# [[Декомпозиция Эдмондса-Галлаи]]
 +
# '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
 +
## Переменные и константы в Tex
 +
## Добавить сначала постановку задачи
 +
## Кривая ссылка на паросочетание
 +
## Дефисы на тире
 +
## Определения выделять жирным
 +
## Отформатировать псевдокоды
 +
## Зачем-то списки в доказательствах лемм использованы
 +
## Битая ссылка на соседей
 +
## Надо бы доказать все леммы
 +
## Оформить правильно источники информации
 +
## И вообще всё оформить надо
  
−
== 11. Задача о максимальном потоке ==
+
== 10. Задача о максимальном потоке ==
−
# ''fixed'' [[Определение сети, потока]]
+
# [[Определение сети, потока]]
−
## ссылки на русскую и английскую википедию
+
# [[Разрез, лемма о потоке через разрез]]  
−
# ''fixed'' [[Разрез, лемма о потоке через разрез]]
+
# [[Дополняющая сеть, дополняющий путь]]
−
## англоязычные термины
+
# [[Лемма о сложении потоков]]
−
## добавить определение минимального разреза
 
−
## ссылки на русскую и английскую википедию
 
−
# ''fixed'' [[Дополняющая сеть, дополняющий путь]]
 
−
## Дополняющую сеть также называют остаточной, указать это
 
−
## ссылки на русскую и английскую википедию
 
−
# ''fixed'' [[Лемма о сложении потоков]]
 
−
## добавить внутренних ссылок
 
 
# [[Теорема Форда-Фалкерсона]]
 
# [[Теорема Форда-Фалкерсона]]
 
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
−
## гм, и зачем "дельта" русским словом в псевдокоде?
+
# '''взяли''' [[Алоритм Эдмондса-Карпа]] (5)
−
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.
+
## Полностью описать пример про грибок с картинками в конспекте
−
# [[Алоритм Эдмондса-Карпа]]
 
−
## а описание алгоритма где?
 
−
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
 
−
## ссылки на русскую/английскую википедию
 
 
# [[Алгоритм масштабирования потока]]
 
# [[Алгоритм масштабирования потока]]
−
## ссылки на русскую/английскую википедию
+
# ''взяли'' [[Блокирующий поток]] (1)
−
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
 
−
# [[Блокирующий поток]]
 
 
## англоязычные термины
 
## англоязычные термины
 
## ссылки на русскую и английскую википедию
 
## ссылки на русскую и английскую википедию
 +
## Добавить немного общей информации
 +
## Расположить красиво картинки, чтобы не наезжали
 
# [[Схема алгоритма Диница]]
 
# [[Схема алгоритма Диница]]
−
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
+
# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
−
## "makeGl" назвать как-нибудь нормально
+
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
−
## "algorithmDinica" тоже назвать нормально
+
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
−
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
+
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
−
## может, назвать остаточную сеть $G_f$, как в предыдущих конспектах?
 
−
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?
 
−
## В лемме в утверждении фигурирует поток $f$, но дальше про него ничего нет. Зачем он?
 
 
## "Мы можем применить Лемму(2" — лемму 3, наверное?
 
## "Мы можем применить Лемму(2" — лемму 3, наверное?
−
# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]
+
## Дефисы на тире
−
## "Жадный Алгоритм" — зачем с большой буквы алгоритм?
+
## Знаки неравенств
−
## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации
+
## Источники информации
−
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
+
# [[Алгоритм поиска блокирующего потока в ациклической сети]]
−
# [[Метод проталкивания предпотока]]
+
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
−
## зачем какие-то кванторы в for?
+
# '''!!!''' [[Метод проталкивания предпотока]] (7)
−
## initialaze -> initialize
+
## Картиночки с резервуарами!
−
## названия функций в тексте оборачиваются в \mathrm
+
## Источники информации
 +
## Добавить см. также
 +
## Дефисы заменить на тире
 +
## Отформатировать псевдокоды
 
# [[Алгоритм "поднять-в-начало"]]
 
# [[Алгоритм "поднять-в-начало"]]
−
## названия функций в тексте оборачиваются в \mathrm
 
−
## relable -> relabel
 
 
# [[Теорема о декомпозиции]]
 
# [[Теорема о декомпозиции]]
−
## кванторы в псевдокоде не нужну, написать просто not exists
+
# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)
−
# [[Теорема о декомпозиционном барьере]]
+
## Источники информации
 +
## Пояснить,почему такие константы используются
 +
## Увеличить дроби
 +
## А что из этой теоремы следует?
 
# [[Циркуляция потока]]
 
# [[Циркуляция потока]]
−
## англоязычные термины
 
−
## ссылки на русскую и английскую википедию
 
−
## раздел постановка задачи не нужен, перенести в заголовок
 
−
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
 
 
# [[Алгоритм Каргера для нахождения минимального разреза]]
 
# [[Алгоритм Каргера для нахождения минимального разреза]]
−
## внутреннюю ссылку на мультиграф
 
−
## названия функций в тексте оборачиваются в \mathrm
 
  
−
== 12. Задача о потоке минимальной стоимости ==
+
== 11. Задача о потоке минимальной стоимости ==
 
# [[Поток минимальной стоимости]]
 
# [[Поток минимальной стоимости]]
−
## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)
 
 
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
 
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
−
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
+
# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
 +
## Интервики на декомпозицию
 +
## Знаки неравенств
 +
## Источники информации
 
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
 
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
−
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
+
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
−
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
+
## Написать и оформить так, чтобы не было чуши
−
# '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]]
+
# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)
−
## написать более подробный псевдокод
+
## Взять задачи в шаблон
 +
## Оформить покрасивей и правильней
 +
# [[Венгерский алгоритм решения задачи о назначениях]]

Текущая версия на 19:15, 23 февраля 2017

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.

1. Основные определения теории графов

  1. Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
  2. Лемма о рукопожатиях
  3. fixed Теорема о существовании простого пути в случае существования пути (4)
    1. Алгоритм и предположение зря оформлены как псевдокод
    2. Добавить ссылок
    3. Заменить названия способов доказательств на конструктивное и неконструктивное
    4. Исправить ошибку в доказательстве построением
    5. Плохо, что картинка наплывает на заголовок — переделать
    6. Добавить в формулировку теоремы, что вершинно-простой путь
  4. Теорема о существовании простого цикла в случае существования цикла
  5. Матрица смежности графа
  6. взяли Матрица инцидентности графа (4 или больше, зависит от свойств)
    1. Добавить свойства матрицы инцидентности с доказательствами
    2. Добавить ссылок в источники информации
    3. Англоязычные термины
    4. Оформить правильно источники информации
    5. Добавить См. также на матрицу смежности
    6. Добавить про списки смежности и их оформить тоже в таблички
  7. Циклическое пространство графа
  8. fixed Фундаментальные циклы графа (1)
    1. Источники информации нормально оформить
    2. Подписать получше картинку
    3. Заменить многоточия на \ldots
    4. Отформатировать по правилам
  9. fixed Дерево, эквивалентные определения (1)
    1. Англоязычные термины
    2. Пофиксить знаки неравенств
    3. Источники информации нормально оформить
    4. Оформить красиво доказательства
  10. Алгоритмы на деревьях
  11. fixed Дополнительный, самодополнительный граф (1)
    1. Англоязычные термины оформить правильно
    2. Заменить угловые скобки на \langle и \rangle
    3. Интервики
    4. Добавить ссылки в источники информации
    5. Шаблоном заменить тире
  12. Теоретико-множественные операции над графами
  13. Рёберное ядро (2)
    1. Добавить больше интервики в конспект
    2. В конце теоремы в доказательстве какая-то лажа
    3. Источники информации
    4. Оформить следствия красиво
  14. Факторизация графов

2. Связность в графах

  1. Отношение связности, компоненты связности
  2. Отношение реберной двусвязности
  3. Отношение вершинной двусвязности
  4. Точка сочленения, эквивалентные определения
  5. Мост, эквивалентные определения
  6. Граф компонент реберной двусвязности
  7. Граф блоков-точек сочленения
  8. k-связность
  9. fixed Теорема Менгера (0.5)
    1. убрать кванторы там, где они не нужны (в формулировках теорем) и заменить словами
    2. Тире заменить на шаблон
    3. Можно добавить ссылок, оформить см. также по-другому
    4. Источники информации
  10. Теорема Менгера, альтернативное доказательство
  11. Вершинная, реберная связность, связь между ними и минимальной степенью вершины (1.5)
    1. пункт "Определения" не нужен
    2. Изменить знаки неравенств в tex
    3. Не надо дублировать определения из другого конспекта
    4. Отформатировать псевдокод
    5. find_flow какой-то стрёмный
    6. Источники информации
    7. k-связность с маленькой буквы
    8. Добавить См. также на что-нибудь разумное
    9. Добавить см. также

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

Построение остовных деревьев

  1. Остовные деревья: определения, лемма о безопасном ребре
  2. Алгоритм Прима
  3. Алгоритм Краскала
  4. Алгоритм Борувки
  5. !!! Теорема Тарьяна (критерий минимальности остовного дерева) (5)
    1. Доказательство красиво оформить
    2. Заменить дефис на шаблон
    3. Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
    4. Почему ребро uv — единственное ребро, пересекающее разрез?
    5. Источники информации
    6. Знаки неравенств
    7. Категория
  6. !!! Алгоритм двух китайцев (7)
    1. Англоязычные термины оформить правильно
    2. Добавить определение покрывающего дерева
    3. Описать реализацию красиво
    4. Дефис заменить на тире
    5. Отформатировать псевдокод
    6. Доказать, почему не более V конденсаций
    7. Источники информации оформить правильно
    8. Доказать второе замечание
    9. Добавить отступы в описании примера
    10. 5ый пункт в описании алгоритма расписать чуть понятней
    11. Категория

Свойства остовных деревьев

  1. Матрица Кирхгофа
  2. Связь матрицы Кирхгофа и матрицы инцидентности
  3. Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
  4. Количество помеченных деревьев
  5. Коды Прюфера

4. Обходы графов

Эйлеровы графы

  1. Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
  2. взяли Покрытие ребер графа путями (3)
    1. Какое-то мутное доказательства
  3. Алгоритм построения Эйлерова цикла (2)
    1. Какое-то мутное доказательство леммы про корректность алгоритма
  4. Произвольно вычерчиваемые из заданной вершины графы

Гамильтоновы графы

  1. Гамильтоновы графы
  2. Теорема Хватала
  3. Теорема Дирака
  4. Теорема Оре
  5. Теорема Поша
  6. Теорема Гуйя-Ури
  7. Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
  8. !!! Теорема Гринберга (5)
    1. Пояснить переходы в теореме
    2. Внести пояснение в определение бонда
    3. И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
    4. Картинку сделать красивой
  9. взяли Турниры (6)
    1. Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
  10. Теорема Редеи-Камиона

5. Укладки графов

  1. Укладка графа на плоскости
  2. Формула Эйлера
  3. fixed Непланарность [math]K_5[/math] и [math]K_{3,3}[/math] (0.5)
    1. Исправить знаки неравенств
    2. Источники информации
    3. Константы в Tex
  4. Укладка дерева
  5. Укладка графа с планарными компонентами реберной двусвязности
  6. Укладка графа с планарными компонентами вершинной двусвязности
  7. Теорема Понтрягина-Куратовского
  8. Род, толщина, крупность, число скрещиваний
  9. Двойственный граф планарного графа
  10. Теорема Фари
  11. Гамма-алгоритм

6. Раскраски графов

  1. Раскраска графа
  2. fixed Двудольные графы и раскраска в 2 цвета (3)
    1. Англоязычные термины
    2. Убрать определение двудольного графа и сделать интервики на основной конспект
    3. Картинку двудольного графа перенести ниже, а то плохо смотрится
    4. Интервики
    5. Добавить, что можно ещё за проход в ширину проверить
    6. Оформить правильно источники информации и См. также
    7. Перенести см. также до источников информации, а ссылку заменить на интервики
  3. Хроматический многочлен
  4. Формула Зыкова
  5. Формула Уитни
  6. Теорема Брукса
  7. Верхние и нижние оценки хроматического числа
  8. Хроматическое число планарного графа
  9. Многочлен Татта
  10. Теория Рамсея (10)
    1. Тут вообще ад какой-то

7. Обход в глубину

  1. fixed Обход в глубину, цвета вершин (5)
    1. Англоязычные термины правильно оформить
    2. Отформатировать псевдокод
    3. Красивую картинку с цветными вершинами
  2. Лемма о белых путях
  3. Использование обхода в глубину для проверки связности
  4. Использование обхода в глубину для поиска цикла в ориентированном графе
  5. Использование обхода в глубину для топологической сортировки
  6. Использование обхода в глубину для поиска компонент сильной связности
  7. fixed Использование обхода в глубину для поиска точек сочленения (4)
    1. Что-то картинки неудачно расположены
    2. Кривая структура у доказательства
    3. Отформатировать псевдокод
    4. Источники информации красиво оформить
  8. Построение компонент вершинной двусвязности
  9. Использование обхода в глубину для поиска мостов
  10. Построение компонент реберной двусвязности

8. Кратчайшие пути в графах

  1. Обход в ширину
  2. Алгоритм Форда-Беллмана
  3. Алгоритм Дейкстры
  4. Алгоритм Флойда
  5. Алгоритм Джонсона
  6. Алгоритм Левита
  7. Алгоритм A*
  8. Алгоритм D*
  9. Эвристики для поиска кратчайших путей

9. Задача о паросочетании

  1. Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
  2. Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
  3. Алгоритм Куна для поиска максимального паросочетания
  4. Теорема Холла
  5. Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
  6. Связь вершинного покрытия и независимого множества
  7. Матрица Татта и связь с размером максимального паросочетания в двудольном графе
  8. Теорема Татта о существовании полного паросочетания
  9. !!! Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
    1. как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
  10. Декомпозиция Эдмондса-Галлаи
  11. взяли Задача об устойчивом паросочетании (все правки стоят 10 баллов)
    1. Переменные и константы в Tex
    2. Добавить сначала постановку задачи
    3. Кривая ссылка на паросочетание
    4. Дефисы на тире
    5. Определения выделять жирным
    6. Отформатировать псевдокоды
    7. Зачем-то списки в доказательствах лемм использованы
    8. Битая ссылка на соседей
    9. Надо бы доказать все леммы
    10. Оформить правильно источники информации
    11. И вообще всё оформить надо

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

  1. Определение сети, потока
  2. Разрез, лемма о потоке через разрез
  3. Дополняющая сеть, дополняющий путь
  4. Лемма о сложении потоков
  5. Теорема Форда-Фалкерсона
  6. Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
  7. взяли Алоритм Эдмондса-Карпа (5)
    1. Полностью описать пример про грибок с картинками в конспекте
  8. Алгоритм масштабирования потока
  9. взяли Блокирующий поток (1)
    1. англоязычные термины
    2. ссылки на русскую и английскую википедию
    3. Добавить немного общей информации
    4. Расположить красиво картинки, чтобы не наезжали
  10. Схема алгоритма Диница
  11. fixed Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями (6)
    1. может, назвать остаточную сеть [math]G_f[/math], как в предыдущих конспектах?
    2. "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
    3. В лемме в утверждении фигурирует поток [math]f[/math], но дальше про него ничего нет. Зачем он?
    4. "Мы можем применить Лемму(2" — лемму 3, наверное?
    5. Дефисы на тире
    6. Знаки неравенств
    7. Источники информации
  12. Алгоритм поиска блокирующего потока в ациклической сети
    1. !!! (10) алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
  13. !!! Метод проталкивания предпотока (7)
    1. Картиночки с резервуарами!
    2. Источники информации
    3. Добавить см. также
    4. Дефисы заменить на тире
    5. Отформатировать псевдокоды
  14. Алгоритм "поднять-в-начало"
  15. Теорема о декомпозиции
  16. fixed Теорема о декомпозиционном барьере (3)
    1. Источники информации
    2. Пояснить,почему такие константы используются
    3. Увеличить дроби
    4. А что из этой теоремы следует?
  17. Циркуляция потока
  18. Алгоритм Каргера для нахождения минимального разреза

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

  1. Поток минимальной стоимости
  2. Теорема Форда-Фалкерсона о потоке минимальной стоимости
  3. fixed Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети (0.5)
    1. Интервики на декомпозицию
    2. Знаки неравенств
    3. Источники информации
  4. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
  5. !!! Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
    1. Написать и оформить так, чтобы не было чуши
  6. взяли Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0.5)
    1. Взять задачи в шаблон
    2. Оформить покрасивей и правильней
  7. Венгерский алгоритм решения задачи о назначениях
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_3ему_терму&oldid=60458»