Список заданий по АСД 2к 2016 весна

<wikitex>

1. Докажите лемму Галлаи: если при удалении любой вершины графа размер его максимального паросочетания не изменяется, то граф фактор-критический.
2. Докажите, что единственное множество Татта фактор-критического графа - пустое множество
3. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $D(G\setminus a)=D(G)$.
4. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $A(G\setminus a)=A(G)\setminus a$.
5. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $C(G\setminus a)=C(G)$.
6. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $\alpha'(G\setminus a)=\alpha'(G)-1$ ($\alpha'(G)$ - размер максимального паросочетания в $G$).
7. Докажите теорему Галлаи-Эдмондса о структурной декомпозиции.
8. Рассмотрим двудольный граф, в качестве одной доли возьмем компоненты связности $D(G)$, а в качестве другой - вершины множества $A$. Соединим вершины ребром, если из соответствующей компоненты в соответствующую вершину есть хотя бы одно ребро. Докажите, что для любого множества $S$ вершин из $A(G)$ множество $N(S)$ содержит больше вершин, чем $S$.
9. Докажите, что любое ребро, соединяющее вершины из $D(G)$ и $A(G)$, лежит в некотором максимальном паросочетании в $G$.
10. Докажите, что любое ребро, соединяющее вершины из $C(G)$ и $A(G)$, не лежит ни в одном максимальном паросочетании в $G$.
11. Будем говорить, что доля $X$ двудольного графа имеет запас, если для любого непустого $S \subset X$ выполнено $|N(S)| > |S|$. Могут ли обе доли двудольного графа иметь запас?
12. Как устроена декомпозиции Галлаи-Эдмондса для двудольного графа, в котором одна из долей имеет запас?
13. Пусть $v \in C(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
14. Пусть $v \in D(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?

</wikitex>