3. Барашев В.П., Унучек С.А. Дискретная математика
.pdf
|
v0 v1 v2 |
v3 |
|
v4 v5 v6 v7 v8 v9 |
||||||||||
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ |
||||||||||||||
|
0 |
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
− |
3 |
1 |
2 |
∞ ∞ ∞ ∞ ∞ ∞ |
|||||||||
|
− |
3 |
− |
2 |
3 |
4 |
5 |
∞ ∞ ∞ |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
− |
|
3 |
− |
− |
3 |
4 |
5 |
∞ ∞ ∞ |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
− |
|
− |
− |
− |
|
3 |
4 |
5 |
∞ ∞ ∞ |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
− |
|
− |
− |
− |
|
− |
|
4 |
5 |
5 |
7 |
∞ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
− |
|
− |
− |
− |
|
− |
|
− |
5 |
5 |
7 |
∞ |
|
|
− |
|
− |
− |
− |
|
− |
|
− |
− |
|
5 |
7 |
9 |
−− − − − − − − 6 6
−− − − − − − − − 6
Вершины графа получают следующие метки: |
|
||||||||||||||||||
|
|
|
v1 |
3 |
|
4 3 v4 |
2 5 |
v7 |
|
|
|||||||||
|
|
|
|
l |
|
|
|
|
|
|
|
||||||||
|
|
|
|
2 |
@l |
|
|
l@ |
|
|
|
|
|||||||
|
|
|
|
|
s |
|
|
s |
@4 |
|
s |
@1 |
|
|
|||||
|
|
3 |
2 |
|
|
|
2 |
|
@ |
|
1 |
|
|
@ |
|
|
|||
|
|
|
v |
|
|
|
|
|
v |
|
@ |
@ |
v8 |
|
|
@ |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
||||||
0l@ |
1 |
|
2 |
@ |
|
3 |
4s |
|
5 |
5 |
|
|
|
3 |
|
6l |
|||
v0 s |
|
1 |
s |
|
|
|
|
|
6s |
|
|
|
|
sv9 |
|||||
|
|
@ |
l |
@ |
@4 |
l |
|
|
|
|
l |
|
|
|
|||||
|
|
@ |
2 |
|
2 |
|
3 |
|
|
|
|
|
|
||||||
|
|
2 |
@ |
|
|
|
@ |
|
|
|
4 |
|
|
|
|
|
|
||
|
|
|
v@3 |
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
2s |
|
5 |
5s |
v6 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
l |
|
|
l |
|
|
|
|
|
|
|
|
|||
Кратчайший путь равен: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
1 |
|
|
2 |
|
|
|
2 |
|
1 |
|
|
|
|
|
||
|
|
v0 → v2 |
→ v4 |
→ v7 |
→ v9. |
|
|
||||||||||||
Длина кратчайшего пути равна 9.
|
|
|
l |
|
l@ |
|
|
l |
|
|
|
|
|
||||||||
|
|
|
v13 |
|
4 |
|
3 |
v4 |
2 |
5 |
v7 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|||||
|
|
|
|
|
s |
|
2 |
s |
@4 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
s |
@1 |
|
|
|
||||||||||
v0 s |
3 |
2 |
|
|
|
2 |
s |
|
@ |
|
1 |
@ |
sv9 |
||||||||
|
1 s |
|
|
4 |
|
|
@ |
|
6s |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
v8 |
|
|
@ |
|
||||||
|
|
@ |
l |
@ |
|
l |
|
|
|
|
l |
|
|
|
|
||||||
|
|
v |
|
|
|
|
|
v |
|
|
@ |
|
|
|
|
|
@ |
|
|||
0l@ |
1 |
|
2 |
@ |
3 |
|
|
|
|
5 |
5 |
|
|
|
3 |
|
|
6l |
|||
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
@ |
2 |
|
@4 |
|
2 |
|
3 |
|
|
|
|
|
|
|
|||||
|
|
2 |
@ |
|
l |
@ |
|
|
|
4 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
@ |
l |
|
|
|
|
|
|
|
|
|
||||
|
|
|
v@3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
2s |
|
5 |
|
5s |
v6 |
|
|
|
|
|
|
|
|
|
|||
211
Пример 11.4. Найти кратчайший путь из вершины v0 в вершину v8 в графе, заданном списком взвешенных ребер:
{({v0, v1}, 10), ({v0, v4}, 5), ({v0, v2}, 8), ({v1, v3}, 3), ({v1, v6}, 6), ({v1, v4}, 3), ({v2, v4}, 1), ({v2, v7}, 10), ({v2, v5}, 1), ({v3, v6}, 1), ({v4, v6}, 12), ({v4, v8}, 10), ({v4, v7}, 9), ({v5, v7}, 7), ({v6, v8}, 2), ({v7, v8}, 1)}.
Решение.
Несмотря на то, что графы принято изображать, располагая вершины по кругу, мы воспользуемся более удобным способом. Очевидно, что в списке смежные ребра указаны рядом. Поэтому целесообразно изобразить граф на рисунке, размещая смежные вершины рядом:
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|
|
@s |
@ |
|
|
|
|
|
|
|
v1 |
3 |
|
1 |
|
|
|
|
||
|
|
|
|
6 |
@ v6 |
|
|
||||
|
|
|
|
|
|
|
@ |
|
|
|
|
|
10 @s |
@ |
3 |
|
@s |
@2 |
|
||||
|
|
|
|
|
12 |
|
|
|
|
||
|
|
|
|
|
@ v4 |
|
|
|
@ |
|
|
|
|
|
|
|
|
@ |
|
|
|
@ |
|
v0 |
s@@ |
5 |
|
@s |
@ |
10 |
|
sv8 |
|||
8@ |
|
|
1 |
|
9 |
|
|
1 |
|||
@ |
|
|
|
10 |
@ |
@ |
|
||||
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
vs2 @ |
|
|
vs7 |
|
|
||||
|
|
|
|
1@@s 7 |
|
|
|
|
|||
|
|
|
|
|
|
v5 |
|
|
|
|
|
Список значений меток вершин данного графа приведен в таблице:
|
v0 |
|
v1 |
|
v2 |
|
v3 |
|
v4 |
v5 |
|
v6 |
|
v7 |
v8 |
|||||||
∞ |
|
∞ |
|
∞ |
|
∞ |
∞ |
∞ |
|
∞ |
|
∞ |
∞ |
|||||||||
|
0 |
|
|
∞ |
|
∞ |
|
∞ |
∞ |
∞ |
|
∞ |
|
∞ |
∞ |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
− |
10 |
|
8 |
|
|
∞ |
|
5 |
|
∞ |
|
∞ |
|
∞ |
∞ |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
− |
8 |
|
|
6 |
|
|
∞ |
|
− |
∞ |
17 |
|
14 |
|
15 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
− |
8 |
|
|
− |
|
∞ |
|
− |
7 |
17 |
|
14 |
|
15 |
|||||||
|
− |
|
8 |
|
|
− |
|
∞ |
|
− |
− |
17 |
|
14 |
|
15 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
− |
|
− |
|
− |
|
11 |
− |
|
− |
|
14 |
|
14 |
|
15 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
− |
|
− |
|
− |
|
− |
|
− |
− |
|
12 |
|
14 |
|
15 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
− |
|
− |
|
− |
|
− |
|
− |
− |
|
− |
|
14 |
|
14 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
− |
|
− |
|
− |
|
− |
|
− |
− |
|
− |
|
− |
14 |
|||||||
212
Длина кратчайшего пути равна 14.
Сам путь найдем, используя обратный ход алгоритма Дейкстры:
|
|
5 |
3 |
|
|
|
3 |
|
|
1 |
|
|
2 |
|
||
v0 → v4 |
→ v1 |
→ v3 → v6 |
→ v8. |
|||||||||||||
|
|
|
|
|
|
|
@l |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
v3 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
|
|
l |
3 s@1 |
|
l |
|
|
|||||||||
|
|
|
|
s |
|
|
|
@ |
|
s |
|
|
|
|||
|
|
|
8 |
6 |
12 |
|
|
|||||||||
|
|
v1 |
|
|
|
|
|
@ |
v6 |
|
|
|||||
|
|
@ |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
12 |
@ |
|
|
|||||||
|
|
10 |
|
|
@3 |
|
|
|
@2 |
|
||||||
|
|
|
5 |
|
@ v4 |
|
|
|
|
@ |
|
|||||
0l@ |
|
|
|
@ |
|
|
10 |
14l |
||||||||
|
|
|
|
|
|
@ |
|
|
|
|
|
|
@ |
|
||
v0 |
s |
@ |
|
|
|
|
|
5s |
@ |
|
|
|
|
|
sv8 |
|
|
|
8 |
|
|
|
1 |
|
l 9 |
|
|
|
1 |
|
|||
|
|
@@ |
10 |
|
@@ |
|
|
|||||||||
|
|
|
|
l1 |
@ |
|
|
|
7 |
|
l |
|
|
|||
|
|
v2 |
6s@@ |
|
|
|
|
14sv7 |
|
|
||||||
@sl
v57
11.3Задачи для самостоятельного решения
1. Найти кратчайший путь, соединяющий вершины v0 и v8 в графе, заданном списком взвешенных ребер.
1.({v0, v1}, 6), ({v0, v4}, 10), ({v0, v2}, 14), ({v1, v3}, 8), ({v1, v6}, 10), ({v1, v4}, 2), ({v2, v4}, 4), ({v2, v7}, 4), ({v2, v5}, 4), ({v3, v6}, 4), ({v4, v6}, 8), ({v4, v8}, 12), ({v4, v7}, 10), ({v5, v7}, 2), ({v6, v8}, 4), ({v7, v8}, 1);
2.({v0, v1}, 5), ({v0, v4}, 22), ({v0, v2}, 4), ({v1, v3}, 3), ({v1, v6}, 6), ({v1, v4}, 9), ({v2, v4}, 16), ({v2, v7}, 15), ({v2, v5}, 9), ({v3, v6}, 2), ({v4, v6}, 3), ({v4, v8}, 4), ({v4, v7}, 6), ({v5, v7}, 7), ({v6, v8}, 11), ({v7, v8}, 3);
3.({v0, v1}, 2), ({v0, v4}, 6), ({v0, v2}, 8), ({v1, v3}, 8), ({v1, v6}, 14), ({v1, v4}, 2), ({v2, v4}, 2), ({v2, v7}, 10), ({v2, v5}, 4), ({v3, v6}, 5), ({v4, v6}, 12), ({v4, v8}, 18), ({v4, v7}, 12), ({v5, v7}, 4), ({v6, v8}, 6), ({v7, v8}, 6).
213
2. Найти кратчайший путь от вершины v0 до вершины v13 в графе G1, заданном списком ребер.
1.({v0, v1}, 3), ({v0, v4}, 6), ({v0, v2}, 2), ({v1, v3}, 2), ({v1, v6}, 9), ({v1, v4}, 2), ({v2, v4}, 4), ({v2, v7}, 8), ({v2, v5}, 1), ({v3, v8}, 5), ({v3, v6}, 6), ({v4, v6}, 6), ({v4, v9}, 8), ({v6, v7}, 5), ({v4, v7}, 4), ({v5, v7}, 7), ({v5, v10}, 8), ({v6, v8}, 2), ({v6, v11}, 4), ({v6, v9}, 3), ({v7, v9}, 4), ({v7, v12}, 5), ({v7, v10}, 1), ({v8, v11}, 4),
({v9, v11}, 1), ({v9, v13}, 3), ({v9, v12}, 1), ({v10, v12}, 3), ({v11, v13}, 2), ({v12, v13}, 2);
2.({v0, v1}, 1), ({v0, v4}, 2), ({v0, v2}, 3), ({v1, v3}, 9), ({v1, v6}, 8), ({v1, v4}, 2), ({v2, v4}, 1), ({v2, v7}, 5), ({v2, v5}, 2), ({v3, v8}, 2), ({v3, v6}, 1), ({v4, v6}, 7), ({v4, v9}, 2), ({v6, v7}, 2), ({v4, v7}, 5), ({v5, v7}, 1), ({v5, v10}, 1), ({v6, v8}, 4), ({v6, v11}, 7), ({v6, v9}, 5), ({v7, v9}, 3), ({v7, v12}, 5), ({v7, v10}, 2), ({v8, v11}, 3),
({v9, v11}, 11), ({v9, v13}, 13), ({v9, v12}, 7), ({v10, v12}, 5), ({v11, v13}, 2), ({v12, v13}, 6);
3.({v0, v1}, 5), ({v0, v4}, 2), ({v0, v2}, 3), ({v1, v3}, 3), ({v1, v6}, 3), ({v1, v4}, 2), ({v2, v4}, 2), ({v2, v7}, 10), ({v2, v5}, 1), ({v3, v8}, 2), ({v3, v6}, 1), ({v4, v6}, 6), ({v4, v9}, 9), ({v6, v7}, 6), ({v4, v7}, 11), ({v5, v7}, 9), ({v5, v10}, 5), ({v6, v8}, 2), ({v6, v11}, 1), ({v6, v9}, 4), ({v7, v9}, 2), ({v7, v12}, 3), ({v7, v10}, 4), ({v8, v11}, 1),
({v9, v11}, 2), ({v9, v13}, 9), ({v9, v12}, 6), ({v10, v12}, 7), ({v11, v13}, 11), ({v12, v13}, 3).
Ответы к задачам для самостоятельного решения
1.
1.lmin = 17; v0→v1→v4→v2→v7→v8;
2.lmin = 17; v0→v1→v3→v6→v4→v8;
3.lmin = 20; v0→v1→v4→v2→v5→v7→v8;
2.
1.lmin = 15; v0→v1→v4→v7→v10→v12→v13;
2.lmin = 16; v0→v2→v5→v7→v6→v3→v8→v11→v13;
3.lmin = 18; v0→v4→v1→v6→v11→v9→v7→v12→v13.
214
Глава 12
Задача об оптимальном назначении
12.1Паросочетания
Напомним, что двудольным называется граф, множество вершин которого можно разбить на два непересекающихся подмножества V и W ( на две доли) и при этом каждое ребро графа соединяет какую-либо вершину из V с какой-либо вершиной из W , но никакие две вершины из одного множества не являются смежными.
Двудольный граф, множество вершин которого распадается на два подмножества V и W , обычно обозначается G =< (V, W ), E >.
Определение 12.1. Паросочетанием в двудольном графе G называется подмножество попарно несмежных ребер графа.
Вспомним, что ребра в двудольном графе G =< (V, W ), E > соединяют вершины из доли V с вершинами доли W .
Пример 12.1.
Двудольный граф G задан графически:
v1 sHHHH sw1 |
|||
v2 |
H |
HH w2 |
|
|
s HHH s |
||
v3 |
s |
HH |
sw3 |
v4 |
s |
|
sw4 |
v1 |
s |
|
sw1 |
v2 |
s |
sw2 |
|
v3 |
s |
|
sw3 |
v4 |
s |
|
sw4 |
G |
П1 |
v1 s v2 s v3 s v4 s
sw1 sw2 sw3 sw4
П2
215
П1, П2 и П3 - паросочетания в графе G. |
|
|
|
|
||||||||
v1 s |
sw1 |
v1 |
s |
|
|
|
sw1 |
v1 |
s |
|
sw1 |
|
s HH |
s |
|
s |
|
|
s |
|
s |
|
s |
||
v2 HH |
w2 |
v2 |
|
|
|
|
w2 |
v2 |
|
|
w2 |
|
v3 s |
HHsw3 |
v3 s |
|
|
|
sw3 |
v3 s |
sw3 |
||||
v4 s |
|
sw4 |
v4 |
s |
|
|
|
sw4 |
v4 s |
|
sw4 |
|
|
П3 |
|
|
|
|
П4 |
|
|
П5 |
|||
Граф П4 не является паросочетанием в данном графе, так как ребра {v1, w1} и {v3, w1} смежны.
П5 также не является паросочетанием в G, так как ребра {v4, w3} в графе G нет.
Определение 12.2. Паросочетание П в двудольном графе G называется полным, если к нему нельзя добавить ни одного ребра, несмежного с ребрами паросочетания.
Определение 12.3. Паросочетание П в двудольном графе G называется максимальным, если никакое другое паросочетание в G не содержит ребер больше, чем П.
Определение 12.4. Пусть G =< (V, W ), E > - двудольный граф, множество вершин которого можно разбить на две доли V и W . Паросочетание П в графе G называется совершенным, если для всякой вершины из V найдется инцидентное ей ребро, то есть |П| = |V |.
Максимальное парасочетание всегда полное. Обратное неверно. Совершенное парасочетание всегда максимальное. Обратное
неверно.
Пример 12.2.
Паросочетание П2 в графе G из предыдущего примера является полным, максимальным и совершенным.
Паросочетание П3 является полным, при этом ни максимальным, ни
216
совершенным не является.
Паросочетание П1 не является ни полным, ни максимальным, ни совершенным.
Пример 12.3.
v1 sHHH sw1 v2 s HHHsw2 HHH
v3 s HHHsw3
G
v1 sHHH sw1 |
v1 s |
sw1 |
|
v2 s HHHsw2 |
v2 s sw2 |
||
v3 s |
sw3 |
v3 s |
sw3 |
|
П1 |
|
П2 |
П1 и П2 являются максимальными паросочетаниями, но не являются совершенными, так как |П| = 2 (в паросочетание входят 2 ребра), а |V | = 3 (левая доля графа состоит из 3 вершин).
12.2Венгерский алгоритм
12.2.1Постановка задачи
Задача 12.1. Пусть имеется n работников и m работ. Известно, какие работы может выполнять каждый из рабочих. Требуется распределить работу между работниками так, чтобы наибольшее количество людей получило работу, которую они могут выполнять. Все ли работники получат работу?
Решим эту задачу при помощи графов. Работникам соответствуют вершины vi двудольного графа G =< (V, W ), E > (vi V ); работам - вершины wj (wj W ).
Если i-тый рабочий выполняет j-тую работу, то в графе существует ребро {vi, wj}. Если i-тый рабочий не может выполнять j-тую работу, то ребра {vi, wj} в графе нет .
Таким образом, на языке графов задача формулируется следующим образом: найти максимальное паросочетание в двудольном графе. Существует ли в графе совершенное сочетание?
Решение этой задачи удобно находить, используя алгоритм отыскания максимального паросочетания, так называемый
217
венгерский алгоритм, названный так в честь Гарольда Куна, впервые предложившего данный алгоритм.
Ответ на вопрос о существовании совершенного паросочетания дает нам теорема Ф.Холла.
12.2.2Основные определения. Теорема Холла
Определение 12.5. Ребра, вошедшие в полное паросочетание, называются толстыми, а не вошедшие - тонкими.
Определение 12.6. Вершины, инцидентные толстым ребрам, называются насыщенными. Остальные вершины графа G называются
ненасыщенными.
Определение 12.7. Цепь в двудольном графе называется чередующейся, если она последовательно соединяет тонкие и толстые ребра.
Определение 12.8. Чередующаяся цепь называется тонкой, если она соединяет две ненасыщенные вершины.
Очевидно, что тонкая цепь начинается и заканчивается тонким ребром. Это значит, что число тонких ребер в тонкой цепи на единицу больше, чем толстых.
Определение 12.9. Пусть S V - подмножество вершин V графа G =< (V, W ), E >. Окружением множества S называется множество φ(S) = φ(v)\S, где φ(v) - множество вершин, смежных с вер-
v S
шиной v.
То есть, окружением множества S является подмножество вершин из W , каждая из которых смежна хотя бы с одной вершиной из S.
Теорема 12.1 (Ф. Холл). Совершенное паросочетание в двудольном графе G =< (V, W ), E > существует тогда, и только тогда, когдаS V выполнено неравенство: |φ(S)| > |S|, то есть тогда, когда число вершин во множестве S не превосходит количества смежных с ней вершин.
218
12.2.3Алгоритм отыскания максимального паросочетания в двудольном графе(венгерский алгоритм)
1.Просматривая в произвольном порядке ребра двудольного графа G, включаем в паросочетание П первое по порядку ребро; затем те ребра, которые не смежны ни с одним из уже включенных в паросочетание. Так действуем до тех пор, пока не получим полное паросочетание.
2.Для найденного полного паросочетания ищем тонкую цепь. Если её нет, то полное паросочетание является максимальным. Алгоритм завершает работу.
3.Если тонкая цепь существует, из полного паросочетания исключаем те толстые ребра, которые вошли в тонкую цепь. При этом включаем в паросочетание все тонкие ребра найденной цепи. Так как количество тонких ребер в цепи на 1 больше числа толстых ребер, то мощность паросочетания (количество ребер в П ) увеличится на 1.
Переходим к пункту 2 (опять ищем тонкую цепь).
Пример 12.4. Найти максимальное паросочетание в графе G:
v |
|
H |
|
|
w |
|
1 |
sJ HH s 1 |
|||
|
|
J H |
Hsw2 |
||
|
|
|
H |
||
v2 s JJ |
|
||||
|
|
JJ |
|
|
|
v3 |
s@@ JJ |
sw3 |
|||
v4 s @@ |
|
Jsw4 |
|||
|
|
|
@@sw5 |
||
G
Решение.
1.Найдем полное паросочетание в графе G. Для этого построим паросочетание, в которое войдут все вершины исходного графа G.
219
v1 s v2 s v3 s v4 s
П1
2.
sw1 sw2 sw3 sw4 sw5
Включим в П1 ребро {v1, w1} (первое из ребер, изображенных на рисунке).
Ребра {v1, w2}, {v1, w4}, {v2, w1} и {v3, w1}, следующие сверху вниз за ребром {v1, w1} при изображении графа, включать в паросочетание нельзя, так как они смежны с уже включенным в паросочетание ребром.
Включим в П1 ребро {v3, w3}, так как оно не смежно с ребром {v1, w1}.
Все остальные ребра смежны с ребрами из П1. Значит, П1 = {{v1, w1}, {v3, w3}} - полное паросочетание.
v |
1 |
H |
|
|
w |
|
sJ HH s 1 |
||||
|
|
J H |
Hsw2 |
||
|
|
|
H |
||
v2 s JJ |
|
||||
|
|
JJ |
|
|
|
v3 |
s@@ JJ |
sw3 |
|||
v4 s @@ |
|
Jsw4 |
|||
|
|
|
@@sw5 |
||
Ребра {v1, w1} и {v3, w3} - толстые ребра графа G, все остальные - тонкие.
Попробуем найти тонкую цепь. Вершины v2, w2, v4, w4 и w5 - ненасыщенные вершины. Тонкой цепью, соединяющей вершины v2 и w2, является последовательность ребер
v2 7→w1 7→v1 7→w2.
При этом ребра {v2, w1} и {v1, w2} - тонкие,
Gребро {v1, w1} - толстое.
3.Исключим из П1 толстое ребро {v1, w1}, включим 2 тонких ребра
{v2, w1} и {v1, w2}.
Паросочетание П2 = {{v1, w2}, {v2, w1}, {v3, w3}} - полное.
|П2| = 3 = |П1| + 1.
220