Изменения
Нет описания правки
# Приведите пример кубического графа, в котором нет полного паросочетания.
# Предложите алгоритм разбиения регулярного двудольного графа степени $k$ на $k$ совершенных паросочетаний за время $O(VE)$.
# Докажите, что ребра двудольного графа можно раскрасить в $k$ цветов, где $k$ - максимальная степень вершины, причем никакие два ребра, инцидентные одной вершине, не будут иметь одинаковый цвет.
# Пусть максимальное паросочетание в графе $G$ имеет размер $k$. Каким может быть размер максимального по включению паросочетания в $G$?
# Докажите, что любое дерево имеет не более одного полного паросочетания. Верно ли это для максимальных, но не полных паросочетаний?
# Докажите, что если в графе четное число вершин и любая вершина имеет степень хотя бы $n / 2$, то в таком графе есть полное паросочетание. Можно ли усилить это утверждение?
# Рассмотрим в двудольном графе с долями $X$ и $Y$ множества $S\subset X$ и $T \subset Y$. Пусть существуют паросочетания $M_S$ и $M_T$, которые покрывают $S$ и $T$, соответственно. Докажите, что существует паросочетание, которое покрывает $S\cup T$.
# Докажите, что граф с $2n$ вершинами и степенью любой вершины не больше $k$ имеет не более $k^n$ различных полных паросочетаний.
# Дайте оценку, аналогичную оценке из предыдущего задания, для двудольного графа с долями, содержащими по $n$ вершин.
# Завершите доказательство теоремы о сжатии соцветий.
# Будем называть множество ребер набором 1-2-путей, если любая компонента связности в этом множестве является содержит не более двух ребер. Предложите алгоритм построения набора 1-2-путей в двудольном графе, покрывающего все вершины.
# В регулярном графе $G$ степень любой вершины $k$ и $\lambda(G) \ge k - 1$. Докажите, что в $G$ есть полное паросочетание.
# Докажите, что ребра кубического графа можно раскрасить в разные цвета так, что для каждого цвета существует ровно три ребра этого цвета, причем они представляют собой простой путь.
</wikitex>
