Разбор теоретического задания 4

Задача 1

Ольга Самойлова

Задача 2

Михаил Слабодкин

Задача 3

Михаил Иванов

Задачи с семинара 6

1. Полезные обозначения: $v(G)$ — количество вершин в графе $G$, $\alpha'(G)$ — размер максимального паросочетания $G$, $\mathop{\mathrm{def}}(G)=v(G)-2\alpha'(G)$ — дефицит графа $G$, число вершин, не покрытых максимальным паросочетанием, $c(G)$ — число компонент связности графа $G$, $o(G)$ — число компонент связности графа $G$, содержащих нечётное число вершин. Совершенным называется паросочетание размера $\frac{v(G)}2$, почти совершенным — паросочетание размера $\frac{v(G)-1}2$. Граф $G$ называется фактор-критическим, если для любой вершины $v\in V(G)$ существует почти совершенное паросочетание $G$, не покрывающее $v$ (другими словами, есть совершенное паросочетание в $G-v$).

2. Барьер графа $G$ — такое множество $B\subseteq V(G)$, для которого $\mathop{\mathrm{def}}(G)=o(G-B)-|B|$. Барьер предоставляет точную верхнюю оценку на $\alpha'(G)$.

3. Сертификат максимальности паросочетания (до сжатия соцветий) — структурная теорема Галлаи-Эдмондса. В графе $G$ обозначим $D$ множество всех вершин, для каждой из которых существует максимальное паросочетание $G$, не покрывающее эту вершину (другими словами, множество таких вершин $v$, что $\alpha'(G)=\alpha'(G-v)$). Обозначим $A$ множество вершин, не принадлежащих $D$, но смежных с некоторой вершиной $D$. Обозначим $C$ множество всех остальных вершин. Тогда:

   1) $G(D)$ состоит из нескольких фактор-критических компонент связности, число которых превосходит $|A|$, в частности, все эти компоненты состоят из нечётного числа вершин;

   2) в двудольном графе, одну долю которого составляет $A$, а другую — $G(D)$, для доли $A$ выполнено условие Холла, причём с запасом (у любого непустого подмножества $A$ число смежных с ним нечётных компонент $G(D)$ превосходит размер этого подмножества);

   3) $A$ — барьер $G$;

   4) $G(C)$ содержит совершенное паросочетание;

   5) любое совершенное паросочетание $G$ состоит из совершенного паросочетания $G(C)$, паросочетания между $A$ и нечётными компонентами $G(D)$, а также почти совершенных паросочетаний во всех компонентах $G(D)$;

   6) $\mathop{\mathrm{def}}(G)=c(G(D))-|A|=o(G(D))-|A|$.

4. Формула Бержа: $\mathop{\mathrm{def}}(G)=\max\limits_{S\subseteq V(G)}{o(G-S)-|S|}$. Альтернативая формулировка: в любом графе $G$ есть барьер.

5. Формулировка задачи поиска максимального паросочетания в терминах целочисленного линейного программирования. Ослабление до задачи линейного программирования.

   а) Докажите, что для двудольного графа максимум целочисленной задачи равен максимуму линейной.

   б) Докажите, что для произвольного графа максимум полуцелочисленной задачи равен максимуму линейной.