Изменения
Нет описания правки
# Предложите алгоритм проверки, что в двудольном графе четное число полных паросочетаний
# Предложите алгоритм проверки по двудольному графу и заданному полному паросочетанию, является ли оно единственным в этом графе (за $O(E)$).
# Предложите алгоритм для решения следующей задачи за $O(E)$. Дан двудольный граф и полное паросочетание в нем. Требуется выяснить для каждого ребра, лежит ли оно на некотором полном паросочетании.
# Задача об устойчивом паросочетании. Задан двудольный граф с равным числом вершин в долях. Для каждой вершины каждой доли известен порядок предпочтения вершин другой доли (каждая вершина знает, какая вершина другой доли ей нравится больше всего, какая вершина на втором месте, и так далее). Паросочетание называется устойчивым, если никакие две вершины не могут обменяться парами, чтобы для каждой из них новый партнер стал более предпочтительным. Требуется построить устойчивое полное паросочетание за $O(VE)$.
# Пусть $G$ - регулярный двудольный граф степени $k$. Докажите, что ребра $G$ можно разбить на $k$ полных паросочетаний.
# Пусть $G$ - регулярный граф степени $k$, $U \subset V$, $U$ содержит нечетное число вершин и $m$ - число ребер, которые соединяют вершины $U$ с вершинами $V \setminus U$. Тогда $m$ четно тогда и только тогда, когда $k$ четно.
# Докажите, что в двусвязном кубическом графе есть полное паросочетание.
# Докажите, что если в двусвязном кубическом графе не более двух мостов, то в нем есть полное паросочетание.
# Приведите пример кубического графа, в котором нет полного паросочетания.
# Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Докажите, что если удалить из $G$ не более $k - 1$ ребра, получившийся граф будет иметь полное паросочетание.
# Докажите, что если в графе $G$ есть соцветие $C$ и черенок достижим из вершины $u$, то в $G$ есть дополняющая цепь из вершины $u$ тогда и только тогда, когда она есть в графе $G/C$ (обратите внимание, она не обязана проходить через черенок, в отличие от леммы, рассказанной на лекции).
</wikitex>
