Определение: Система различных представителей для семейтсва конечных множеств S = {A₁, A₂,..,A_i,…,A_m} есть система попарно различных элементов {a₁, a₂,…, a_i,…, a_m}, для которых a_i ∈ A_i [i=1,2…m].

По семейству множеств S построим двудольный граф G = (V1,V2,E), положив V1 = S = {A₁, A₂,..,A_i,…,A_m} V2 = ∪_i=1..mA_i ={a₁,…,a_r}. Ребро е=(A_i, a_j)∈E ⇔ a_j∈A_i. Семейство множеств 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)|)

Комментарии запрещены.