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

Презентация:



Advertisements
Похожие презентации
M-чередующаяся декомпозиция Лекция 10. Нечетная декомпозиция Теорема 9.7 (Lovász [1972] ) Граф является фактор-критическим тогда и только тогда, когда.
Advertisements

Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин.
Паросочетания в двудольных графах Лекция 8. Паросочетание Паросочетанием в графе G называется множество попарно несмежных ребер.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
Алгоритмы сканирования и обхода Лекция 3. Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s,
Остовные деревья Лекция 4. Задача «Минимальное остовное дерево» Дано: Граф G, веса c: E(G) R. Найти остовное дерево в G наименьшего веса или определить,
NP-полнота Основные NP-полные задачи. Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество.
Задачи раскраски графов А.В.Пяткин. Вершинная раскраска Раскрасить вершины графа в минимальное число цветов так, чтобы смежные вершины получали бы разные.
Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.
Линейное программирование Задача теории расписаний.
Потоки в сетях Теорема о максимальном потоке и минимальном разрезе Лекция 6.
{ изоморфизм графов - подграф - планарный и плоский графы - укладка плоских графов - маршруты, связность и компоненты - метрические характеристики - Эйлеровы.
П АРОСОЧЕТАНИЯ В ДВУДОЛЬНЫХ ГРАФАХ. Подмножество М ребер графа G=(V,E) называется паросочетанием, если никакие два ребра из М не имеют общей вершины.
Матроиды Лекция 12. Введение Даны система множеств (E, F ), то есть конечное множество E, F 2 E и стоимостная функция c : F R, найти элемент из F, стоимость.
Определение Две плоскости называются параллельными, если они не пересекаются. α α β, тогда αβ β.
Графы Степень вершины Подсчет числа ребер графа. Разминка… Вставьте недостающие слова в предложения (граф, титул, ребро, вершина) Всем известно, что слово.
Двусвязность Лекция 14. Связность компонент Граф G называется k-связным (k 1), если не существует набора из k-1 или меньшего числа узлов V` V, такого,
О. Степенным рядом называется функциональный ряд вида (1) где a 0, a 1, a 2, …,a n,…, а также x 0 – постоянные числа. Точку x 0 называют центром степенного.
Построение минимальной сильно связной реконструкции произвольных орграфов Выполнила А.С. Кадушкина Научный руководитель. проф. В.Н. Салий.
Определение Прямая и плоскость называются параллельными, если они не пересекаются. α а - прямая, α - плоскость а а α,тогда а α.
Транксрипт:

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

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

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

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

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

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

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

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

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.

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

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.

Доказательство Осталось найти паросочетание между вершинами 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)| противоречие.

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

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

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

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

Пусть в 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.

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

Ушки Определение 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 пути, то декомпозиция называется совершенной.

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

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

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

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

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

Доказательство Пусть 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, которая принадлежит Ĝ.

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