第9章 特殊图与应用

1、DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY第第9 9章章 特殊图与应用特殊图与应用第第1节节 欧拉图与哈密顿图欧拉图与哈密顿图第第2节节 平面图与欧拉公式平面图与欧拉公式第第3节节 二二部图与匹配部图与匹配第第4节节 对偶图与着色对偶图与着色第第5节节 树树第第6节节 根树与应用根树与应用DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY第第1节节 欧拉图与哈密顿图欧拉图与哈密顿图一、欧拉图一、欧拉图二、哈密顿图二、哈密顿图DA

2、LIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY一、欧拉图一、欧拉图1、欧拉路径、欧拉路径2、欧拉回路、欧拉回路3、欧拉图、欧拉图4、有向欧拉图、有向欧拉图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY欧拉图的起源欧拉图的起源哥尼斯堡七桥问题哥尼斯堡七桥问题ABCDDALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY欧拉图欧拉图G: 是连通无向图是连通无向图

3、经过图中每条边一次且仅一次的路径经过图中每条边一次且仅一次的路径欧拉路径欧拉路径:欧拉回路欧拉回路: :经过图中每条边一次且仅一次的回路经过图中每条边一次且仅一次的回路具有欧拉回路的图叫欧拉图。具有欧拉回路的图叫欧拉图。欧拉图欧拉图: :DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY欧拉图举例欧拉图举例判断图判断图G1和和G2是否是欧拉图？是否是欧拉图？DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答G1：欧拉回路欧拉回路

4、1234563726781欧拉图欧拉图G2：125462341欧拉回路欧拉回路欧拉图欧拉图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理无向连通图无向连通图G G是欧拉图是欧拉图G中每个结点的度均为偶数中每个结点的度均为偶数(偶结点偶结点)DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY哥尼斯堡七桥问题哥尼斯堡七桥问题deg(A)=deg(B)=deg(D)=3，deg(C)=5哥尼斯堡七桥问题哥尼斯堡七桥问题无解。无解。

5、DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY欧拉图应用举例欧拉图应用举例环卫工人清扫街道，清扫路线如图所示，试环卫工人清扫街道，清扫路线如图所示，试问是否存在清扫路线：问是否存在清扫路线：使环卫工人从使环卫工人从V1出发通过出发通过所有路线而不重复且最后所有路线而不重复且最后回到回到V1。 DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答由于图中每个结点度均为偶数，故由定理可知这样的一由于图中每个结点度均为偶数，故由定理

6、可知这样的一条清扫路线是存在的。条清扫路线是存在的。 (v1, v5, v11, v7, v12, v8, v10, v6, v9, v11, v12, v10, v9, v5, v2, v6, v4, v8, v3, v7, v1)DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理无向连通图无向连通图G中结点中结点vi与与vj间存在间存在欧拉路径欧拉路径vi与与vj的度数均为奇数，的度数均为奇数，其它结点的度数均为偶数其它结点的度数均为偶数DALIAN MARITIME UNIVERSITY大大连连海海事

7、事大大学学 DALIAN MARITIME UNIVERSITY定理应用举例定理应用举例一笔画问题：一笔画问题：判别图判别图(1)、(2)是否可以一笔画。是否可以一笔画。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答图图(1)A、B为奇结点为奇结点C, D, E为偶结点为偶结点欧拉路径欧拉路径:AEDCBECABDALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答图图(2)A、B为奇结点为奇结点其余各点为偶结点其余各点

8、为偶结点A与与B两点间存在欧拉路径，即两点间存在欧拉路径，即从从A到到B可以一笔画。可以一笔画。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理应用举例定理应用举例判断图（判断图（3）是否可以一笔画）是否可以一笔画 。A,B,C,D均为奇结点均为奇结点图图(3)中无欧拉路径，中无欧拉路径，因此不可以一笔画。因此不可以一笔画。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY4 4、有向、有向欧拉图欧拉图G:有向图有向图经过图中每条

9、边一次且仅一次的经过图中每条边一次且仅一次的有向路径有向路径有向欧拉路径有向欧拉路径:有向欧拉回路有向欧拉回路:经过图中每条边一次且仅一次的经过图中每条边一次且仅一次的有向回路有向回路有向欧拉图有向欧拉图:具有具有有向欧拉回路有向欧拉回路的有向图的有向图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理一个连通有向图一个连通有向图G是有向欧拉图是有向欧拉图对对G中的所有结点中的所有结点v, 有：有：d +(v) = d-(v)DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DA

10、LIAN MARITIME UNIVERSITY有向欧拉图举例有向欧拉图举例判断图判断图G1和和G2是否为有向欧拉图，如果是，请给出有是否为有向欧拉图，如果是，请给出有向欧拉回路。向欧拉回路。图图G1图图G2DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答d+(v1)=d-(v1)=1d+(v2)=d-(v2)=2d+(v3)=d-(v3)=1d+(v4)=d-(v4)=2d+(v5)=d-(v5)=2具有具有有向欧拉图有向欧拉图有向欧拉回路有向欧拉回路:v1e1v2e3v4e7v5e5v1e6v4e8v

11、5e4v3e2v1DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答d+(v4)=1 d-(v4)=3d+(v5)=3 d-(v5)=1不具有有向欧拉图不具有有向欧拉图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理G:连通有向图，连通有向图，G中两个结点中两个结点vi和和vjvi的出度比入度大的出度比入度大1vj的出度比入度小的出度比入度小1其它结点的出度和入度相等其它结点的出度和入度相等G中存在从中存在从vi到到v

12、j的有向欧拉路径的有向欧拉路径DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY二、哈密顿图二、哈密顿图1、哈密顿图的起源、哈密顿图的起源2、哈密顿图、哈密顿图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY1 1、哈密顿图的起源哈密顿图的起源 周游世界游戏：周游世界游戏：从某个城市出发，经过每个城市一次且仅一从某个城市出发，经过每个城市一次且仅一次，最后回到出发点。次，最后回到出发点。DALIAN MARITIME UNIVERSI

13、TY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY2 2、哈密顿图、哈密顿图G:无向图无向图经过图中每个结点一次且仅一次的路径经过图中每个结点一次且仅一次的路径哈密顿路径哈密顿路径:哈密顿回路哈密顿回路:经过图中每个结点一次且仅一次的回路经过图中每个结点一次且仅一次的回路哈密顿图哈密顿图:有哈密顿回路的图有哈密顿回路的图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY哈密顿图举例哈密顿图举例判断图判断图G1和和G2是否为哈密顿图，如果是，请给出是否为哈密顿图，如果是，请给出哈密顿回

14、路。哈密顿回路。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答G1：1a2b3c4d5e1哈密顿回路哈密顿回路G2：是哈密顿图是哈密顿图不是哈密顿图不是哈密顿图无哈密顿回路无哈密顿回路DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY判断哈密顿图的必要条件定理判断哈密顿图的必要条件定理G=是哈密顿图是哈密顿图W(V-S)|S|S: V中任意一个非空真子集中任意一个非空真子集V-S：从：从G中去掉中去掉S结点及所关联的边剩下的

15、图结点及所关联的边剩下的图W(V-S) ：V-S图的分支数图的分支数DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解释解释(1) 若若G是哈密顿图，则一定满足上式；是哈密顿图，则一定满足上式；(2) 满足上式却不一定是哈密顿图；满足上式却不一定是哈密顿图；(3) 不满足上式一定不是哈密顿图。不满足上式一定不是哈密顿图。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理应用举例定理应用举例利用定理说明下图不是哈密顿图。利用定理说明

16、下图不是哈密顿图。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答取取S=v1,v4，则：，则：|S|=2W(V-S)=3 不满足：不满足： W(V-S)|S|不是哈密顿图不是哈密顿图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY判断哈密顿图的充分条件定理判断哈密顿图的充分条件定理G=:具有具有n个结点的简单图个结点的简单图(1) 对每对结点对每对结点vi和和vj 有：有：d(vi)+d(vj) n-1G中存在一条哈密顿路

17、径中存在一条哈密顿路径(2)对每对结点对每对结点vi和和vj 有有: d(vi)+d(vj) nG是哈密顿图是哈密顿图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解释解释(1) 满足上式一定是哈密顿图；满足上式一定是哈密顿图；(2) 是哈密顿图不一定满足上式；是哈密顿图不一定满足上式；(3) 不是哈密顿图一定不满足上式。不是哈密顿图一定不满足上式。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理应用举例定理应用举例任意两点的

18、度之和为任意两点的度之和为4n=6不满足不满足d(vi) + d(vj) n但却是哈密顿图，但却是哈密顿图，也有哈密顿路径。也有哈密顿路径。是哈密顿图是哈密顿图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY第第2 2节节 平面图与欧拉公式平面图与欧拉公式1、平面图、平面图2、平面图的区、平面图的区(面面)3、相邻区、相邻区4、在、在2度结点内同构度结点内同构5、对偶图、对偶图6、自对偶图、自对偶图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNI

19、VERSITY1 1、平面图、平面图G=: 无向图无向图G的所有结点和边均能画在一个平面上的所有结点和边均能画在一个平面上,任意两条边除任意两条边除了端点外没有任何交叉。了端点外没有任何交叉。则称则称G为平面图；为平面图；如果无论怎让改画，也避免不了边与边的交叉，如果无论怎让改画，也避免不了边与边的交叉，则称则称G为非平面图为非平面图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY平面图举例平面图举例说明说明G1是平面图是平面图G2是非平面图。是非平面图。DALIAN MARITIME UNIVERSITY大大连

20、连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY2 2、平面图的区平面图的区（面）（面）G:连通的平面图。连通的平面图。(1) 由由图中的边所围成的空白区域，称为面（区图中的边所围成的空白区域，称为面（区/网孔）网孔）(2) 区区内区和外区（内区和外区（内区是有限区，外区为无限区内区是有限区，外区为无限区）(3) 围成一个区所含边的数目围成一个区所含边的数目称为区的长度称为区的长度DALIAN MARITIME UNIVERSITY大

21、大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY平面图的面举例平面图的面举例平面图平面图G1有有4个区：个区：R0, R1, R2, R3，R0是无限区是无限区(外区外区)平面图平面图G1有有5个区：个区：R0, R1, R2, R3, R4，R0是无限区是无限区(外区外区)DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY平面图的面举例平面图的面举例 同一图的不同画法，它的区也不同，但它们所含同一图的不同画法，它的区也不同，但它们所含区的个数是相同的。例如：区的个数是相同的。例如：G1

22、:R0是无限区是无限区R1, R2, R3是内区是内区G1:R3是无限区是无限区R1, R2, R0是内区是内区DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY3 3、相邻区、相邻区两个区的边界至少有一条公共边两个区的边界至少有一条公共边两个区是相邻的两个区是相邻的否则否则:两个区是不相邻的两个区是不相邻的DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY相邻区举例相邻区举例R0和和R1、R2、R3 、R4相邻区相邻区R1和和R0、R

23、3相邻区相邻区R2和和R0、R3相邻区相邻区DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理（欧拉公式）定理（欧拉公式）n m + f = 2G:连通的平面图连通的平面图n:结点数结点数m:边数边数f:面数面数(区数区数)欧拉公式欧拉公式DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY 证明证明(对边数对边数m进行归纳进行归纳)(1) 若若G的边数为的边数为0，因，因 G连通。所以连通。所以G只有只有 一个一个孤立结点孤立结点n

24、=1m=0f=1n m + f= 1-0+1=2(2) 若若G为一条边为一条边,因连通因连通,有两种情况。有两种情况。n=2m=1f=1n- m + f= 2-1+1 = 2n m + f = 2m=1n=1f=2n- m + f= 1-1+2 = 22)1)DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明（续）证明（续）(3)设设G有有mk条边时成立，即：条边时成立，即：n k-m k+ fk=2，证明证明G有有mk+1条边时亦成立：条边时亦成立：在具有在具有mk条边的连通图条边的连通图G上增加一条边，使它

25、仍为连上增加一条边，使它仍为连通图只有两种情况：通图只有两种情况：DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明（续）证明（续）增加一个新结点增加一个新结点v2v2与图与图G上的一个结点上的一个结点v1相连相连n= nk+1m= mk+1f = fkn-m+f = nk+ 1- ( mk+1) + fk= nk-mk+fk = 2DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明（续）证明（续） 用一条边连通图用一条边连通图

26、G中的两个已知结点中的两个已知结点v1和和v2n= nkm= mk+1f=fk +1n-m+f = nk- ( mk+1) +fk +1= nk-mk+fk = 2DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解释解释欧拉公式只适用于连通平面图欧拉公式只适用于连通平面图(是必要条件是必要条件)，即：，即：(1) 任何一个连通平面图都满足欧拉公式；任何一个连通平面图都满足欧拉公式；(2) 不满足欧拉公式的图一定不是平面图；不满足欧拉公式的图一定不是平面图；(3) 满足欧拉公式的图不一定是平面图。满足欧拉公式的图不

27、一定是平面图。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理(欧拉公式的推论欧拉公式的推论)设设G是一个简单连通平面图，则：是一个简单连通平面图，则：(1) 若每一个区至少由若每一个区至少由3条边围成，则条边围成，则: m3(n-2); (2) 若每一个区至少由若每一个区至少由4条边围成，则条边围成，则: m2(n-2);(3) 若每一个区至少由若每一个区至少由5条边围成，则条边围成，则: 3m5(n-2); (4) 若每一个区至少由若每一个区至少由6条边围成，则条边围成，则: 2m3(n-2); DA

28、LIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解释解释 此定理也是此定理也是必要条件必要条件；判断平面图的不等式要随着周界长度的改变，即随着判断平面图的不等式要随着周界长度的改变，即随着周界长度的不同，套用不同的不等式进行判断。周界长度的不同，套用不同的不等式进行判断。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY平面图的不等式举例平面图的不等式举例图图K3,3每个区至少由每个区至少由4条边围成条边围成m = 9n = 6K3,3是

29、非平面图是非平面图(2) 若每一个区至少由若每一个区至少由4条边围成，则条边围成，则: m2(n-2);9 8DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY平面图的不等式举例平面图的不等式举例图图K5每个区至少由每个区至少由3条边围成条边围成m = 10n = 5K5是非平面图是非平面图109(1) 若每一个区至少由若每一个区至少由3条边围成，则条边围成，则: m3(n-2);DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY4 4

30、、在、在2 2度结点内同构度结点内同构图图G1, G2G1和和G2同构同构或通过反复插入或除去度为或通过反复插入或除去度为2的结点的结点G1和和G2同构同构在在2度结点内同构度结点内同构DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY举例举例v上面两个图，在上面两个图，在2度结点内是同构的度结点内是同构的DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY库拉托夫斯基定理库拉托夫斯基定理一个图是平面图一个图是平面图它不包含与它不包含与k

31、3,3或或k5在在2度结点内同构的子图度结点内同构的子图k3,3和和 k5库拉托夫斯基图库拉托夫斯基图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY库拉托夫斯基定理的应用举例库拉托夫斯基定理的应用举例利用库拉托夫斯基定理证明利用库拉托夫斯基定理证明G是非平面图。是非平面图。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明证明(1)去掉边去掉边(v2,v3), (v3,v4), (v6,v7) 形成形成G的子图的子图G1;(2)

32、删除度为删除度为2的结点的结点v3形成形成G的子图的子图G2;(3)G2与与k3,3同构同构G中包含与中包含与k3,3在在2度结点内同构的子图度结点内同构的子图G是非平面图是非平面图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY库拉托夫斯基定理的应用举例库拉托夫斯基定理的应用举例利用库拉托夫斯基定理证明彼得森图是非平面图。利用库拉托夫斯基定理证明彼得森图是非平面图。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明证明(1) 去

33、掉结点去掉结点10及与及与10关联的边形成关联的边形成G的子图的子图G1(2) 删除度为删除度为2的结点的结点5、7、8形成形成G的子图的子图G2(3) G2与与k3,3同构同构彼得森图中包含与彼得森图中包含与k3,3在在2度结点内同构的子图度结点内同构的子图彼得森图是个非平面图彼得森图是个非平面图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY第第3 3节节 二部图与匹配二部图与匹配一、二部图一、二部图二、匹配二、匹配DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN M

34、ARITIME UNIVERSITY一、二部图一、二部图1 1、二部图的定义、二部图的定义2 2、完全二部图、完全二部图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY1 1、二部图的定义、二部图的定义G=:无向图无向图 V1, V2 :V的划分的划分使得使得Vi (i=1, 2)中任何两个结点都不邻接中任何两个结点都不邻接二部图二部图V1,V2:互补结点子集。互补结点子集。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY二部图举例

35、二部图举例工作分配问题：工作分配问题：4个待业人员个待业人员a1, a2, a3, a4a1a2a3a46项工作任务项工作任务p1, p2, p3, p4, p5, p6p2p3p4p5p1p6a1, a2, a4能胜任能胜任p2, p5a3能胜任能胜任p1, p2, p3, p4, p6V1V2DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY2 2、完全二部图、完全二部图V1, V2:简单二部图的互补结点子集简单二部图的互补结点子集V1中的每个结点与中的每个结点与V2中的每个结点邻接中的每个结点邻接G为完全二部

36、图为完全二部图|V1| = m|V2| = nKm, nDALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY完全二部图举例完全二部图举例DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY二、匹配二、匹配(略略)1、匹配、匹配2、极大匹配、极大匹配3、最大匹配、匹配数、最大匹配、匹配数4、完备匹配、完备匹配转到对偶图与着色转到对偶图与着色DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITI

37、ME UNIVERSITY1 1、匹配、匹配G=: 无向图无向图E EE 中任何两条边都不邻接中任何两条边都不邻接E 为为G中的匹配中的匹配DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY2 2、极大匹配、极大匹配G=:无向图无向图E EE 为为G中的匹配中的匹配对于对于G中的一切匹配中的一切匹配EE EE EE 为为G中的极大匹配中的极大匹配DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY3 3、最大匹配、匹配数、最大匹配、匹配数

38、G=: 无向图无向图最大匹配最大匹配:G中边数最多的匹配中边数最多的匹配匹匹 配配 数数:最大匹配所包含的边数最大匹配所包含的边数DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解释解释（1）最大匹配一定是极大匹配；）最大匹配一定是极大匹配；（2）极大匹配不一定是最大匹配；）极大匹配不一定是最大匹配；（3）最大匹配和极大匹配不唯一；）最大匹配和极大匹配不唯一；（4）匹配是对任意图定义的。）匹配是对任意图定义的。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITI

39、ME UNIVERSITY匹配举例匹配举例求图求图G的极大匹配、最大匹配和匹配数。的极大匹配、最大匹配和匹配数。最大匹配：最大匹配： a, c, g b, f, h 极大匹配：极大匹配：a, c, g, a, f, a, eb, e, b, f, h , b, g c, i, c, hd, g, d, hf, i匹配数：匹配数：3DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY4 4、完备匹配、完备匹配只有只有|V|V2 2| |V| |V1 1| |时，才可能有完备匹配时，才可能有完备匹配V1, V2:简单二部

40、图的互补结点子集简单二部图的互补结点子集G的匹配数的匹配数=|V1|V1到到V2的完备匹配的完备匹配最大匹配最大匹配DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY完备匹配举例完备匹配举例工作分配问题：工作分配问题：|V1|4， |V2|6满足：满足： |V2| |V1|但是却不存在完备匹配但是却不存在完备匹配因为：因为： a1, a2, a4只能胜任只能胜任p2, p5所以：必有一个人不能匹配，所以：必有一个人不能匹配，即没有工作。即没有工作。DALIAN MARITIME UNIVERSITY大大连连海海事事

41、大大学学 DALIAN MARITIME UNIVERSITY定理定理V1, V2:二部图的互补结点子集二部图的互补结点子集t:正整数正整数V1中的每个结点在中的每个结点在V2中至少有中至少有t个结点与其邻接个结点与其邻接V2中的每个结点在中的每个结点在V1中至多有中至多有t个结点与其邻接个结点与其邻接存在从存在从V1到到V2的完备匹配的完备匹配DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解释解释充分条件充分条件: :(1)满足条件一定存在完备匹配满足条件一定存在完备匹配(2)不满足条件也可能存在完备匹配不满

42、足条件也可能存在完备匹配DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理应用举例定理应用举例判断图判断图G是否存在完备匹配？如果存在请找出完备匹配。是否存在完备匹配？如果存在请找出完备匹配。d(ai) 2,(i=1,2,3,4)d(bj) 2(j=1,2,3,4,5)t存在完备匹配存在完备匹配(a1 1, b2 2),(a2 2, b1 1),(a3 3, b4 4),(a4 4, b3 3)(a1 1, b5 5),(a2 2, b1 1),(a3 3, b4 4),(a4 4, b3 3)DALIAN M

43、ARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理应用举例定理应用举例判断图判断图G是否存在完备匹配？如果存在请找出完备匹配。是否存在完备匹配？如果存在请找出完备匹配。d(a2)=3d(b1)=4不满足定理条件不满足定理条件存在完备匹配存在完备匹配:(a1, b2),(a2, b1),(a3, b4),(a4, b3)DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理V1, V2: 二部图的互补结点子集二部图的互补结点子集存在从存在从V1到

44、到V2的完备匹配的完备匹配对于任意的对于任意的S V1|S|NG(S)|NG(S)=v|v V2( v)v Sv与与 v在在G中邻接中邻接 DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理应用举例定理应用举例判断图判断图G是否存在完备匹配？如果存在请找出完备匹配。是否存在完备匹配？如果存在请找出完备匹配。V1=v1, v3, v5V2=v2, v4, v6, v7(V1)=,v1,v3,v5,v1,v3,v1,v5, v3,v5,v1,v3,v5DALIAN MARITIME UNIVERSITY大大连连海海

45、事事大大学学 DALIAN MARITIME UNIVERSITY解答解答(1) S1=v1, NG(S1)=v2,v6(2) S2=v3, NG(S2)=v2, v4,v6, v7 (3) S3=v5, NG(S3)=v4,v6,v7(4) S4=v1 , v3, NG(S4)=v2, v4,v6, v7(5) S5=v1 , v5, NG(S5)=v2, v4,v6, v7(6) S6=v3 , v5, NG(S6)=v2, v4,v6, v7(7) S7=v1 , v3 , v5, NG(S7)=v2, v4,v6, v7所以存在从所以存在从V1到到V2的完备匹配的完备匹配:(v1, v

46、2),(v3, v4),(v5, v6)DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY第第4 4节节 对偶图与着色对偶图与着色( (简介简介) )G=:平面图平面图F1,F2,Fn:G的的n个面个面(区区)图图G*=(1) G的任意一个面的任意一个面Fi， 内部有且仅有一个结点内部有且仅有一个结点vi* V*(2) 面面Fi, Fj的公共边界的公共边界ek,存在且仅存在一条边存在且仅存在一条边ek* E*ek*=(vi*,vj*)ek*与与ek相交相交(3) 当且仅当当且仅当ek只是一个面只是一个面Fi的边界时

47、，的边界时，vi*存在一个环存在一个环ek*和和ek相交相交图图G的对偶图的对偶图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解释解释（1）G与与G*的边数相同；的边数相同；（2）G*的结点数等于的结点数等于G的面数；的面数；（3）G*的面数等于的面数等于G的结点数。的结点数。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY对偶图举例对偶图举例求图求图G1的对偶图。的对偶图。F1内有一个结点内有一个结点v1*,v1*F2内有一个

48、结点内有一个结点v2*,v2*F3内有一个结点内有一个结点v3*,v3*V*=v1*, v2*, v3*DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答解答F1和和F3的公共边界为的公共边界为e1e1*=(v1*,v3*)e1*F1和和F3的公共边界为的公共边界为e4e4*=(v1*,v3*)e4*F1和和F2的公共边界为的公共边界为e5e5*=(v1*,v2*)F2和和F3的公共边界为的公共边界为e2e2*=(v2*,v3*)e2*F2和和F3的公共边界为的公共边界为e3e3*=(v2*,v3*)e3*e6

49、是是F3的边界的边界e6*是是v3*的一个环，且与的一个环，且与e6相交相交e6*E*=e1*,e2*,e3*,e4*,e5*,e6*e5*DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY6 6、自对偶图、自对偶图若若G与其对偶图同构，则称与其对偶图同构，则称G是自对偶图。是自对偶图。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY自对偶图举例自对偶图举例求图求图G2的对偶图，并说明的对偶图，并说明G2是自对偶图。是自对偶图。DAL

50、IAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答F1内有一个结点内有一个结点v1*,F2内有一个结点内有一个结点v2*,F3内有一个结点内有一个结点v3*,F4内有一个结点内有一个结点v4*,V*=v1*,v2*,v3* *,v4*v1*v2*v3*v4*DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答F1和和F4的公共边界为的公共边界为e1e1*=(v1*,v4*)e1*F3和和F4的公共边界为的公共边界为e2e2*=(v3*,

51、v4*)e2*F2和和F4的公共边界为的公共边界为e3e3*=(v2*,v4*)e3*F1和和F2的公共边界为的公共边界为e4e4*=(v1*,v2*)e4*F1和和F3的公共边界为的公共边界为e5e5*=(v1*,v3*)e5*F2和和F3的公共边界为的公共边界为e6e6*=(v2*,v3*)e6*DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY解答（续解答（续）DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY第第5节节 树树1、

52、树、树叶、树枝、分枝结点、树、树叶、树枝、分枝结点2、最小连通图、最小连通图3、森林、森林4、生成树、生成树树枝与连枝树枝与连枝5、求一个连通图、求一个连通图G的生成树的方法的生成树的方法6、最小生成树、最小生成树7、求最小生成树的算法、求最小生成树的算法DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY1 1、树、树叶、分枝结点、树枝、树、树叶、分枝结点、树枝(1) 树树:连通且无回路的无向图连通且无回路的无向图称为无向称为无向树，简称树，简称为树为树 T(2) 树叶树叶:树中度数为树中度数为1的结点的结点(3)

53、 分枝结点分枝结点: 树中度数大于树中度数大于1的结点的结点内结点内结点(4) 树枝树枝:树中的边树中的边注：一个平凡图注：一个平凡图(只有一个孤立结点的图只有一个孤立结点的图)也是连通且无也是连通且无回路，因此平凡图也是树，把这种树称为平凡树。其回路，因此平凡图也是树，把这种树称为平凡树。其它树称为非平凡树。它树称为非平凡树。DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY树的举例DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY2

54、 2、最小连通图、最小连通图G:连通图连通图G中去掉任何一条边中去掉任何一条边G变为不连通的图变为不连通的图最小连通图最小连通图DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理G=(n, m):无向图无向图以下关于树的定义是等价的：以下关于树的定义是等价的：（1）G连通且无回路连通且无回路（2）G无回路且无回路且m=n-1（3）G连通且连通且m=n-1（4）G无回路但增加一条边，得到且仅得到一条回路无回路但增加一条边，得到且仅得到一条回路（5）G是最小连通图是最小连通图（6）G中每一对结点之间有且仅有一条

55、路中每一对结点之间有且仅有一条路DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明证明: (1): (1)(2)(2)G连通且无回路连通且无回路 G无回路且无回路且m=n-1(1)当当n=1时，时，因因G连通且无回路，连通且无回路，m=0，显然，显然m=n-1成立成立(2)当当n=2时，时，因因G连通且无回路，所以连通且无回路，所以m=1，即，即m=n-1=2-1=1成立成立(3)假设当假设当n=k-1时成立，时成立，m=n-1=k-1-1=k-2来证来证n=k时也成立。时也成立。m=n-1=k-1因因G中无回

56、路且连通中无回路且连通至少有一个结点至少有一个结点u的度为的度为1DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明（续）证明（续）uW边边:(u, w)删除结点删除结点u与其相关联的边，得到一个具有与其相关联的边，得到一个具有k- 1个个结点的图结点的图G, 由归纳假设知：由归纳假设知： m= k-2成立。成立。再将结点再将结点u以及关联的边以及关联的边(u, w)加入加入G中得到原图中得到原图G。边数边数m+1: m=k-2+1=k-1结点数结点数n+1：n=k-1+1=km=n-1成立成立DALIAN M

57、ARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明证明: (2)(3)G无回路且无回路且m=n-1 G连通且连通且m=n-1假设假设G不连通不连通:不妨设不妨设G有有k个分支个分支G1=(n1,m1),G2=(n2,m2),Gk=(nk,mk)n1+n2+nk=nm1+m2+mk=mG无回路无回路每个分支连通且无回路每个分支连通且无回路m1=n1-1,m2=n2-1,mk=nk-1m=(n1-1)+(n2-1)+(nk-1)= n1+n2+nk k=n-kk=1G是连通的是连通的DALIAN MARITIME UNIVERSI

58、TY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY定理定理任意一棵非平凡树至少有两个树叶。任意一棵非平凡树至少有两个树叶。【平凡树：只有一个孤立节点的树【平凡树：只有一个孤立节点的树(连通、无回路连通、无回路)】DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY证明证明(1)假设假设T中各结点的度均大于或等于中各结点的度均大于或等于2，则：，则：deg(v1)+deg(v2)+deg(vn)2n，即得：，即得：2n-2 2n-2，矛盾矛盾(2)假设假设T中只有中只有1个结点的度为个结

59、点的度为1，其余结点的度均大于，其余结点的度均大于1，则：，则：d(v1)+d(v2)+d(vn)1+(n-1)2=2n-2+1=2n-1，即得：，即得： 2n-2 2n-1，矛盾矛盾再由再由(1)、(2)知：一棵非平凡树中至少有两个度为知：一棵非平凡树中至少有两个度为1的结点，的结点，即至少有两片树叶。即至少有两片树叶。 mvnii2)deg(1树树T=(n, m)，则，则m= n-1=2m=2(n-1)=2n-2DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY3 3、森林、森林如果非连通无向图如果非连通无向图

60、G的每个支都是树，则称的每个支都是树，则称G为森林。为森林。若森林的分支数为若森林的分支数为k, 则：则：m=n-kDALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DALIAN MARITIME UNIVERSITY4 4、生成树、树枝、连枝、生成树、树枝、连枝生成树不唯一生成树不唯一(1) 生成树生成树:无向图无向图G的生成子图的生成子图T是一棵树是一棵树G的生成树的生成树(2) 树枝：树枝：G的生成树的生成树T中的边中的边(3) 连枝：连枝：属于属于G但不属于但不属于T的边的边DALIAN MARITIME UNIVERSITY大大连连海海事事大大学学 DAL