离散数学及其应用-11 几类典型图

11.1欧拉图11.2哈密顿图11.3二分图11.4平面图第十一章

几类典型图欧拉图起源

东普鲁士一座小镇哥尼斯堡(现俄罗斯加里宁格勒)被普雷格尔河支流分成四部分:河两岸、河道中央的克奈普霍夫岛以及河两条支流之间的陆地区域,十八世纪有七座桥将四部分陆地连接起来。镇上居民想知道从镇上某一地出发,不重复地经过所有七座桥能否再回到原地。数学家欧拉将此问题抽象成由顶点和边组成的图,四部分陆地为顶点A、B、C、D,桥为连接两地对应顶点的边（右下图）,求遍历图中各边均一次的回路。11.1.1欧拉无向图

由哥尼斯堡七桥问题抽象得到的图和不重复地经过所有桥回到原地的问题,得到欧拉回路(与通路)等著名定义。欧拉无向图相关定义连通无向图G=<V,E>（1）经过图G的每一条边恰好一次(起点、终点不重合)的通路称为欧拉通路或欧拉开迹(Eulertrail),有欧拉通路的图称为半欧拉图。（2）经过图G的每一条边恰好一次的回路称为欧拉回路或欧拉闭迹(Eulercircuit),有欧拉回路的图称为欧拉图。11.1.1欧拉无向图定理

连通无向图G=<V,E>为欧拉图的充分必要条件是G所有顶点度为偶数。证明

(1)

必要条件:图G无孤立顶点,任意二顶点连通,任意顶点均有关联边v∈V,d(v)≥1。G有欧拉回路L:vi1e1vi2e2…emvi1,则顶点v在回路L中出现至少1次。令v∈V在回路L中出现nv次,如果顶点v的关联边为自环,组成自环的一边为d(v)贡献2,在回路中对应顶点v的两次相邻出现各贡献1。否则,每次出现在回路中与之关联的两边不同,而且由欧拉回路知,L中所有与之关联的边均各异,则一次出现为度数贡献2,则d(v)=2·nv为偶数。11.1.1欧拉无向图定理

连通无向图G=<V,E>为欧拉图的充分必要条件是G所有顶点度为偶数。证明（续）

(2)

充分条件:图G连通,则无孤立顶点,任意顶点v∈V,d(v)≥1。而所有顶点度均为偶数,有v∈V,d(v)≥2,则如果G为简单图,有长度大于等于3的初级回路L0:vi0e0i0vi0+1…vi1e0i1…vi0。如果G为重图,环、重边同为初级回路。可知L0中除端点外顶点无重复,则边无重复,L0各顶点度贡献为偶数2。如果E-E(L0)为空,则初级回路L0为欧拉回路。11.1.1欧拉无向图定理

连通无向图G=<V,E>为欧拉图的充分必要条件是G所有顶点度为偶数。证明（续）

否则,如果E-E(L0)非空,由于G和L0所有顶点度为偶数,G[E-E(L0)]中各顶点度d'(v)均为偶数。可以证明L0∩G[E-E(L0)]非空,即L0中存在顶点在G[E-E(L0)]中有非零偶数条关联边:G[E-E(L0)]非空而G连通,则有顶点u∈G[E-E(L0)],v∈L0,u,v两顶点在G中连通,则u,v通路中存在顶点u0∈G[E-E(L0)]邻接顶点v0∈L0,则顶点v0在G[E-E(L0)]有关联边(u0,v0),则d'(v0)≠0。d'(v0)为偶数,则d'(v0)≥2。11.1.1欧拉无向图定理

连通无向图G=<V,E>为欧拉图的充分必要条件是G所有顶点度为偶数。证明（续）

G[E-E(L0)]中各顶点v度d'(v)≥2,为偶数,同理有初级回路L1,L1端点外顶点无重复,边无重复,各顶点度贡献为偶数2,易知初级回路L0,L1中无重复边:E(L1)∩(E-E(L0))=E(L1)⇒E(L0)∩E(L1)=E(L0)∩(E(L1)∩(E-E(L0)))=E(L0)∩(E(L1)∩(E∩~E(L0)))=E(L0)∩~E(L0)∩E(L1)∩E=⌀。11.1.1欧拉无向图定理

连通无向图G=<V,E>为欧拉图的充分必要条件是G所有顶点度为偶数。证明（续）

G如果E(L0)∪E(L1)=E,则v0∈L0,v0∈L1,L=L0∪L1为简单回路而且是欧拉回路。如果E-E(L0)-E(L1)≠⌀,同理依次可得初级回路L2,L3,…,Ls-1,Ls,Ls为最后一条初级回路,有G=∪sj=0Lj。如此依次可得简单回路L0,L0∪L1,L0∪L1∪L2,L0∪L1∪L2∪L3,…,∪sj=0Lj,而最后一个简单回路∪sj=0Lj包含G所有边恰好一次,为欧拉回路。11.1.1欧拉无向图定理

连通无向图G=<V,E>为半欧拉图的充分必要条件是G有且只有两个顶点度为奇数。证明

本定理证明主要前一定理结论。(1)充分条件:令两个奇度数顶点为u,v∈G,d(u)=2·k1+1,d(v)=2·k2+1,则增加边e0=(u,v),则G'=<V,E∪{e0}>中所有顶点度均为偶数⇔G'中有欧拉回路L0:ue1u1e2…emve0u,则有P0⊆G:ue1u1e2…emv为欧拉通路,图G为半欧拉图。11.1.1欧拉无向图定理

连通无向图G=<V,E>为欧拉图的充分必要条件是G所有顶点度为偶数。证明（续）

(2)必要条件:图G为半欧拉图,有欧拉通路。令欧拉通路为P0:vi1e1vi2e2…emvim+1(vi1≠vim+1),G中增加关联起点终点的边e0=(vi1,vim+1),则G'=<V,E∪{e0}>中有欧拉回路L0=P0∪{e0}:vi1e1vi2e2…emvim+1e0vi1⇔G'中所有顶点度均为偶数,因此G中只有顶点vi1,vim+1为奇数。11.1.1欧拉无向图如果哥尼斯堡七桥问题经变换如左图所示,能否从某地出发经过七座桥只一次而回到原地?解

将哥尼斯堡七桥问题抽象成右图,经验证,所有顶点A,B,C,D度均为偶数,则图中有欧拉回路。按边1,2,3,4,5,6的顺序得到欧拉回路,遍历图的所有边各一次。11.1.1欧拉无向图欧拉有向图相关定义

有向图D=<V,E>（1）经过图D的每一条边恰好一次(起点、终点不重合)的有向通路称为有向欧拉通路,有有向欧拉通路的图称为半欧拉有向图。（2）经过图D的每一条边恰好一次的有向回路称为有向欧拉回路,有有向欧拉回路的图称为欧拉有向图。依据前文结论,如果有向图是欧拉有向图,则为强连通图；如果有向图是半欧拉有向图,则为单向连通图。11.1.2欧拉有向图

依据前文欧拉图和半欧拉图与图顶点度之间关系的结论,对有向图有如下相似结论。定理（1）连通有向图D=<V,E>为半欧拉有向图的充分必要条件是D恰有两顶点度为奇数,其中之一出度比入度大1,另一顶点入度比出度大1,其他顶点v均有d+(v)=d-(v)。（2）连通有向图D=<V,E>为半欧拉有向图的充分必要条件是D任意顶点v均有d+(v)=d-(v)。11.1.2欧拉有向图欧拉有向图的一类应用与笛波滤恩序列有关。笛波滤恩序列(DeBruijnsequence)是一个长度为L由字母表Σ={0,1,…,σ-1}中不同字符组成的循环序列a0a1…aL-1(ai∈Σ,0≤i≤L-1),记作B(σ,n),序列B(σ,n)中连续有L个长度为n的子序列;令子序列为词w,词长为n,任意词w在循环序列对应唯一i,令w=aiai+1…ai+n-1(i+s=(i+s)modL,0≤s≤n-1),不难证明L=σn。11.1.3欧拉回路与通路的应用如果字母表只有二进制字符Σ={0,1},则有L=2n;考虑n=4,有L=24=16,如循环序列0000100110101111为笛波滤恩序列。如(b)图,构造有向图D=<V,E>,V={v0,v1,…,v7},顶点与8个二进制数有一一对应关系:f(v0)=000,f(v1)=001,f(v2)=010,…,f(v7)=111。11.1.3欧拉回路与通路的应用（a）（b）（续）顶点vi,vj之间如果有f(vi)长度为2的后缀等于f(vj)长度为2的前缀,则定义有向边eij=<vi,vj>,同时定义与边eij一一对应的4位二进制数,长度为3的前缀是f(vi),长度为3的后缀是f(vj),令f(vi),f(vj)之间重复的2位只在二进制数中间出现一次。例如f(v0)=000,f(v1)=001,e01=<v0,v1>=0001,又如f(v1)=001,f(v2)=010,e12=<v1,v2>=0010。如此构造有向图D各顶点出度、入度相等,为欧拉有向图,而一组笛波滤恩序列对应有向图D的一条有向欧拉回路。另外,(a)图展示n=3情况下Σ={0,1}上的笛波滤恩序列对应的欧拉有向图。11.1.3欧拉回路与通路的应用笛波滤恩序列可应用于通信、密码学、计算机科学、生物信息等重要领域。如基因组测序组装过程读段分割成等长子序列k-mer,子序列长度为k个碱基(碱基可以是A,C,G,T)。以子序列k-mer的k-1前缀和k-1后缀为顶点,二者之间重叠关系定义边,按照以上所示构造笛波滤恩图的方法可以构造欧拉有向图,通过找欧拉回路来得到原始基因序列的可能组装。如后图所示,序列ATGGCGTGCA有子序列k-mer,词(子序列)长k=3,重叠部分k-2=1。例如子序列ATG前缀AT和后缀TG顶点有重叠T,则有向边关联e=<AT,TG>=ATG,以此类推得到8顶点10条边的欧拉有向图,有向欧拉回路经过顶点依次为AT-TG-GG-GC-CG-GT-TG-GC-CA-AA-AT,重叠部分只算一次得到的边沿此欧拉回路依次为ATG,TGG,GGC,GCG,CGT,GTG,TGC,GCA,CAA,AAT（如后图）。11.1.3欧拉回路与通路的应用11.1.3欧拉回路与通路的应用11.1欧拉图11.2哈密顿图11.3二分图11.4平面图第十一章

几类典型图十九世纪爱尔兰数学家哈密顿爵士提出“周游世界”游戏,要求玩家在地球上20个不同城市中选择其中之一为出发点,游历所有城市各一次而不重复,最后回到出发点。抽象成数学问题即20个城市为正十二面体的20个顶点,两顶点之间的棱线象征两城市之间的交通路线,从其中一顶点出发沿着棱线经过正十二面体的20个顶点恰好一次回到原点的回路。11.2哈密顿图正十二面体左图的平面拓扑哈密顿图相关定义

连通图G=<V,E>中（1）有一条经过各顶点恰好一次的通路,则称此通路为哈密顿通路(Hamiltonpath),称G为半哈密顿图。（2）有一条经过各顶点恰好一次的回路,则称此回路为哈密顿回路(Hamiltoncircle),称G为哈密顿图。需注意,通常所研究问题中G的顶点数大于等于3,则哈密顿回路又称为哈密顿圈(Hamiltoncycle)。11.2哈密顿图定理

图G=<V,E>为哈密顿图,则对于顶点集V的每一个非空顶点子集S,P(G-S)≤|S|均成立,其中P(G-S)是G-S的连通分支数,|S|是S中顶点数。证明

图G为哈密顿图,则连通⇔P(G)=1,有哈密顿回路L⊆G,为各顶点出现一次的初级回路,V(L)=V(G)=V,L⊆G⇔L=G或L⊂G二者之一为真。(1)L=G,任意顶点子集S⊂V,当|S|=1时,删除S得到G-S的哈密顿通路,有P(G-S)=1=|S|;数学归纳令|S|=k,删除S至多得到|S|个连通分支G1,G2,…,Gs(1≤s≤S)。11.2哈密顿图定理

图G=<V,E>为哈密顿图,则对于顶点集V的每一个非空顶点子集S,P(G-S)≤|S|均成立,其中P(G-S)是G-S的连通分支数,|S|是S中顶点数。证明（续）

如果S中顶点均两两不邻接,有s=P(G-S)=|S|,否则有s=P(G-S)<|S|,各连通分支Gi均为一条Gi中各顶点出现一次的初级通路。|S|=k+1时,删除S中前k个顶点得到连通分支G1,G2,…,Gs(1≤s≤|S|-1),有连通分支Gi0令第k+1个顶点vk+1∈Gi0,1≤i0≤s。如果vk+1不是Gi0端点则删除vk+1将Gi0分为两段,有P(G-S)=s+1≤|S|,否则P(G-S)=s<|S|,而当Gi0为一孤立顶点{vk+1}则P(G-S)=s-1<|S|。11.2哈密顿图定理

图G=<V,E>为哈密顿图,则对于顶点集V的每一个非空顶点子集S,P(G-S)≤|S|均成立,其中P(G-S)是G-S的连通分支数,|S|是S中顶点数。证明（续）

(2)如L⊂G,任意顶点子集S⊂V,V(G-S)=V(L-S)⇔L-S为G-S生成子图,这等价于在L-S中增加边关联部分顶点得到G-S,因此P(G-S)≤P(L-S)≤|S|。11.2哈密顿图定理

图G=<V,E>为哈密顿图,则对于顶点集V的每一个非空顶点子集S,P(G-S)≤|S|均成立,其中P(G-S)是G-S的连通分支数,|S|是S中顶点数。由此定理得知哈密顿图都是2-连通的。定理结论为哈密顿图的必要条件,而非充分条件,因此不能用来直接判断一图是否为哈密顿图。而如果这一必要条件对图不成立,可以排除图为哈密顿图。11.2哈密顿图判断如下各图是否为哈密顿图,说明右图不是哈密顿图。解

(a)图和(b)图均有删除任意非空子集S⊂V,P(G-S)≤|S|条件成立,而(b)图和(c)图非哈密顿图,(b)图为著名的彼得森(Peterson)图,右图为有割点的连通图。11.2哈密顿图（a）（c）（b）彼得森图删除一顶点可得到哈密顿图。解

(a)图删除一顶点得到(b)图,由路径e1e2e3e4e5e6e7e8e9得到哈密顿回路,是哈密顿图。11.2哈密顿图（a）（b）

11.2哈密顿图定理

图G=<V,E>是n(n≥3)个顶点的简单图,对于每一对不相邻顶点u,v有d(u)+d(v)≥n-1,则G是半哈密顿图,有一条哈密顿通路。证明（续）

如果s=n-1,则初级通路P包含G中所有n个顶点,为哈密顿通路。可以证明如果s<n-1,则P不是G最长的初级通路,矛盾:先证明如果s<n-1,则G中有包含P所有顶点各一次的初级回路L。如果端点v0,vs邻接,显然L:v0v1v2…vsv0。如果v0,vs不邻接,可以证明P中存在两邻接顶点vk,vk+1,有vk与vs邻接,vk+1与v0邻接:11.2哈密顿图定理

图G=<V,E>是n(n≥3)个顶点的简单图,对于每一对不相邻顶点u,v有d(u)+d(v)≥n-1,则G是半哈密顿图,有一条哈密顿通路。证明（续）

令通路P中v0所有d(v0)=m个邻接顶点沿P由近到远依次为vi1,vi2,…,vim,只需证明vi1-1,vi2-1,…,vim-1至少有一个邻接vs;否则vs的所有邻接点为通路P两端点v0,vs以及m个vi1-1,vi2-1,…,vim-1以外的其他顶点,则有d(vs)≤s+1-2-m<n-m-2,而由v0,vs不邻接得知d(vs)≥n-m-1,矛盾。因此P有邻接顶点vk,vk+1,令vk与vs邻接,vk+1与v0邻接。如后图所示,有包含P中所有顶点各一次的初级回路L:vkvsvs-1…vk+1v0v1v2…vk。11.2哈密顿图定理

图G=<V,E>是n(n≥3)个顶点的简单图,对于每一对不相邻顶点u,v有d(u)+d(v)≥n-1,则G是半哈密顿图,有一条哈密顿通路。11.2哈密顿图（a）（c）（b）定理

图G=<V,E>是n(n≥3)个顶点的简单图,对于每一对不相邻顶点u,v有d(u)+d(v)≥n-1,则G是半哈密顿图,有一条哈密顿通路。证明（续）

再证明如果s<n-1,P不是G最长初级通路这一矛盾:令顶点u∈G,u∉P,由已证结论知u与P的端点v0不邻接,则简单图G中与u邻接的顶点数为d(u)≥n-d(v0)-1。端点v0邻接点都在P中,G中不与v0邻接而不包括u与v0的顶点数有n-d(v0)-2<d(u),则u与v0有一共有邻接点w。通路P端点v0邻接点w∈P,则w∈L。令w在初级回路L中两邻接点为w1,w2,能由此利用u与初级回路L。11.2哈密顿图

11.2哈密顿图定理

图G是n(n≥3)个顶点的简单图,对于每一对不相邻顶点u,v有d(u)+d(v)≥n,则G是哈密顿图,有一条哈密顿回路(哈密顿圈)。证明同前一定理的哈密顿通路证明。推论

图G是n(n≥3)阶简单图,δ(G)≥n/2,则G是哈密顿图。推论

完全图Kn(n≥3)均为哈密顿图。11.2哈密顿图有20人参加活动,每人均与10人相互认识,如果20人都出席一圆桌会议,能否合理安排座位令每人与邻座两人认识?解

将此问题构造为简单无向图G=<V,E>,n=|V|=20,参加活动的人作为顶点,两人如相互认识则有边关联两顶点。此问题需判断图G中能否找到哈密顿回路。而任意顶点v的度d(v)=10,则任意不邻接顶点u,v的度之和d(u)+d(v)=20≥n,判断哈密顿图的充分条件成立,则存在哈密顿回路,确定存在圆桌会议的座位安排顺序令所有人都与相互认识的人邻座。11.2哈密顿图与欧拉图不同,已知对哈密顿图的判断条件尚缺少充分必要条件。以上定理为判断哈密顿图提供充分条件,陈述一个直观事实:简单图所有顶点之间关联边越多就越可能是哈密顿图。而充分条件不成立则不能排除哈密顿图。例如,一n阶图G(n≥5)为n个顶点组成的初级回路,为哈密顿图,而所有顶点度均为2,判定哈密顿图的充分条件不成立;再如,彼得森图删除一顶点可以得到哈密顿图,而充分条件对此图亦不成立。11.2哈密顿图

11.2哈密顿图（a）（c）（b）

11.2哈密顿图11.1欧拉图11.2哈密顿图11.3二分图11.4平面图第十一章

几类典型图二分图无向图G=<V,E>(1)对于整数r≥2,如果顶点集V能划分成r个类,令任意边的两端点都属于不同的类,即任一顶点u如果有邻接顶点v则v不属于u的类,则称图G为r-部图(r-partitegraph)。通常称2-部图为二部图或二分图(bipartitegraph)。(2)二分图G=<V,E>划分成两个类,得非空顶点子集V1,V2,V1∪V2=V,V1∩V2=⌀,∀e=(u,v)∈E→u∈V1∧v∈V2,V1,V2称为互补顶点子集,二分图记作G=<V1,V2,E>。(3)如果二分图G=<V1,V2,E>任意两顶点u∈V1,v∈V2都恰有一边关联,则称G为完全二分图。令|V1|=n1,|V2|=n2,则完全二分图记作Kn1,n2。完全二分图Kn1,n2顶点数n=n1+n2,边数m=n1·n2。11.3.1二分图相关定义注意

r-部图包括二分图的定义中,对图G=<V,E>顶点集V的划分定义了一个等价类,这蕴含顶点子集非空,不考虑平凡图;如果在r-部图包括二分图中考虑平凡图,则须指出允许存在空顶点子集,则顶点子集非划分所得等价类。简单说明下图两个例子是否为r-部图或二分图。

11.3.1二分图相关定义（a）（b）解

(a)为3-部图,G=<V1,V2,V3,E>,V1={a},V2={b,c},V3={d,e};(b)为二分图,G=<V1,V2,E>,xi∈V1,yj∈V2(i,j=1,2,3,4,5)。一般来说难以从外观直观判断二分图,因此需要结论提供判断依据。定理

非平凡无向图G为二分图的充分必要条件是图G中无长度为奇数的回路。11.3.1二分图相关定义证明

(1)必要条件:如果二分图G=<V1,V2,E>有回路L0:v1e1,2v2…vnen,1v1,不妨令v1∈V1。二分图V1,V2内部无邻接顶点,则回路的边e1,2,e2,3,…,en,1依次为V1到V2,V2回V1交替成对出现直至返回V1起点v1,则L0长度为偶数。(2)充分条件:只需考虑连通图G,因为非连通图只需逐一证明连通分支为二分图。G非平凡而连通,则存在一非平凡初级通路P0:v01e01,2v02e02,3…e0r0-1,r0v0r0,依次序交替令各顶点交替属于两顶点子集V1,V2:v02·k-1∈V1,v02·k∈V2(k=1,2,…),证明G[V(P0)]为二分图:显然有V1∪V2=V(P0),V1∩V2=⌀,只需反证G有边e0关联同一子集中顶点。令其为V1,e0=(v02·k1-1,v02·k2-1)∈G,k1≤k2,e0与P0中v02·k1-1v02·k1v02·k1+1…v02·k2-1段初级通路组成G中长度为奇数的回路,矛盾。11.3.1二分图相关定义证明（续）

如果G-G[V(P0)]≠⌀,其中有顶点v,v∉V1,v∉V2,G连通则v与P0顶点连通,存在非平凡初级通路P1:v11e11,2v12e12,3…e1r1-1,r1v1r1,v=v1r1,有且只有第一个顶点v11∈G[V(P0)],则v11∈V1或v11∈V2。不妨令v11∈V1,按初级通路P0的顶点分配方法,初级通路P1中顶点顺序依次交替属于两子集V1,V2:v12·k-1∈V1,v12·k∈V2(k=1,2,…)。可以证明P0∪P1为二分连通图:v1r1∈P1,v11∈P0,而v1r1,v11连通则由连通等价关系知P0∪P1连通;而由V1,V2构造方式知,P0,P1任意边都关联V1,V2中顶点各一,P0∪P1为二分图。可以证明G[V(P0∪P1)]为二分图:从构造方式有V1∪V2=V(P0∪P1),V1∩V2=⌀,只需反证有边e1=(u,v)∈G关联相同顶点子集中两顶点u,v,则边e1∉P0∪P1。11.3.1二分图相关定义证明（续）

不妨令u,v∈V1,P0∪P1连通则有初级通路Pu,v⊆P0∪P1连通u,v。P0∪P1为二分图,则有Pu,v中边依次为V1到V2,V2回到V1交替成对出现直至回到同属于V1的终点v,所以Pu,v长度为偶数,则L=Pu,v∪{e1}⊆G为奇数长度的回路,矛盾。因此G[V(P0∪P1)]为二分图。以此类推依次得初级通路P0,P1,…,Ps,至V(P0∪P1∪…∪Ps)=V,G[V(P0∪P1∪…∪Ps)]为二分图:G[V(P0∪P1∪…∪Ps)]=G[V]=G=<V1,V2,E>。推论

非平凡树为二分图(如果二分图将平凡图考虑在内,则树为二分图)。11.3.1二分图相关定义

11.3.1二分图相关定义二分图重要应用是匹配问题,对此先同时给出针对一般图与二分图的相关概念。匹配相关定义

无向图G=<V,E>,边集的子集M⊆E

(1)如果M中的边均无公共端点,无顶点自环,则称M为G的一个匹配(matching)。

(2)如果匹配M=⌀,则称M为空匹配。

(3)如果匹配M不能通过添加G中的边来扩大M中元素数,则称M为极大匹配。11.3.2匹

配

11.3.2匹

配匹配相关定义（续）

(8)已知图G匹配M,如果G中一条通路由交替出现和不出现在M中的边组成,则称此通路为M-交互道。

(9)如果M-交互道两个端点均为M-不饱和顶点,则称其为M-可增广道(augmentingpath)。注意

二分图重要应用是匹配问题,对此先同时给出针对一般图与二分图的相关概念。M-可增广道长度为奇数,不属于M的边数量为属于M的边数量加1。特别地,一条边的两端点均为M-不饱和,则此边为可增广道。二分图G如有完全匹配M,则M显然为最大匹配。11.3.2匹

配

11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配二分图G=<V1,V2,E>如图所示,V1={x1,x2,…,x7},V2={y1,y2,…,y7},求最大匹配M。解（续）

11.3.3最大匹配与完全匹配二分图G=<V1,V2,E>如图所示,V1={x1,x2,…,x7},V2={y1,y2,…,y7},求最大匹配M。解（续）

4.x=x4,M-可增广道(x4,y3,x1,y1,x2,y2,x3,y4),置M={(x4,y3),(x3,y4),(x2,y2),(x1,y1)}。5.x=x5,M-可增广道(x5,y5),置M={(x5,y5),(x4,y3),(x3,y4),(x2,y2),(x1,y1)}。6.x=x6,M-可增广道(x6,y4,x3,y6),置M={(x6,y4),(x5,y5),(x4,y3),(x3,y6),(x2,y2),(x1,y1)}。11.3.3最大匹配与完全匹配二分图G=<V1,V2,E>如图所示,V1={x1,x2,…,x7},V2={y1,y2,…,y7},求最大匹配M。解（续）

7.x=x7,M-可增广道(x7,y6,x3,y2,x2,y1,x1,y4,x6,y7),置M={(x7,y6),(x6,y7),(x5,y5),(x4,y3),(x3,y2),(x2,y1),(x1,y4)}得到最大匹配M有7条无共有顶点的边,如最后一图的实线所示。11.3.3最大匹配与完全匹配定理

霍尔定理:二分图G=<V1,V2,E>有V1-完全匹配M的充分必要条件为对V1任意子集S⊆V1和所有与S邻接的顶点组成的顶点集N(S)恒有|N(S)|≥|S|。证明

(1)必要条件:V1-完全匹配M,则任意顶点u∈V1有e=(u,v)∈M⊆E,V1所有顶点u在M中有一一对应邻接点,无重复。则任意子集S⊆V1,M中S邻接顶点组成子集NM(S)有集合计数运算:|NM(S)|=|S|,而NM(S)⊆N(S),则|N(S)|≥|S|。(2)充分条件:令二分图G=<V1,V2,E>有对任何子集S⊆V1,令与S邻接的顶点集N(S)恒有|N(S)|≥|S|。11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配定理

霍尔定理:二分图G=<V1,V2,E>有V1-完全匹配M的充分必要条件为对V1任意子集S⊆V1和所有与S邻接的顶点组成的顶点集N(S)恒有|N(S)|≥|S|。证明（续）

则|T∩V1-{v0}|=|T∩V2|。G为二分图知T∩V2⊆N(T∩V1),只需证明N(T∩V1)⊆T∩V2。可以证明任意顶点v∈N(T∩V1)→v∈T∩V2:反证,令顶点w0∈N(T∩V1),w0∉T∩V2,则有w0∉M,令其邻接点w1∈T∩V1,et=(w0,w1)∉M,而由T∩V1定义知,存在一条以v0为端点,另一端点在T∩V1中的M-交互道P0:v0e0,1v1e1,2v2…er,w1w1ew1,t…经过顶点w1。11.3.3最大匹配与完全匹配

11.3.3最大匹配与完全匹配定理

霍尔定理:二分图G=<V1,V2,E>有V1-完全匹配M的充分必要条件为对V1任意子集S⊆V1和所有与S邻接的顶点组成的顶点集N(S)恒有|N(S)|≥|S|。证明（续）

综上,同时有T∩V2⊆N(T∩V1),N(T∩V1)⊆T∩V2,则N(T∩V1)=T∩V2。而由T∩V1-{v0}和T∩V2一一对应关系可知:|N(T∩V1)|=|T∩V2|=|T∩V1-{v0}|=|T∩V1|-1<|T∩V1|。由如上求得V1子集T∩V1令|N(T∩V1)|<|T∩V1|,与|N(T∩V1)|≥|T∩V1|矛盾。因此G有V1-完全匹配。11.3.3最大匹配与完全匹配

工作中任务调度寻找一种方案,现将待分配任务x1,x2,…,x6指派给y1,y2,…,y66位工作人员,让每人都完成一项自己胜任的任务,如图G=<V1,V2,E>,V1={x1,x2,…,x6},V2={y1,y2,…,y6},每人各自擅长不同任务,人员yj能胜任任务xi一一对应图中边eij=(xi,yj)。能否找到达到以上目的的方案?11.3.3最大匹配与完全匹配

工作中任务调度寻找一种方案,现将待分配任务x1,x2,…,x6指派给y1,y2,…,y66位工作人员,让每人都完成一项自己胜任的任务,如图G=<V1,V2,E>,V1={x1,x2,…,x6},V2={y1,y2,…,y6},每人各自擅长不同任务,人员yj能胜任任务xi一一对应图中边eij=(xi,yj)。能否找到达到以上目的的方案?解

不能。方案需所有人都完成自己胜任的任务,即二分图应达到V2-完全匹配。而根据霍尔定理结论,V2-完全匹配条件不成立:令S={y1,y2,y5,y6}⊆V2,N(S)={x1,x2,x3},而|N(S)|<|S|。11.3.3最大匹配与完全匹配11.1欧拉图11.2哈密顿图11.3二分图11.4平面图第十一章

几类典型图图的一类应用问题如电子电路设计、地理位置选址和布局等在约束中用到平面概念,如要求在问题中模拟的顶点之间布线以建立联系,所有顶点与线在同一平面而线与线除在顶点以外不相交,由此用到平面图以及相关概念。特别地,平面图着色问题有诸多应用场景,如地图着色、不同时间段任务最优调度等统筹规划问题。平面图相关定义

无向图G=<V,E>

(1)图G所有顶点和边都可以画在同一平面上,而且边之间除顶点外无交点,则称图G为可平面图(planargraph),或称图G可嵌入平面。这种画法称为图G的平面表示。否则称图G为非平面图。可平面图嵌入平面得到平面嵌入实例,为平面图。11.4.1平面图相关定义平面图相关定义（续）

(2)可平面图G嵌入平面后将平面分为数个区域,每个区域由边包围而内部无G的任何顶点或边,称为G的一个面(region),其中面积无限的区域称为外部面或无限面。包围面的所有边组成的回路称为这个面的边界(boundary),边界长度称为面的次数或度(degree),面Ri的度记作deg(Ri)。

(3)平面简单图G的任意两顶点之间加一条边(非环非重边),所得图为非平面图,则称G为极大平面图。

(4)非平面图G删除任一边所得图为平面图,则称G为极小非平面图。11.4.1平面图相关定义可平面图具有诸多特征,应用广泛。注意可平面图的定义,有的图的边有除顶点之外的交点,却为可平面图:如果对已知图G的顶点和边只作位置、几何形状的调整而不改变顶点和边的关联定义,得到一平面嵌入实例。显然,并非所有图都能通过此类调整得到平面嵌入。以下有关顶点数、边数、面的度数之间关系的结论不区分可平面图与平面图。阐述左下图能否平面嵌入,如果能,说出各个面的度。11.4.1平面图相关定义（a）（b）解

原图有相交的边,移动2条边的位置而不改变其与顶点之间的对应关联关系能将原图化为下图平面嵌入,有六边形内部4个面,度均为3;六边形上方的弧和2条边组成度为3的面,左下方弧和3条边组成度为4的面,以及外部无界的面度为3。11.4.1平面图相关定义（a）（b）定理

平面图G所有面的度之和为边数的2倍。证明

平面图G的边有两种:不同两个面共有的边和只为一个面所有的边。不同两个面Ri、Rj的边eij为面Ri和Rj的度贡献值均为1。只为1个面Ri的边eii为Ri的度贡献为2。则图G所有边累加之和的2倍为所有面度累加之和。11.4.1平面图相关定义定理

欧拉(Euler)公式:平面连通图G有n个顶点,m条边,r个面,n-m+r=2。证明

G是连通图,则有n-m≤1。当n-m=1时,G是树,树无回路,是平面图,有唯一一个无界面,有n-m+r=2。当n-m<1时G有回路,删除回路的一条边G仍是平面连通图,以下证明当n-m<1时有n-m+r=2。在平面连通图边的条数m上做数学归纳:m=0,G为平凡图,有n=1,r=1,n-m+r=2。令m=k,n-m+r=2成立。则m=k+1时,已知在m=k时n-m+r=2对平面连通图成立,如果增加1条边G仍为平面连通图,则所增加边为11.4.1平面图相关定义定理

欧拉(Euler)公式:平面连通图G有n个顶点,m条边,r个面,n-m+r=2。证明（续）

(1)一顶点的环:为图G增加1条边,1个面,则n-(m+1)+(r+1)=n-m+r=2。(2)悬挂边:为图G增加1条边,1个顶点,则(n+1)-(m+1)+r=n-m+r=2。(3)图G中两不同顶点定义:为图G增加1条边,1个面,则n-(m+1)+(r+1)=n-m+r=2。11.4.1平面图相关定义推论

G为平面连通简单图(n,m),n≥3,则m≤3·n-6。证明

G为简单图,顶点数大于等于3,排除平凡图、二顶点连通简单图、重边或环组成的面,则每个面至少有3条边。G是顶点数大于等于3的平面连通图,则欧拉公式有n-m+r=2,而∑Ri∈Gdeg(Ri)=2·m⇒3·r≤2·m,则2=n-m+r≤n-m+2·m/3⇒3·n-6≥m。推论

极大平面连通图的边数m=3·n-6。证明

极大平面连通图的每个面的次数均为3,则3·r=2·m。欧拉公式有n-m+r=2,则m=3·n-6。11.4.1平面图相关定义定理G为平面连通图(n,m),每个面的度至少为l(l≥3),则m≤l·(n-2)/(l-2)。证明

G由平面图面的度和边数的关系:2·m=∑i=1rdeg(Ri)≥l·r。由欧拉公式知n-m+r=2,则有r≤2·m/l,m≤l·(n-2)/(l-2)。推论

平面连通简单图不以K3为子图,则m≤2·n-4。证明

平面连通简单图不以K3为子图,而且无环、重边组成的面,则任一面Ri的度deg(Ri)≥l=4。则m≤l·(n-2)/(l-2)=2·n-4。11.4.1平面图相关定义推论

K5,K3,3是非平面图。证明

K5有m=n·(n-1)/2=10条边,而令m≤3·n-6=9不成立。K3,3有m=3×3=9条边,而因无长度为奇数的回路则不以K3为子图,而令m≤2·n-4=8不成立。定理

平面简单图G中至少有一个顶点v0,d(v0)≤5。证明

只需要证明连通图。反证,平面简单图G所有顶点v都有d(v)>5⇒m≤3·n-6,2·m=∑v∈Gd(v)≥6·n⇒3·n≤m≤3·n-6,矛盾。11.4.1平面图相关定义同胚相关定义

如果两图G1、G2同构,或者能够通过不计次数地以度为2的顶点将边一分为二和(或)贯通度为2的顶点(顶点只有自环除外),随后令G1、G2同构,则称G1和G2在2度顶点内同构,或称图G1和G2同胚(homeomorphism)。具体说来,两图G1和G2在2度顶点内同构或G1和G2同胚指通过下文定义了切割边、贯通2度顶点两种方式达到同构,G1通过切割边而增加2度顶点得G2则称G2为G1的细分。如果图G有子图G″是图G'的细分,称G'为G的拓扑子式(拓扑子式为图子式之一,本课程不作介绍)。11.4.1平面图相关定义同胚相关定义(1)对边的切割:图G中有边e=(u,v),关联顶点u,vA.删除边e=(u,v)B.增加顶点w,增加边e1=(u,w),e2=(w,v)(2)对2度顶点的贯通:图G中有度为2的顶点u,其关联边为e1=(w,u),e2=(u,v)A.删除顶点u以及关联边e1=(w,u),e2=(u,v)B.增加边e=(w,v)11.4.1平面图相关定义如下图所示,(a)图的边e=(v1,v3)在(b)图中被顶点v4一分为二;(c)图的顶点v5在(d)图中被边e=(v2,v4)所贯穿。(b)图为(a)图的细分,(c)图为(d)图的细分。11.4.1平面图相关定义（a）（b）（c）（d）定理

库拉托夫斯基(Kuratowski)定理:一图是可平面图的充分必要条件为此图不包含与K5或K3,3同胚的子图。图K3,3和图K5为库拉托夫斯基发现的非平面图,如图所示。二者删去一边成为平面图,为极小非平面图。11.4.1平面图相关定义（a）K5（b）K3,3平面或球面上的地图可视作平面图,面对应地域,顶点对应边界交点位置,边对应区域之间的边界,允许重边和圈。一平面图可以计算得到一与之相关的图,此图值得研究与应用。对偶图平面图G=<V,E>有面R1,R2,…,Rr,由以下方法构造的图G*=<V*,E*>称为图G的对偶图(dualgraph):(1)图G任意一面Ri对应图G*唯一顶点vi*∈V*,在面Ri内部做顶点vi*,i=1,2,…,r。(2)图G的不同面Ri、Rj有公共边eij,恰有一条图G*的边ei*j=(vi*,vj*)∈E*与eij相交。vi*、vj*分别为面Ri、Rj对应图G*的顶点。11.4.2着色问题对偶图（续）(3)图当且仅当eii只为一个面Ri的边界,图G*在面Ri的对应顶点vi*有一环与边eii恰好相交于一处。易知平面图G的对偶图G*是平面连通图。如果G与G*同构,则称图G为自对偶图(self-dualgraph)。11.4.2着色问题如图所示,已知实线作平面图,求平面图的度;以虚线作平面图的对偶图。11.4.2着色问题（a）（b）如图所示,已知实线作平面图,求平面图的度;以虚线作平面图的对偶图。解

(a)图G=<V,E>,V={v1,v2,v3,v4,v5,v6},有5个由边围成的面和1个无限面:v1-v2-v3-v1,度为3;v1-v4-v3-v1,度为3;v1-v2-v5-v1,度为3;v1-v4-v5-v1,度为3;v1-v5-v1,度为2;v6-v5-v2-v3-v4-v5-v6,度为6。(b)图G=<V,E>,V={v1,v2,v3,v4,v5},有4个由边围成的面和1个无限面:v1-v2-v5-v1,度为3;v1-v4-v5-v1,度为3;v3-v4-v5-v3,度为3;v1-v1,度为1;v5-v2-v1-v1-v4-v3-v5,度为6。11.4.2着色问题如图所示,已知实线作平面图,求平面图的度;以虚线作平面图的对偶图。解（续）

左图对偶图G*=<V*,E*>,V*={u1,u2,u3,u4,u5,u6};右图对偶图G*=<V*,E*>,V*={u1,u2,u3,u4,u5}。二对偶图连通,是平面图。对偶图G*有重边当且仅当图G有两个面至少有2条公共边。11.4.2着色问题哥尼斯堡问题抽象成图为平面图G,求图G的对偶图G*。解

哥尼斯堡问题平面图G（图(a)）和对偶图G*（图(b)）如上图所示。11.4.2着色问题（a）（b）定理

平面图G任意面的度为偶数的充分必要条件为对偶图是欧拉图。证明

由对偶图作法知,平面图G任意面Ri的度对应图G之对偶图G*在Ri中顶点vi*的度;而G为平面图,则由对偶图作法知G*连通;因此由欧拉图判定充要条件为各顶点具有偶度数,有此等价结论。11.4.2着色问题定理

平面图G的对偶图为G*,G有面R1,R2,…,Rr,图G与其对偶图G*的顶点、边、面的数量分别为n、m、r和n*、m*、r*,则有r=n*、m=m*、n=r*,vi*∈G*,d(vi*)=deg(Ri),i=1,2,…,r。证明

注意到图G和其对偶图G*均为平面图,有n-m+r=2,n*-m*+r*=2,由对偶图定义知n*=r,m*=m⇒r*=n。而d(vi*)=deg(Ri)由对偶图作法显然成立。11.4.2着色问题着色问题平面图与对偶图的研究常应用于地图着色等一系列相关问题,即消耗最少的色彩种类用以区分地图G中诸多相邻区域Ri。推而广之,对一般图,与之本质相同的问题有:对众多不同时间段任务优化调度、地区广播频道分配、学校在规定时间段合理安排考试、课程等。其问题归结于对图G(或对偶图G*)顶点的着色问题。本课程只研究顶点着色问题。11.4.2着色问题图着色相关定义

无环图G=<V,E>的一个顶点着色(vertexcolouring)定义为映射c:V→S,令任意邻接顶点u、v有c(u)≠c(v)。S中元素为可用颜色,着色问题在于找到S的基数S。如果找到一最小正整数k0令图G有k0-着色,即一个顶点着色c:V→{1,2,…,k0},则称k0为图G的顶点色数(chromaticnumber),记作χ(G)。如果正整数k有χ(G)=k,则称图G为k-色的(k-chromatic);如果正整数k有χ(G)≤k,则称图G为k-可着色的(k-colourable)。着色问题只需考虑简单图。由定义易知,n阶完全图为n-着色图;G为零图的充要条件为χ(G)=1;二分图有χ(G)=2(不考虑平凡图和零图),则非平凡树有χ(G)=2。11.4.2着色问题图论中对k-着色问题的讨论由来已久,可平面图有众人熟知的“四色定理”(thefourcolourtheorem):定理

任意可平面图是4-可着色的。对这一定理有诸多讨论,本课程只考虑连通简单图,简要证明如下定理。定理

可平面图G是5-可着色的。11.4.2着色问题定理

可平面图G是5-可着色的。证明

图G顶点数n≤5时结论显然成立。数学归纳顶点数则令n=k时结论成立。则n=k+1时,由前文结论知,图G中有顶点v0,d(v0)≤5⇒G-{v0}顶点数为n=k,是5-可着色图。在G-{v0}定义一种着色后,只需确定有5-可着色映射定义v0和其邻接顶点而对图G其他顶点无影响。(1)d(v0)<5:所有邻接顶点之不同着色小于5,则可以直接选择与所有邻接顶点都不同的一种颜色。11.4.2着色问题定理

可平面图G是5-可着色的。证明（续）