Системы различных представителей, теорема Холла о совершенном паросочетании в двудольном графе

Определение: Система различных представителей для семейтсва конечных множеств S = {A1, A2,..,Ai,…,Am} есть система попарно различных элементов {a1, a2,…, ai,…, am}, для которых ai ∈ Ai [i=1,2…m].

По семейству множеств S построим двудольный граф G = (V1,V2,E), положив V1 = S = {A1, A2,..,Ai,…,Am} V2 = ∪i=1..mAi ={a1,…,ar}. Ребро е=(Ai, aj)∈E ⇔ aj∈Ai. Семейство множеств S имеет СРП ⇔ когда граф G имеет совершенное паросочетание. Для двудольного графа G = (V1,V2,E) можно построить семейство S(u) = {v∈V2: ребро e=(u,v)∈E; u∈V1}. Тогда семейство множеств S имеет СРП ⇔ граф G имеет совершенное паросочетание. Вопрос о наличии совершенного паросочетания у двудольного графа G эквивалентен вопросу о наличии СРП для семейства множеств S, которое порождает двудольный граф G описанным выше способом.

Пусть G =(V1,V2,E) – двудольный граф. Вершина u∈V1, множество вершин A⊆V1. Положим множество S(u) = {v∈V2: v смежно u}, S(A) = ∪u∈AS(u)

Теорема Холла: Пусть G=(V1,V2,E) – двудольный граф, тогда граф G имеет совершенное паросочетание ⇔ ∀A ⊆ V1: (|A| ≤ |S(A)|)


Оставить комментарий





Статистика

Рейтинг@Mail.ru