X1 y1 Шаг 4.

P₄ = {( x₁ , y₁), ( x₂ , y₅),( x₃ , y₆), ( x₄ , y₃)}.

μ₄ = [x₅ , y₁ , x₁ , y₄]

y₂ 0 1 0

x₂ 1 0 1

Удаляем из P₄ ребро ( x₁ , y₁) и добавляем

y₃ вместо него ребра ( x₅ , y₁),( x₁ , y₄) (Рис. 6).

x₃

y₄

x₄

y₅

x₅

y₆

Рис. 5.

x₁ y₁

y₂

x₂

y₃

x₃

y₄

x₄

y₅

x₅

y₆

Рис. 6.

Шаг 5. P₅ = {( x₁ , y₄), ( x₂ , y₅),( x₃ , y₆), ( x₄ , y₃), ( x₅ , y₁)} (Рис. 6). P₅ − есть искомое совершенное паросочетание для исходного графа (Рис. 7).

x₁ y₄

x₂ y₅

x₃ y₆

x₄ y₃

x₅ y₁

Рис. 7.

Ответ: P₅ − есть искомое совершенное паросочетание для исходного графа.

Задача 8.21

Для указанных множеств найти систему различных представителей.

А₁ = {2, 4, 5}, А₂ = {2, 5, 6}, А₃ = {2, 4, 6}, А₄ = {1, 3, 5}, А₅ = {1, 4, 5}.

Решение:

6

Пусть множества вершин U = {А₁ , А₂ , А₃ , А₄ , А₅}, V = А_i ={1, 2, 3, 4, 5, 6}.

^{i = 1}

Множество Е ребер таково, что (А_i , j)Е ↔ j А_i . Тогда

Е = {(А₁ , 2), (А₁ , 4), (А₁ , 5), (А₂ , 2), (А₂ , 5), (А₂ , 6), (А₃ , 2), (А₃ , 4), (А₃ , 6),

(А₄ , 1), (А₄ , 3), (А₄ , 5), (А₅ , 1), (А₅ , 4), (А₅ , 5)}.

A₁ 1

2

A₂

3

A₃

4

A₄

5

A₅

6

Рис. 1.

A₁ 1 Шаг 1. Выбираем исходное паросочетание

P₁ = {(A₁ , 2)}. P₁ – увеличитель

(чередующаяся цепь) (Рис. 2).

2 μ₁ = [А₂ , 2, А₁ , 4]

A₂ 0 1 0

1 0 1

3

A₃ Единственная единица в первой строке

из нулей и единиц означает, что

4 соответствующее этой единицы ребро

A₄ (А₁ , 2) лежит в P₁ . Убираем это ребро

из P₁ , а вместо него добавляем два ребра

5 (А₁ , 4), (А₂ , 2) соответствующие двум

A₅ единицам второй строки из нулей и

единиц. В результате получим следующее

6 паросочетание P₂ , число ребер в котором

Рис. 2. на одно больше, чем в P₁ (Рис. 3).

A₁ 1 Шаг 2. Выбираем исходное паросочетание

P₂ = {(А₁ , 4), (А₂ , 2)}. (Рис. 3).

2 μ₂ = [А₃ , 2, А₂ , 5]

A₂ 0 1 0

1 0 1

3

A₃ Единственная единица в первой строке

из нулей и единиц означает, что

4 соответствующее этой единицы ребро

A₄ (А₂ , 2) лежит в P₂ . Убираем это ребро

из P₂ , а вместо него добавляем два ребра

5 (А₃ , 2), (А₂ , 5) соответствующие двум

A₅ единицам второй строки из нулей и

единиц. В результате получим следующее

6 паросочетание P₃ , число ребер в котором

Рис. 3. на одно больше, чем в P₂ (Рис. 4).

A₁ 1 Шаг 3. Выбираем исходное паросочетание

P₃ = {(А₁ , 4),(А₂ , 5),(А₃ , 2)}.(Рис. 4).

2 μ₃ = [А₄ , 3]

A₂ 0

1

3 Добавляем в P₃ ребро (А₄ , 3) (Рис. 5).

A₃

4

A₄

5

A₅

6

Рис. 4.

A₁ 1 Шаг 4. Выбираем исходное паросочетание

P₄ = {(А₁ , 4),(А₂ , 5),(А₃ , 2),(А₄ , 3)}.(Рис. 5).

2 μ₄ = [А₅ , 4, А₁ , 5, А₂ , 6]

A₂ 0 1 0 1 0

1 0 1 0 1

3 Удаляем из P₄ ребра (А₁ , 4), (А₂ , 5) и

A₃ добавляем вместо него ребра (А₅ , 4),

(А₁ , 5), (А₂ , 6) (Рис. 6).

4

A₄

5

A₅

6

Рис. 5.

A₁ 1

2

A₂

3

A₃

4

A₄

5

A₅

6

Рис. 6.

Шаг 5. P₅ = {(А₁ , 5),(А₂ , 6),(А₃ , 2),(А₄ , 3), (А₅ , 4)}.(Рис. 6). P₅ − есть совершенное паросочетание для двудольного графа G = (U, V, E) (Рис. 7).

А₁ 5

А₂ 6

А₃ 2

А₄ 3

А₅ 4

Рис. 7.

Система различных представителей:

5 А₁ = {2, 4, 5}, 6 А₂ = {2, 5, 6},2 А₃ = {2, 4, 6},3 А₄ = {1, 3, 5},

4 А₅ = {1, 4, 5}.

Ответ: P₅ − есть совершенное паросочетание для исходного графа. Система

различных представителей: 5 А₁ = {2, 4, 5}, 6 А₂ = {2, 5, 6},2

А₃ = {2, 4, 6},3 А₄ = {1, 3, 5}, 4 А₅ = {1, 4, 5}.

Задача 9.21

Построить наибольшее по весу совершенное паросочетание в полном двудольном графе G = (V₁ , V₂ , E), V₁ = { x₁ , x₂ , x₃ , x₄ }, V₂ = { y₁ , y₂ , y₃ , y₄ },

E = {e_ij = (x_i , y_j )} : i = 1, 2, 3, 4; j = 1, 2, 3, 4. С весами ребер, заданными 4 х 4 – матрице W = [w_ij], где вес w_ij ребра e_ij = (x_i , y_j ) равен N(i² + j²) + i² + j² + i + j по модулю (остаток от деления w_ij на 10). N – есть номер варианта.