Изменения

Перейти к: навигация, поиск

Теория графов:Тикеты

1130 байт добавлено, 5 сентябрь
Нет описания правки
# Категория
</ol>
 
== 2 Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Точка сочленения, эквивалентные определения]] 4
## разобраться с доказательством теоремы из 7 пунктов
* [[Мост, эквивалентные определения]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
* [[Задача о динамической связности]]
 
== Обходы графов ==
=== 2 3 Эйлеровы графы ===
# [[Алгоритм построения Эйлерова цикла]] (2)
## Какое-то мутное доказательство леммы про корректность алгоритма
=== 3 4 Гамильтовы графы ===
<ol value="2">
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
</ol>
== 45. Обход в глубину ==
# [[Обход в глубину, цвета вершин]] 1
## поправить тех (цифры и аргументы функций)
## поправить тех для "dfs", "paint"
== 56. Кратчайшие пути в графах ==
# [[Обход в ширину]] 5
## исправить речевые ошибки в описании
## вряд ли 16MB памяти в таблице про Европу
== 67. Задача о паросочетании ==
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]] 0.5
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
== 78. Задача о максимальном потоке ==
# [[Определение сети, потока]] 0.5
## добавить "см. также"
## добавить "см. также"
== 89. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]] 3
## исправить замечания из обсуждения статьи

Навигация