图4-3
第3步 选择空匹配点Bob,建立第2条增广路径Bob-->Carol, 并进行置换,创建第2个匹配:红色标记Bob--->Carol。如图4-4所示。
图4-4
第4步,选择空匹配点Christ,建立增广路径Christ--->Alice--->Al--->Beatrice
(增广路径满足:头部Christ、尾部Beatrice都是非匹配点, 中间Alice、Al都是匹配点;蓝色标记Christ--->Alice是非匹配边,红色标记Alice--->Al是匹配边,蓝色标记Al--->Beatrice是非匹配边)。如图4-5所示。
图4-5
第5步,置换增广路径中的匹配边和非匹配边。建立新的匹配:Christ--->Alice--->Al--->Beatrice
(红色标记Christ--->Alice是匹配边,Alice--->Al是非匹配边,红色标记Al--->Beatrice是匹配边)。如图4-6所示。
图4-6
第6步,选择空匹配点Dan,建立增广路径Dan--->Carol--->Bob--->Danielle
(增广路径满足:头部Dan、尾部Danielle都是非匹配点, 中间Carol、Bob都是匹配点;蓝色标记Dan--->Carol是非匹配边,红色标记Carol--->Bob是匹配边,蓝色标记Bob--->Danielle是非匹配边)。如图4-7所示。