Изменения
Новая страница: «<wikitex> # Докажите лемму Галлаи: если при удалении любой вершины графа размер его максималь...»
<wikitex>
# Докажите лемму Галлаи: если при удалении любой вершины графа размер его максимального паросочетания не изменяется, то граф фактор-критический.
# Докажите, что единственное множество Татта фактор-критического графа - пустое множество
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $D(G\setminus a)=D(G)$.
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $A(G\setminus a)=A(G)\setminus a$.
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $C(G\setminus a)=C(G)$.
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $\alpha'(G\setminus a)=\alpha'(G)-1$ ($\alpha'(G)$ - размер максимального паросочетания в $G$).
# Докажите теорему Галлаи-Эдмондса о структурной декомпозиции.
# Рассмотрим двудольный граф, в качестве одной доли возьмем компоненты связности $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|$. Могут ли обе доли двудольного графа иметь запас?
# Как устроена декомпозиции Галлаи-Эдмондса для двудольного графа, в котором одна из долей имеет запас?
# Пусть $v \in C(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
# Пусть $v \in D(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
</wikitex>
# Докажите лемму Галлаи: если при удалении любой вершины графа размер его максимального паросочетания не изменяется, то граф фактор-критический.
# Докажите, что единственное множество Татта фактор-критического графа - пустое множество
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $D(G\setminus a)=D(G)$.
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $A(G\setminus a)=A(G)\setminus a$.
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $C(G\setminus a)=C(G)$.
# Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $\alpha'(G\setminus a)=\alpha'(G)-1$ ($\alpha'(G)$ - размер максимального паросочетания в $G$).
# Докажите теорему Галлаи-Эдмондса о структурной декомпозиции.
# Рассмотрим двудольный граф, в качестве одной доли возьмем компоненты связности $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|$. Могут ли обе доли двудольного графа иметь запас?
# Как устроена декомпозиции Галлаи-Эдмондса для двудольного графа, в котором одна из долей имеет запас?
# Пусть $v \in C(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
# Пусть $v \in D(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
</wikitex>
