Изменения
Нет описания правки
# Докажите реберную теорему Менгера: минимальное число ребер, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу реберно непересекающихся путей из $s$ в $t$.
# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
# Предложите алгоритм проверки, что в графе единственный минимальный разрез
# Петя в алгоритме Форда-Фалкерсона для поиска паросочетания в двудольном графе сделал ошибку: оставил рёбра между долями графа неориентированными. Построить пример, на котором алгоритм будет работать неправильно.
# Доказать теорему Холла: что в двудольном графе $G$ существует полное паросочетание тогда и только тогда, когда для любого множества вершин левой доли $A \subset X$ выполнено $|N(A)| \ge |A|$. ($N(A)$ - множество соседей вершин из $A$)
# Докажите, что в регулярном двудольном графе существует полное паросочетание.
# Дефектом множества вершин левой доли в графе называется $def(A) = |N(A)| - |A|$. Найти в двудольном графе множество с минимальным дефектом.
# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом вершинно-непересекающихся путей. Сведите эту задачу к задаче о максимальном паросочетании.
# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом реберно-непересекающихся путей.
# Докажите, что если в графе единственное паросочетание, то в нем есть мост
# Предложите алгоритм проверки, что в двудольном графе четное число полных паросочетаний
# Предложите алгоритм проверки по двудольному графу и заданному паросочетанию, является ли оно единственным в этом графе (за $O(E)$).
</wikitex>
