离散2-15-偶图与匹配

主要内容偶图基本概念判别定理匹配最大匹配判别求最大匹配算法1-吴扬扬-§11.5偶图与匹配

1.偶图(1)定义:设无向图G=<V,E>,若V可划分成子集V1和V2(V1

V2=,V1

V2=V),并且G的任何一条边的两个端点，一个属于V1,另一个属于V2,则称G为偶图或二分图，记为G=<V1,V2,E>。若

u∈V1,

v∈V2有且仅有一条边相关联，则称G为完全偶图，若

V1

=n,V2=m,则完全偶图G记为Kn,m.例1：下列图中哪些是偶图？哪些是完全偶图？K2,3K3,3判别»K3,32-吴扬扬-§11.5偶图与匹配

1.偶图(2)定理11.5.1：图G为偶图iffG中没有奇数长度的回路。证明:(必要性)设G=<V1,V2,E>是偶图，C:v0v1…vkv0是一条回路，不妨设v0

V1，则v2i+1

V2(i≥0),∴k=2t+1(t≥0且tI)。∴C长度为2t+2。因此，G中没有奇数长度的回路。(充分性)设G连通(否则对G的每个连通分支进行证明),任取v0

V，令V1={v|d(v0,v)为偶数v

V}，V2=V-V1，则V1

V2=

V1

V2=V.

(ui,uj)E，若ui,ujV1，由V1的定义知必存在长为偶数的通路：L1:v0v1…v2k+1ui，L2:v0v’1…v’2t+1uj，则下列回路长为奇数：v0v1,…v2k+1uiujv’2t+1…v’1v0,矛盾。∴ui和uj不同属于V1。同理可证ui,uj也不同属V2。所以,G为偶图。«例13-吴扬扬-§11.5偶图与匹配

2.匹配(1)定义：设G=<V1,V2,E>是偶图，M

E,若M中任意两条边均无公共端点,则称M为G的一个匹配；边数最多的匹配称为最大匹配,最大匹配的边数称为G的匹配数；若M为G的最大匹配,且

M

=min{V1

,V2

},则称M为G的完备匹配；如果

V1

=

V2

,则称M为G的完美匹配.例2：求下列图的匹配、最大匹配、完备匹配和完美匹配。应用实例:pp.244例11.5.34-吴扬扬-§11.5偶图与匹配

2.匹配(2)定义:设M是G=<V1,V2,E>的一个匹配,若存在一条由E-M和M的边交替构成的基本通路,并且其起点和终点都不是M的边的端点，则称该通路是G关于M的交替链。例3：x1x2x3x4y1y2y3y4y5M={(x1,y5),(x3,y1),(x4,y3)}x2y1x3y4为

G关于M的一条交替链。还有其他关于M的交替链吗？定理11.5.2偶图G的一个匹配M是最大匹配iffG不含关于M的交替链。5-吴扬扬-§11.5偶图与匹配

2.匹配(3)求偶图G=<V1,V2,E>的最大匹配算法①M:=;②求一条G关于M的交替链；③若不存在G关于M的交替链，则输出M,结束;④设②所求的G关于M的交替链为v0v1…v2kv2k+1,置M:=M

{(v0,v1),(v2,v3),…(v2m,v2m+1)}-{(v1,v2),(v3,v4),…(v2m-1,v2m)},转②x1x2x3x4y1y2y3y4交替链匹配

x2y2{(x2,y2)}y1x2y2x3{(y1,x2),(y2,x3)}x4y4{(y1,x2),(y2