Список заданий по АСД 2к 2016 весна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<wikitex> # Докажите лемму Галлаи: если при удалении любой вершины графа размер его максималь...»)
(нет различий)

Версия 16:42, 14 февраля 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>