Фактор-критические графы Лекция 9. Необходимость Необходимое условие для графа иметь совершенное паросочетание – это четное число вершин в каждой компоненте. - презентация

1 Фактор-критические графы Лекция 9

2 Необходимость Необходимое условие для графа иметь совершенное паросочетание – это четное число вершин в каждой компоненте связности. Однако это условие не является достаточным.

3 Нечетные связные компоненты

4 # нечетных связных компонент Пусть X V(G), и q G (X) число нечетных связных компонент в G – X. Если q G (X) > |X| для некоторого X V(G), то G не имеет совершенного паросочетания.

5 Условие Татта Определение 9.1 Граф G удовлетворяет условию Татта, если q G (X) | X | для всех X V(G). Непустое множество вершин X V(G) называется барьером, если q G (X) = | X |.

6 Фактор-критический граф Утверждение 9.2 Для любого графа G и любого X V(G) имеем q G (X) – | X | |V(G)| (mod 2). Определение 9.3 Граф G называется фактор-критическим, если G – v имеет совершенное паросочетание для каждого v V(G). Паросочетание называется почти совершенным, если оно покрывает все вершины кроме одной.

7 Упражнение 9.1 Доказать, что фактор-критический граф всегда является связным.

8 Теорема Татта Теорема 9.4 (Tutte [1947] ) Граф G имеет совершенное паросочетание тогда и только тогда, когда он удовлетворяет условию Татта: q G (X) | X | для всех X V(G).

9 q G (X) | X | для всех X V(G) Докажем достаточность индукцией по |V(G)|. Утверждение очевидно для |V(G)| 2. Пусть G удовлетворяет условию Татта. в нем четное число вершин (иначе q G ( ) 1). Утверждение 9.2 |X| – q G (X) четно для всех X V(G). Четность и условие Татта одновершинное множество является барьером. Выберем максимальный по мощности барьер X.

10 q G (X) | X | для всех X V(G) Выберем максимальный по мощности барьер X. –G – X имеет |X| нечетных связных компонент. –В G – X нет четных связных компонент. Докажем, что каждая нечетная связная компонента в G – X является фактор-критической (для любой v G – X, G – X – v имеет совершенное паросочетание).

11 q G (X) | X | для всех X V(G) Пусть C нечетная связная компонента G – X и v V(C), такие что в C – v нет совершенного паросочетания. По индукции Y V(C)\{v} такой что q C–v (Y) > |Y |. Утверждение 9.2 q C–v (Y) – |Y | четно q C–v (Y) |Y |+2. Так как X, Y, {v} попарно не пересекаются, то q G (X U Y U {v}) = q G (X) – 1 + q C (Y U {v}) = = |X | – 1 + q C–v (Y) |X | – 1 + |Y | + 2 = = |X U Y U {v}|. X U Y U {v} – барьер, что противоречит максимальности X.

12 Доказательство Осталось найти паросочетание между вершинами X и представителями связных нечетных компонент. Двудольный граф G' : V (G' ) = X U Z, где Z множество вершин, соответствующих связным нечетным компонентам C z в G – X. Вершины x X и z Z связаны ребром {x,z} E(G' ), если ребро из x в одну из вершин C z. Если в G ' нет совершенного паросочетания, то Теорема Фробениуса A Z такое, что | G' (A)| < |A|. q G ( G' (A)) |A| > | G' (A)| противоречие.

13 Теорема Татта Теорема 9.4 (Tutte [1947] ) Граф G имеет совершенное паросочетание тогда и только тогда, когда он удовлетворяет условию Татта: q G (X) | X | для всех X V(G).

14 Формула Бержа-Татта Теорема 9.5 (Berge [1948] )

15 Доказательство Для любого X V(G), любое паросочетание должно оставлять по крайней мере q G (X) – | X | вершин не покрытыми. 2ν(G) + q G (X) – | X | | V(G) |.

16 Доказательство k G H Если в H есть совершенное паросочетание, то 2ν(G) + k 2ν(H) – k = |V(H)| – k = |V(G)|.

17 Пусть в H нет совершенного паросочетания. Теорема Татта Y V(H), такое что q(Y) > |Y|. Утверждение 9.2 k имеет ту же четность как и V(G) V(H) – четно. Y и q H (Y) > 1. Y содержит все новые вершины. q G (YV(G)) = q H (Y) > |Y| = |YV(G)| + k. Противоречие с определением k.

18 Формула Бержа-Татта Теорема 9.5 (Berge [1948] )

19 Ушки Определение 9.6 Декомпозицией графа G на множество ушек называется последовательность r, P 1,...,P k с G=({r}, ) + P P k, такая что каждый P i есть либо путь с граничными точками из {r} U V(P 1 ) U... U V(P i–1 ), либо цикл, в котором ровно одна из его вершин принадлежит {r} U V(P 1 ) U... U V(P i–1 ) (i {1,...,k}). P 1,...,P k называются ушками. Если k 1, P 1 цикл длины не меньше 3, и P 2,...,P k пути, то декомпозиция называется совершенной.

20 Декомпозиция P1P1 P2P2 P3P3 P4P4 P5P5

21 Нечетная декомпозиция Определение 9.7 Декомпозиция называется нечетной, если каждое ушко имеет нечетную длину. Теорема 9.8 (Lovász [1972] ) Граф является фактор-критическим тогда и только тогда, когда он имеет нечетную декомпозицию. Более того, начальная вершина в декомпозиции может быть выбрана произвольна.

22 Доказательство Пусть G граф с фиксированной нечетной декомпозицией. Докажем что G фактор критический индукцией на число ушек. Пусть P последнее ушко в нечетной декомпозиции.

23 Индукция P P G G

24 Доказательство Выберем произвольную вершину z, как начальную вершину декомпозиции. Пусть M почти совершенное паросочетание в G покрывающее V(G)/{z}. Предположим, что мы построили нечетную декомпозицию для Ĝ G такую, что z V(Ĝ), и M E(Ĝ) является почти совершенным паросочетанием в Ĝ.

25 Доказательство Пусть G Ĝ. G – связный, то {x,y} E(G) \ E(Ĝ), и x V(Ĝ). Если y V(Ĝ),то {x,y} следующее ушко. Иначе, пусть N почти совершенное паросочетание в G покрывающее V(G)/{y}. Тогда MN содержит путь P из y в z. Пусть w будет ближайшая к y вершина в P, которая принадлежит Ĝ.

26 MN и P [y,w] P y Ĝ z x G w M N