Изменения
Нет описания правки
# Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Докажите, что если удалить из $G$ не более $k - 1$ ребра, получившийся граф будет иметь полное паросочетание.
# Докажите, что если в графе $G$ есть соцветие $C$ и черенок достижим из вершины $u$, то в $G$ есть дополняющая цепь из вершины $u$ тогда и только тогда, когда она есть в графе $G/C$ (обратите внимание, она не обязана проходить через черенок, в отличие от леммы, рассказанной на лекции).
# Предложите алгоритм разбиения регулярного двудольного графа степени $k$ на $k$ совершенных паросочетаний за время $O(VE)$.
# Рассмотрим двудольный граф, в качестве одной доли возьмем компоненты связности $D(G)$, а в качестве другой - вершины множества $A$. Соединим вершины ребром, если из соответствующей компоненты в соответствующую вершину есть хотя бы одно ребро. Докажите, что для любого множества $S$ вершин из $A(G)$ множество $N(S)$ содержит больше вершин, чем $S$.
# Докажите, что любое ребро, соединяющее вершины из $D(G)$ и $A(G)$, лежит в некотором максимальном паросочетании в $G$.
# Докажите, что любое ребро, соединяющее вершины из $C(G)$ и $A(G)$, не лежит ни в одном максимальном паросочетании в $G$.
# Будем говорить, что доля $X$ двудольного графа имеет запас, если для любого непустого $S \subset X$ выполнено $|N(S)| > |S|$. Могут ли обе доли двудольного графа иметь запас?
# Как устроена декомпозиции Галлаи-Эдмондса для двудольного графа, в котором одна из долей имеет запас?
# Предложите полиномиальный алгоритм построения декомпозиции Галлаи-Эдмондса, работающий за $O(V^2E)$.
# Пусть $v \in C(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
# Пусть $v \in D(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
# Докажите, что если $f$ - поток, и в графе $G_f$ нет циклов отрицательного веса и пути отрицательного веса из $s$ в $t$, то $f$ - поток минимальной стоимости среди всех потоков в $G$ (вне зависимости от величины).
# Пусть в графе нет циклов отрицательной стоимости. Рассмотрим алгоритм: начав с нулевого потока, каждый раз дополняем поток вдоль пути минимальной стоимости способности из $s$ в $t$ в остаточной сети. Докажите, что стоимости найденных путей не убывают.
# Пусть в графе нет циклов отрицательной стоимости. Предложите алгоритм поиска потока минимальной среди всех потоков стоимости (вне зависимости от величины).
</wikitex>
