第8章-几种特殊的图解析课件

第8章几种特殊的图1第8章几种特殊的图8.1欧拉图8.2哈密顿图8.3二部图8.4平面图8.5树2SevenBridgesofKönigsberg能否既不重复又不遗漏地一次相继走遍这七座桥?

3SevenBridgesofKönigsberg忽略不重要的细节忽略更多的细节研究方法——抽象从而将哥尼斯堡七桥问题抽象为一个数学问题：即经过图中每边一次且仅一次的问题。4adcbe1e3e2e4e6e5e7假设有这样的通路,该通路有一个起点和一个终点v对每一个“中间”顶点v,必有相同数目的入边和出边，因此顶点v的度数必为偶数问题：是否有经过图中每边一次且仅一次的通路？Euler’sSolution5Euler’sSolutionadcbe1e3e2e4e6e5e7假设有这样的通路,该通路有一个起点和一个终点对每一个“中间”顶点v,必有相同数目的入边和出边，因此顶点v的度数必为偶数问题：是否有经过图中每边一次且仅一次的通路？因此,最多2个顶点度数为奇数.该图中,每个顶点度数均为奇数,因此，不存在经过图中每边一次且仅一次的通路6欧拉图问题寻找走遍哥尼斯堡(KÖnigsberg)城的7座桥,且只许走过每座桥一次,最后又回到原出发点(图论源于游戏).求解1736年瑞士大数学家欧拉(LeonhardEuler)发表了关于“哥尼斯堡七桥问题”的论文(图论的第一篇论文).他指出从一点出发不重复的走遍七桥,最后又回到原来出发点是不可能的.欧拉因此被称为“图论之父”,1736年通常被称为“图论元年”.7欧拉图定义8.1欧拉通路:经过所有顶点且每条边恰好经过一次的通路欧拉回路:经过所有顶点且每条边恰好经过一次的回路欧拉图:有欧拉回路的图说明：上述定义对无向图和有向图都适用规定平凡图为欧拉图欧拉通路是简单通路,欧拉回路是简单回路8欧拉图判别定理定理8.1

无向图G具有欧拉回路当且仅当G是连通的且无奇度顶点.无向图G具有欧拉通路、但没有欧拉回路当且仅当G是连通的且有2个奇度顶点,其余顶点均为偶度数的.这2个奇度顶点是每条欧拉通路的端点.推论无向图G是欧拉图当且仅当G是连通的且无奇度顶点9实例(1)没有欧拉回路和欧拉通路,不是欧拉图.(2)没有欧拉回路,有欧拉通路,不是欧拉图.(3)没有欧拉回路,有欧拉通路,不是欧拉图.(4)有欧拉回路,是欧拉图.

abcdabcdabcdefabcdefghi10欧拉图判别定理(续)定理8.2

有向图D有欧拉回路当且仅当D是连通的且所有顶点的入度等于出度.有向图D有欧拉通路、但没有欧拉回路当且仅当D是连通的且有一个顶点的入度比出度大1、一个顶点的入度比出度小1,其余的顶点的入度等于出度.推论有向图D是欧拉图当且仅当D是连通的且所有顶点的入度等于出度.11实例(1)没有欧拉回路和欧拉通路,不是欧拉图.(2)没有欧拉回路,有欧拉通路,不是欧拉图.(3)有欧拉回路,是欧拉图.

abcdbccbadda12哈密顿图定义8.2哈密顿通路:经过图中所有顶点一次且仅一次的通路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.说明：哈密顿通路是初级通路哈密顿回路是初级回路有哈密顿通路不一定有哈密顿回路13周游世界问题(W.Hamilton,1859年)14存在哈密顿回路(通路)的充分条件定理8.3设G是n(n3)阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n1,则G中存在哈密顿通路;若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路,即G为哈密顿图.推论设G是n(n3)阶无向简单图,若δ(G)n/2,则G是哈密顿图.15应用例一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？解:可以.作无向图,每人是一个顶点,2人之间有边他们是朋友.由已知，图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。16应用例有7个人,A会讲英语,B会讲英语和汉语,C会讲英语、意大利语和俄语,D会讲日语和汉语,E会讲德语和意大利语,F会讲法语、日语和俄语,G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?解作无向图,每人是一个顶点,2人之间有边他们有共同的语言.ABCDEFGACEGFDBA是一条哈密顿回路,按此顺序就坐即可.17应用例考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是存在的。

证明：设G为具有7个结点的图，每个结点对应于一门课程考试，如果任两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边.因为每个教师所任课程数不超过4，故每个结点的度数至少是3，因此任两个结点的度数之和至少是6，故G总是存在一条哈密尔顿通路，它对应于一个七门考试课程的一个适当的安排。18二部图定义8.3

设无向图G=<V,E>,若能将V分成V1和V2

使得V1V2=V,V1V2=,且G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为<V1,V2,E>,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点均与V2中每个顶点都相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.

K23K3319非二部图非二部图定理8.4

无向图G=(V,

E)为二部图的充要条件是G的所有回路长度均为偶数。

20平面图与非平面图定义8.4

如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.例如

下图中(1)~(4)是平面图,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面图.218.5.1无向树无向树的定义及其性质生成树最小生成树8.5.2根树及其应用根树及其分类最优树与哈夫曼算法最佳前缀码树228.5.1

无向树无向树的定义及其性质生成树最小生成树最短通路问题23真实的树变换

计算机科学中一种非常重要的图叫作树抽象的树24无向树的定义无向树:连通无回路的无向图平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数2的顶点例如G1G2abcdefgh25无向树的性质定理8.5

设G=<V,E>是n阶m条边的无向图,下面各命题是等价的：(1)G是树(连通无回路);(2)G中任意两个顶点之间存在惟一的路径;(3)G是连通的且m=n1;(4)G中无回路且m=n1;(5)G中无回路,但在任何两个不相邻的顶点之间加一条边所得图中有惟一的一条初级回路.(6)G是连通的，但删去任意一条边，则变成不连通图。abcdefgh26定理8.5的证明(1)(2)由连通性,任意2个顶点之间有一条路径.又,假设某2个顶点之间有2条路径,则这2条路径可组合成一条回路,与树的定义矛盾.(2)(3)显然连通,要证m=n1.对n作归纳证明.当n=1时,显然m=0,结论成立.假设当nk(k1)时结论成立,考虑n=k+1.任取一条边e=(u,v),它是u,v之间惟一的通路,删去e,G被分成2个连通分支,设它们分别有n1,n2个顶点和m1,m2条边,n1k,

n2k.由归纳假设,m1=n11,m2=n21,得m=m1+m2+1=n1.27定理8.5的证明(续)(3)(4)假设有回路,任取一个回路,删去回路中的一条边,所得图仍是连通的.重复这个做法,直到没有回路为止,得到一棵树,它有n个顶点mr条边,r>0.由(1)(2)(3),得mr

=n1,矛盾.(4)(1)只需证G连通.假设G不连通,有p(p>1)个连通分支.设第k个连通分支有nk个顶点和mk条边,由(1)(2)(3),mk=nk1.得到m=np,矛盾.28定理8.5的证明(续)(1)(5)由(1)(2),任意2个不相邻的顶点之间有一条惟一的路径,故在这2个顶点之间添加一条新边,必得到一条惟一的初级回路.(5)(6)首先,任意2个不相邻的顶点之间都有一条通路,否则在它们之间添加一条新边不可能构成回路,故G连通.其次,若删去一条边G仍是连通的,这条边必在一条回路上,与G中无回路矛盾.(6)(1)G中无回路,否则删去回路上任意条边,G仍连通.29无向树的性质(续)定理8.6

非平凡的无向树至少有两片树叶证设有n(n>1)个顶点,x片树叶,由握手定理和定理8.5,有

解得x2.30实例例已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数,并画出满足要求的非同构的无向树.

解设有x片树叶,树的顶点数为1+2+x=3+x,树的边数为(3+x)-1=2+x,2(2+x)=13+22+x解得x=3,故T有3片树叶.31生成树定义8.5

设G是无向连通图,若G的生成子图T是一棵树,则称T是G的生成树.G在T中的边称作T的树枝,不在T中的边称作T的弦.例如图G2中结点和黑边构成G的生成树.黑边为树枝,红边为弦.GG1G232生成树的存在性定理8.7

任何无向连通图都有生成树.证用破圈法.若图中无圈,则图本身就是自己的生成树.否则删去圈上的任一条边,不破坏连通性,重复进行直到无圈为止,得到图的一棵生成树.推论

设n阶无向连通图有m条边,则mn1.uvaebcd33最小生成树图G的每一条边e附加一个实数w(e),称作边e的权.图G连同附加在边上的权称作带权图,记作G=<V,E,W>.设H是G的子图,H所有边的权的和称作H的权,记作W(H).GW(G)=42G1W(G1)=19G2W(G2)=2534最小生成树最小生成树:带权图中权最小的生成树避圈法(Kruskal)(1)将所有非环边按权从小到大排列,

设为e1,e2,…,em(2)令T

=(3)fork=1tomdo若ek与T中的边不构成回路,则将ek加入T中35实例例

求图的一棵最小生成树W(T)=1+2+3+3+4+7+18=3836G的最小生成树可能不唯一,但G的不同最小生成树权的值一样.例求图的一棵最小生成树T及其权W(T)W(T1)=15W(T2)=1537步骤一步骤三步骤四步骤二步骤五38例求图的一棵最小生成树T及其权W(T)W(T1)=18W(T2)=1839定理8.8

对赋权图G(n,m),用Kruskal算法得到的G的子图T*必是最优树。证明：假设T*不是最优树,令k是G的最优树与T*有共同边的数目中的最大值.令T为最优树,与T*有k条共同边的最优树.T≠T*ek+1:ek+1

E(T)且ek+1∈E(T*)由定理8.5(5)知,T+ek+1中含唯一的回路C,C至少有条边ek’不在T*中.做T’=(T+ek+1)–ek’,于是T’是有n–1条边的连通图.T’是G的生成树.显然,w(T’)=w(T)+w(ek+1)–w(ek’).由算法知,w(ek+1)w(ek’).这说明T’也是G的最优树.但T’与T*有k+1条共同边.矛盾.故T*是最优树.40普林法(Prim)首先选择带最小权的边，把它放进生成树里。相继向树里添加带最小权的边，这些边与已在树里的顶相关联，并且不与已在树里的边形成简单回路。当已经添加了n-1条边时停止。41(旧金山,

丹佛)$900(旧金山,芝加哥)$1200(旧金山,亚特兰大)$2200(旧金山,纽约)$2000(丹佛,芝加哥)$1300(丹佛,亚特兰大)$1400(丹佛,纽约)$1600(芝加哥,亚特兰大)$700(芝加哥,纽约)$1000(亚特兰大,纽约)$800例一家公司计划建立它的五个计算机中心的通信网络。可以用租用的电话线连接这些中心的任何一对。应当建立哪些连接，以便保证在任何两个计算机中心之间都有通路，使得网络的总成本是最小的？42旧金山丹佛亚特兰大纽约芝加哥2000120010009001300160014002200800700可以用带权图为这个问题建模，其中顶点表示计算机中心，边表示可能租用的电话线，边上的权是边所表示的电话线的月租费。通过找出一棵最小生成树，就可以解决这个问题。43旧金山丹佛亚特兰大纽约芝加哥2000120010009001300160014002200800700(旧金山,

丹佛)$900(旧金山,芝加哥)$1200(芝加哥,亚特兰大)$700(亚特兰大,纽约)$800总费用:$3600900+1200+700+800=360044离散建模现实世界问题域问题域解离散世界离散模型离散模型解转换(抽象化)逆转换(语义化)离散建模示意图求解当数学模型建立在有限集或可列集之上时,此种模型的建立称离散建模.由于计算机科学是一种以离散对象为研究目标的学科,因此,离散建模特别适合于计算机科学领域.45每台计算机是一个顶点.如果两台计算机有直接连接，则对应顶点有一条边如何找到两台计算机之间的最短路由？（最短路径问题）如何找到连接所有计算机的代价最小的网络?（最小生成树问题）如何在两台计算机之间传输最大量的信息?（网络最大流问题）应用46旧金山丹佛亚特兰大纽约芝加哥25345959571855860191349760722最短通路问题洛杉矶2451908迈阿密834波士顿6061090为航线系统建模的带权图:里程在波士顿与洛杉矶之间以空中距离计算的最短通路是什么？47旧金山丹佛亚特兰大纽约芝加哥4:051:302:202:552:100:501:151:551:50最短通路问题洛杉矶3:502:10迈阿密2:00波士顿1:402:45为航线系统建模的带权图:飞行时间在波士顿与洛杉矶什么样的航班组合的总飞行时间最短？48旧金山丹佛亚特兰大纽约芝加哥$129$69$89$99$79$39$39$79$59最短通路问题洛杉矶$129$69迈阿密$89波士顿$99$99在波士顿与洛杉矶之间以空中距离计算的最短通路是什么？为航线系统建模的带权图:票价49旧金山丹佛达拉斯纽约芝加哥13729571855860191349722最短通路问题洛杉矶6459081376波士顿1235为计算机网络建模的带权图:距离连接旧金山的计算机与纽约的计算机，哪一段电话线有最短的总距离？79850旧金山丹佛达拉斯纽约芝加哥6秒4秒5秒3秒2秒3秒4秒最短通路问题洛杉矶4秒6秒7秒波士顿5秒为计算机网络建模的带权图:响应时间哪一段电话线给出旧金山与纽约之间通信的最短响应时间？5秒51旧金山丹佛达拉斯纽约芝加哥$1200$1000$1500$900$300$400$700最短通路问题洛杉矶$600$500$1400波士顿$1100为计算机网络建模的带权图:月租费连接旧金山的计算机与纽约的计算机所需要的最便宜的一组电话线是什么？$80052图G带有顶点a=v0,v1,...,vn=z和权w(vi,vj),

其中若(vi,vj)不是G中的边,则w(vi,vj)=∞迪克斯屈拉算法(现在初始化标记,使得a的标记为0而所有其余标记为∞,而S是空集合)for

i=1to

n

L(vi)=∞L(a)=0S=abcde5432z8210610∞∞∞∞∞535428210613∞ea0c2(a)d∞z∞4(a)b迪克斯屈拉算法(续)While

uS{u=不属于S的L(u)最小的一个顶点;S=S∪{u}For

所有不属于S的顶点v

if

L(u)+w(u,v)<L(v)

then

L(v)=L(u)+w(u,v)(这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记)}/*L(z)=从a到z的最短通路长度*/54542821061312(a,c)ea0c2(a)d10(a,c)z∞3(a,c)b迪克斯屈拉算法(续)While

uS{u=不属于S的L(u)最小的一个顶点;S=S∪{u}For

所有不属于S的顶点v

if

L(u)+w(u,v)<L(v)

then

L(v)=L(u)+w(u,v)(这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记)}/*L(z)=从a到z的最短通路长度*/55542821061312(a,c)ea0c2(a)d8(a,c,b)z∞3(a,c)b5428210613z5428210613a0c2(a)3(a,c)b5428210613ezc2(a)3(a,c)ba0d8(a,c,b)10(a,c,b,d)14(a,c,b,d)d8(a,c,b)e10(a,c,b,d)13(a,c,b,d,e)a0z13(a,c,b,d,e)3(a,c)bc2(a)e10(a,c,b,d)d8(a,c,b)56旧金山丹佛达拉斯纽约芝加哥$1200$1000$1500$900$300$400$700洛杉矶$600$500$1400波士顿$1100为计算机网络建模的带权图:月租费连接旧金山的计算机与纽约的计算机所需要的最便宜的一组电话线是什么？$80057旧金山(a)洛杉矶(b)丹佛(c)达拉斯(d)芝加哥(e)纽约(f)波士顿(g)0∞∞∞∞∞∞400(a)1000(a)∞1500(a)∞∞1000(a)1500(a,b)1500(a)∞∞1500(a,b)1500(a)∞∞1500(a)2700(a,b,d)∞2200(a,e)2400(a,e)旧金山->芝加哥->纽约588.5.2

根树及其应用根树及其分类最优树与哈夫曼算法最佳前缀码59根树的定义有向树:略去方向后为无向树的有向图根树:有一个顶点入度为0,其余的入度均为1的非平凡的有向树树根:有向树中入度为0的顶点树叶:有向树中入度为1,出度为0的顶点内点:有向树中入度为1,出度大于0的顶点分支点:树根与内点的总称顶点v的层数:从树根到v的通路长度树高:有向树中顶点的最大层数60实例根树的画法:树根放上方,省去所有有向边上的箭头右图中

a是树根

b,e,f,h,i是树叶

c,d,g是内点

a,c,d,g是分支点

a为0层;1层有b,c;2层有d,e,f;3层有g,h;4层有i.

树高为461家族树把根树看作一棵家族树:若顶点a邻接到顶点b,则称b是a的儿子,a是b的父亲若b和c为同一个顶点的儿子,则称b和c是兄弟若ab且a可达b,则称a是b的祖先,b是a的后代r元树:根树的每个分支点至多有r个儿子62最优2元树定义8.6设2元树T有t片树叶v1,v2,…,vt,树叶的权分别为w1,w2,…,wt,称为T的权,记作W(T),其中l(vi)是vi的层数.在所有有t片树叶,带权w1,w2,…,wt的2元树中,权最小的2元树称为最优2元树例如134561345613456W(T1)=63+33+42+52+12=47W(T2)=54W(T3)=4363求最优2元树的算法哈夫曼(Huffman)算法给定实数w1,w2,…,wt

①作t片树叶,分别以w1,w2,…,wt为权②在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和③重复②,直到只有1个入度为0的顶点为止W(T)等于所有分支点的权之和64实例例求以1,3,4,5,6为权的最优2元树,并计算它的权解步骤一作5片树叶,分别以1,3,4,5,6为权13456步骤二134456在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和65步骤三134458步骤四13448611566651344861119步骤五W(T)=4+8+11+19=42W(T)=1×3+3×3+4×2+5×2+6×2=426751344861119W(T)=42最优2元树可能不唯一,但不同最优2元树权的值一样.4134596191068最佳前缀码定义8.7

设=12…n-1n是长度为n的符号串,12…k称作的长度为k的前缀,k=1,2,…,n1.

若非空字符串1,2,…,m中任何两个互不为前缀,则称{1,2,…,m}为前缀码只出现两个符号(如0与1)的前缀码称作2元前缀码例如

{0,10,110,1111},{10,01,001,110}是2元前缀码{0,