1、1第8章 几种特殊的图2第8章 几种特殊的图n8.1 欧拉图欧拉图n8.2 哈密顿图哈密顿图n8.3 二部图二部图n8.4 平面图平面图n8.5 树树3Seven Bridges of Knigsberg能否既不重复又不遗漏地一次相继走遍这七座桥能否既不重复又不遗漏地一次相继走遍这七座桥? 4Seven Bridges of Knigsberg忽略不重要的细节忽略不重要的细节忽略更多的细节忽略更多的细节研究方法研究方法抽象抽象从而将哥尼斯堡七桥问题抽象为一个数学问题：即经过图从而将哥尼斯堡七桥问题抽象为一个数学问题：即经过图中每边一次且仅一次的问题。中每边一次且仅一次的问题。5adcbe1e3
2、e2e4e6e5e7假设有这样的通路假设有这样的通路, , 该通路有一个起点和一个终点该通路有一个起点和一个终点v对每一个对每一个“中间中间”顶点顶点v,v,必有相同数目的入边和出边，因此顶点必有相同数目的入边和出边，因此顶点v v的的度数必为偶数度数必为偶数问题：是否有经过图中每边一次且仅一次的通路？问题：是否有经过图中每边一次且仅一次的通路？Eulers Solution6Eulers Solutionadcbe1e3e2e4e6e5e7假设有这样的通路假设有这样的通路, , 该通路有一个起点和一个终点该通路有一个起点和一个终点对每一个对每一个“中间中间”顶点顶点v,v,必有相同数目的入边
3、和出边，因此顶点必有相同数目的入边和出边，因此顶点v v的的度数必为偶数度数必为偶数问题：是否有经过图中每边一次且仅一次的通路？问题：是否有经过图中每边一次且仅一次的通路？因此因此, , 最多最多 2 2个顶点度数为奇数个顶点度数为奇数. .该图中该图中, ,每个顶点度数均为奇数每个顶点度数均为奇数, ,因此，不存在经过图中每边一次因此，不存在经过图中每边一次且仅一次的通路且仅一次的通路7欧拉图欧拉图n问题问题q寻找走遍哥尼斯堡寻找走遍哥尼斯堡(Knigsberg)城的城的7座桥座桥, 且只许走且只许走过每座桥一次过每座桥一次, 最后又回到原出发点最后又回到原出发点(图论源于游戏图论源于游戏)
4、.n求解求解q1736年瑞士大数学家欧拉年瑞士大数学家欧拉(Leonhard Euler)发表了关发表了关于于“哥尼斯堡七桥问题哥尼斯堡七桥问题”的论文的论文(图论的第一篇论文图论的第一篇论文). 他指出从一点出发不重复的走遍七桥他指出从一点出发不重复的走遍七桥, 最后又回到原来最后又回到原来出发点是不可能的出发点是不可能的.n欧拉因此被称为欧拉因此被称为“图论之父图论之父”, 1736年通常被称为年通常被称为“图论图论元年元年”.8欧拉图欧拉图定义定义8.1欧拉通路欧拉通路:经过所有顶点且每条边恰好经过一次的通路经过所有顶点且每条边恰好经过一次的通路 欧拉回路欧拉回路:经过所有顶点且每条边恰
5、好经过一次的回路经过所有顶点且每条边恰好经过一次的回路欧拉图欧拉图:有欧拉回路的图有欧拉回路的图说明：说明：上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用规定平凡图为欧拉图规定平凡图为欧拉图欧拉通路是简单通路欧拉通路是简单通路, 欧拉回路是简单回路欧拉回路是简单回路9欧拉图判别定理欧拉图判别定理定理定理8.1 无向图无向图G具有欧拉回路当且仅当具有欧拉回路当且仅当G是连通的且无是连通的且无奇度顶点奇度顶点. 无向图无向图G具有欧拉通路、但没有欧拉回路当且仅当具有欧拉通路、但没有欧拉回路当且仅当G是连是连通的且有通的且有2个奇度顶点个奇度顶点, 其余顶点均为偶度数的其余顶点均为偶度
6、数的. 这这2个奇个奇度顶点是每条欧拉通路的端点度顶点是每条欧拉通路的端点.推论推论 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通的且无奇度顶点是连通的且无奇度顶点10实例实例(1)没有欧拉回路和欧拉通路没有欧拉回路和欧拉通路, 不是欧拉图不是欧拉图.(2)没有欧拉回路没有欧拉回路, 有欧拉通路有欧拉通路, 不是欧拉图不是欧拉图.(3)没有欧拉回路没有欧拉回路, 有欧拉通路有欧拉通路, 不是欧拉图不是欧拉图.(4)有欧拉回路有欧拉回路, 是欧拉图是欧拉图. abcdabcdabcdefabcdefghi11欧拉图判别定理欧拉图判别定理(续续)定理定理8.2 有向图有向图D有欧拉回路当
7、且仅当有欧拉回路当且仅当D是连通的且所有是连通的且所有顶点的入度等于出度顶点的入度等于出度.有向图有向图D有欧拉通路、但没有欧拉回路当且仅当有欧拉通路、但没有欧拉回路当且仅当D是连通是连通的且有一个顶点的入度比出度大的且有一个顶点的入度比出度大1、一个顶点的入度比出、一个顶点的入度比出度小度小1, 其余的顶点的入度等于出度其余的顶点的入度等于出度.推论推论 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是连通的且所有顶点的是连通的且所有顶点的入度等于出度入度等于出度.12实例实例(1)没有欧拉回路和欧拉通路没有欧拉回路和欧拉通路, 不是欧拉图不是欧拉图.(2)没有欧拉回路没有欧拉回路, 有欧
8、拉通路有欧拉通路, 不是欧拉图不是欧拉图.(3)有欧拉回路有欧拉回路, 是欧拉图是欧拉图. abcdbccbadda13哈密顿图哈密顿图定义定义8.2哈密顿通路哈密顿通路: : 经过图中所有顶点一次且仅一次的通路经过图中所有顶点一次且仅一次的通路. .哈密顿回路哈密顿回路: : 经过图中所有顶点一次且仅一次的回路经过图中所有顶点一次且仅一次的回路. .哈密顿图哈密顿图: : 具有哈密顿回路的图具有哈密顿回路的图. .说明：说明：哈密顿通路是初级通路哈密顿通路是初级通路哈密顿回路是初级回路哈密顿回路是初级回路有哈密顿通路不一定有哈密顿回路有哈密顿通路不一定有哈密顿回路14周游世界问题周游世界问题
9、(W.Hamilton, 1859年年)15存在哈密顿回路存在哈密顿回路(通路通路)的充分条件的充分条件定理定理8.3 设设G是是n(n 3)阶无向简单图阶无向简单图, 若任意两个不相邻若任意两个不相邻的顶点的度数之和大于等于的顶点的度数之和大于等于n 1, 则则G中存在哈密顿通路中存在哈密顿通路;若任意两个不相邻的顶点的度数之和大于等于若任意两个不相邻的顶点的度数之和大于等于n, 则则G中中存在哈密顿回路存在哈密顿回路, 即即G为哈密顿图为哈密顿图.推论推论 设设G是是n(n 3)阶无向简单图阶无向简单图, 若若(G) n/2, 则则G是哈是哈密顿图密顿图.16应用应用例例一次会议有一次会议
10、有20人参加，其中每个人都在其中有不下人参加，其中每个人都在其中有不下10个个朋友。这朋友。这20人围成一圆桌入席。有没有可能使任意相邻人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？而坐的两个人都是朋友？为什么？解解:可以可以.作无向图作无向图, 每人是一个顶点每人是一个顶点, 2人之间有边人之间有边他们是朋友他们是朋友.由已知，图中每个顶点的度数都大于等于由已知，图中每个顶点的度数都大于等于10。即图中任。即图中任两个不相邻的顶点的度数大于等于两个不相邻的顶点的度数大于等于20，即顶点数。故这，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取个图是一个哈密
11、尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。的人的座位，就可满足要求。17应用应用例例 有有7个人个人, A会讲英语会讲英语, B会讲英语和汉语会讲英语和汉语, C会讲英语、会讲英语、意大利语和俄语意大利语和俄语, D会讲日语和汉语会讲日语和汉语, E会讲德语和意大利会讲德语和意大利语语, F会讲法语、日语和俄语会讲法语、日语和俄语, G会讲法语和德语会讲法语和德语. 问能否将问能否将他们沿圆桌安排就坐成一圈他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人使得每个人都能与两旁的人
12、交谈交谈?解解作无向图作无向图, 每人是一个顶点每人是一个顶点, 2人之间有边人之间有边他们有共同的语言他们有共同的语言.ABCDEFGACEGFDBA是一条哈密顿回路是一条哈密顿回路,按此顺序就坐即可按此顺序就坐即可.18应用应用例例 考虑在七天内安排七门课程的考试，使得同一位教师考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证明如果没所任的两门课程考试不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总有教师担任多于四门课程，则符合上述要求的考试安排总是存在的。是存在的。 证明：设证明：设G为具有为具有7个结点的图，每个
13、结点对应于一门课个结点的图，每个结点对应于一门课程考试，如果任两个结点对应的课程考试是由不同教师担程考试，如果任两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边任的，那么这两个结点之间有一条边.因为每个教师所任因为每个教师所任课程数不超过课程数不超过4，故每个结点的度数至少是，故每个结点的度数至少是3，因此任两，因此任两个结点的度数之和至少是个结点的度数之和至少是6，故，故G总是存在一条哈密尔顿总是存在一条哈密尔顿通路，它对应于一个七门考试课程的一个适当的安排。通路，它对应于一个七门考试课程的一个适当的安排。19二部图二部图定义定义8.3 设无向图设无向图 G=, 若能将若
14、能将V 分成分成V1 和和 V2 使得使得V1 V2=V, V1 V2=, 且且G中的每条边的两个端点都一个中的每条边的两个端点都一个属于属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图, 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 又若又若G是简单图是简单图, 且且V1中每个顶中每个顶点均与点均与V2中每个顶点都相邻中每个顶点都相邻, 则称则称G为为完全二部图完全二部图, 记为记为Kr,s, 其中其中r=|V1|, s=|V2|. K23K3320非二部图非二部图非二部图非二部图定理定理8.4 无向图无向图G=(V, E)为二部图的充要条件是为二部图的充要条
15、件是G的所有的所有回路长度均为偶数。回路长度均为偶数。 21平面图与非平面图平面图与非平面图定义定义8.4 如果能将图如果能将图G除顶点外边不相交地画在平面上除顶点外边不相交地画在平面上, 则称则称G是是平面图平面图. 这个画出的无边相交的图称作这个画出的无边相交的图称作G的的平面平面嵌入嵌入. 没有平面嵌入的图称作没有平面嵌入的图称作非平面图非平面图.例如例如 下图中下图中(1)(4)是平面图是平面图, (2)是是(1)的平面嵌入，的平面嵌入， (4)是是(3)的平面嵌入的平面嵌入. (5)是非平面图是非平面图.22n8.5.1 无向树无向树q无向树的定义及其性质无向树的定义及其性质q生成树
16、生成树q最小生成树最小生成树n8.5.2 根树及其应用根树及其应用q根树及其分类根树及其分类q最优树与哈夫曼算法最优树与哈夫曼算法q最佳前缀码最佳前缀码树238.5.1 无向树n无向树的定义及其性质无向树的定义及其性质n生成树生成树n最小生成树最小生成树n最短通路问题最短通路问题24真实的树真实的树变换变换 计算机科学中一种非常重要的图叫作树计算机科学中一种非常重要的图叫作树抽象的树抽象的树25无向树的定义无向树的定义无向树无向树: 连通无回路的无向图连通无回路的无向图平凡树平凡树: 平凡图平凡图森林森林: 每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图树叶树叶: 树中度
17、数为树中度数为1的顶点的顶点分支点分支点: 树中度数树中度数 2的顶点的顶点例如例如G1G2abcdefgh26无向树的性质无向树的性质定理定理8.5 设设G=是是n阶阶m条边的无向图条边的无向图, 下面各命题是等价的：下面各命题是等价的：(1) G是树是树(连通无回路连通无回路);(2) G中任意两个顶点之间存在惟一的路径中任意两个顶点之间存在惟一的路径;(3) G是连通的且是连通的且m=n 1;(4) G中无回路且中无回路且m=n 1;(5) G中无回路中无回路, 但在任何两个不相邻的顶点之间加一条边但在任何两个不相邻的顶点之间加一条边 所得图中有惟一的一条初级回路所得图中有惟一的一条初级
18、回路.(6) G是连通的，但删去任意一条边，则变成不连通图。是连通的，但删去任意一条边，则变成不连通图。abcdefgh27定理定理8.5的证明的证明(1)(2) 由连通性由连通性, 任意任意2个顶点之间有一条路径个顶点之间有一条路径. 又又, 假设假设某某2个顶点之间有个顶点之间有2条路径条路径, 则这则这2条路径可组合成一条回条路径可组合成一条回路路, 与树的定义矛盾与树的定义矛盾.(2)(3) 显然连通显然连通, 要证要证m=n 1. 对对n作归纳证明作归纳证明. 当当n=1时时, 显然显然m=0, 结论成立结论成立. 假设当假设当n k(k 1)时结论成立时结论成立, 考虑考虑n=k+
19、1. 任取一条边任取一条边e=(u,v), 它是它是u,v之间惟一的通路之间惟一的通路, 删去删去e, G被分成被分成2个连通分个连通分支支, 设它们分别有设它们分别有n1, n2个顶点和个顶点和m1, m2条边条边, n1 k, n2 k. 由归纳假设由归纳假设, m1=n1 1, m2=n2 1, 得得m= m1+m2+1= n 1.28定理定理8.5的证明的证明(续续)(3)(4) 假设有回路假设有回路, 任取一个回路任取一个回路, 删去回路中的一条边删去回路中的一条边, 所得图仍是连通的所得图仍是连通的. 重复这个做法重复这个做法, 直到没有回路为止直到没有回路为止, 得得到一棵树到一
20、棵树, 它有它有n个个顶点顶点m r条边条边, r0. 由由(1)(2)(3), 得得m r =n 1, 矛盾矛盾.(4)(1) 只需证只需证G连通连通. 假设假设G不连通不连通, 有有p(p1)个连通分支个连通分支.设第设第k个连通分支有个连通分支有nk个顶点和个顶点和mk条边条边, 由由(1)(2)(3),mk= nk 1. 得到得到m= n p, 矛盾矛盾.29定理定理8.5的证明的证明(续续)(1)(5) 由由(1)(2), 任意任意2个不相邻的顶点之间有一条惟个不相邻的顶点之间有一条惟一的路径一的路径, 故在这故在这2个顶点之间添加一条新边个顶点之间添加一条新边, 必得到一条必得到一
21、条惟一的初级回路惟一的初级回路.(5)(6) 首先首先, 任意任意2个不相邻的顶点之间都有一条通路个不相邻的顶点之间都有一条通路, 否则在它们之间添加一条新边不可能构成回路否则在它们之间添加一条新边不可能构成回路, 故故G连通连通.其次其次, 若删去一条边若删去一条边G仍是连通的仍是连通的, 这条边必在一条回路这条边必在一条回路上上,与与G中无回路矛盾中无回路矛盾.(6)(1) G中无回路中无回路, 否则删去回路上任意条边否则删去回路上任意条边, G仍连通仍连通.30无向树的性质无向树的性质(续续)定理定理8.6 非平凡的无向树至少有两片树叶非平凡的无向树至少有两片树叶 证证 设有设有n(n1
22、)个顶点个顶点, x片树叶片树叶, 由握手定理和定理由握手定理和定理8.5, 有有 解得解得 x 2.)(2)()1(2xnxvdni 31实例实例例例 已知无向树已知无向树T中中, 有有1个个3度顶点度顶点, 2个个2度顶点度顶点, 其余顶其余顶点全是树叶点全是树叶. 试求树叶数试求树叶数, 并画出满足要求的非同构的无并画出满足要求的非同构的无向树向树. 解解 设有设有x片树叶片树叶,树的顶点数为树的顶点数为1+2+x=3+x,树的边数为树的边数为(3+x)-1=2+x,2 (2+x)=1 3+2 2+x解得解得x=3, 故故T有有3片树叶片树叶.32生成树生成树定义定义8.5 设设G是无向
23、连通图是无向连通图, 若若G的生成子图的生成子图T是一棵树是一棵树, 则则称称T是是G的的生成树生成树. G在在T中的边称作中的边称作T的的树枝树枝,不在不在T中的边中的边称作称作T的的弦弦. 例如例如 图图G2中结点和黑边构成中结点和黑边构成G的生成树的生成树.黑边为树枝黑边为树枝, 红红边为弦边为弦.GG1G233生成树的存在性生成树的存在性定理定理8.7 任何无向连通图都有生成树任何无向连通图都有生成树.证证 用破圈法用破圈法. 若图中无圈若图中无圈, 则图本身就是自己的生成树则图本身就是自己的生成树. 否则否则删去圈上的任一条边删去圈上的任一条边, 不破坏连通性不破坏连通性, 重复进行
24、直到重复进行直到无圈为止无圈为止, 得到图的一棵生成树得到图的一棵生成树.推论推论 设设n阶无向连通图有阶无向连通图有m条边条边, 则则m n 1. uvaebcd34最小生成树最小生成树图图G的每一条边的每一条边e附加一个实数附加一个实数w(e), 称作称作边边e的的权权. 图图G连连同附加在边上的权称作同附加在边上的权称作带权图带权图, 记作记作G=. 设设H是是G的子图的子图, H所有边的权的和称作所有边的权的和称作H的权的权, 记作记作W(H). GW(G)=42 G1W(G1)=19 G2W(G2)=2535最小生成树最小生成树最小生成树最小生成树: 带权图中权最小的生成树带权图中权
25、最小的生成树避圈法避圈法 (Kruskal)(1) 将所有非环边按权从小到大排列将所有非环边按权从小到大排列, 设为设为e1, e2, , em(2) 令令T = (3) for k=1 to m do 若若ek与与T 中的边不构成回路中的边不构成回路, 则将则将ek加入加入T 中中36实例实例例例 求图的一棵最小生成树求图的一棵最小生成树W(T)=1+2+3+3+4+7+18=3837(1)6643215555fabcde(1)6643215555fabcdeG的最小生成树可能不唯一的最小生成树可能不唯一, 但但G的不同最小生成树权的值一样的不同最小生成树权的值一样. .例例 求图的一棵最小
26、生成树求图的一棵最小生成树T及其权及其权W(T)W(T1)=15W(T2)=1538(1)6643215555fabcdecdefba123cdefba1234cdefba1cdefba12步骤一步骤一步骤三步骤三步骤四步骤四步骤二步骤二cdefba12354步骤五步骤五39(2)987764321105abcdef(2)987764321105abcdef例例 求图的一棵最小生成树求图的一棵最小生成树T及其权及其权W(T)W(T1)=18W(T2)=1840定理定理8.8 对赋权图对赋权图G(n,m) , 用用Kruskal算法得到的算法得到的G的子图的子图T*必是最优树。必是最优树。证明：
27、证明：假设假设T*不是最优树不是最优树, 令令k是是G的最优树与的最优树与T*有共同边的有共同边的数目中的数目中的最大值最大值. 令令T为最优树为最优树, 与与T*有有k条共同边的最优树条共同边的最优树. TT* ek+1 : ek+1 E(T)且且ek+1E(T*)由定理由定理8.5(5)知知, T+ ek+1中含唯一的回路中含唯一的回路C, C至少有条边至少有条边ek不不在在T*中中. 做做T= (T+ek+1) ek , 于是于是T是有是有n1条边的连通图条边的连通图.T是是G的生成树的生成树. 显然显然, w(T)=w(T)+w(ek+1) w(ek). 由算法知由算法知, w(ek+
28、1) w(ek) . 这说明这说明T也是也是G的最优树的最优树. 但但T与与T*有有k+1条条共同边共同边. 矛盾矛盾. 故故T*是最优树是最优树.41普林法普林法 (Prim)首先选择带最小权的边，把它放进生成树里。首先选择带最小权的边，把它放进生成树里。相继向树里添加带最小权的边，这些边与已在树里的顶相相继向树里添加带最小权的边，这些边与已在树里的顶相关联，并且不与已在树里的边形成简单回路。关联，并且不与已在树里的边形成简单回路。当已经添加了当已经添加了n-1条边时停止。条边时停止。(1)6643215555fabcde(1)6643215555fabcde42(旧金山旧金山, 丹佛丹佛)
29、 $900(旧金山旧金山, 芝加哥芝加哥) $1200(旧金山旧金山, 亚特兰大亚特兰大) $2200(旧金山旧金山, 纽约纽约) $2000(丹佛丹佛, 芝加哥芝加哥) $1300(丹佛丹佛, 亚特兰大亚特兰大) $1400(丹佛丹佛, 纽约纽约) $1600(芝加哥芝加哥, 亚特兰大亚特兰大) $700(芝加哥芝加哥, 纽约纽约) $1000(亚特兰大亚特兰大, 纽约纽约) $800例例 一家公司计划建立它的五个计算机中心的通信网络。可一家公司计划建立它的五个计算机中心的通信网络。可以用租用的电话线连接这些中心的任何一对。应当建立哪以用租用的电话线连接这些中心的任何一对。应当建立哪些连接，
30、以便保证在任何两个计算机中心之间都有通路，些连接，以便保证在任何两个计算机中心之间都有通路，使得网络的总成本是最小的？使得网络的总成本是最小的？43旧金山旧金山丹佛丹佛亚特兰大亚特兰大纽约纽约芝加哥芝加哥2000120010009001300160014002200800700可以用带权图为这个问题建模，其中顶点表示计算机中心，可以用带权图为这个问题建模，其中顶点表示计算机中心，边表示可能租用的电话线，边上的权是边所表示的电话线的边表示可能租用的电话线，边上的权是边所表示的电话线的月租费。通过找出一棵最小生成树，就可以解决这个问题。月租费。通过找出一棵最小生成树，就可以解决这个问题。44旧金山
31、旧金山丹佛丹佛亚特兰大亚特兰大纽约纽约芝加哥芝加哥2000120010009001300160014002200800700(旧金山旧金山, 丹佛丹佛) $900(旧金山旧金山, 芝加哥芝加哥) $1200(芝加哥芝加哥, 亚特兰大亚特兰大) $700(亚特兰大亚特兰大, 纽约纽约) $800总费用总费用: $3600900+1200+700+800=360045离散建模离散建模现实世界现实世界问题域问题域问题域解问题域解离散世界离散世界离散模型离散模型离散模型解离散模型解转换转换(抽象化抽象化)逆转换逆转换(语义化语义化)离散建模示意图离散建模示意图求解求解当数学模型建立在有限当数学模型建立
32、在有限集或可列集之上时集或可列集之上时, 此种此种模型的建立称离散建模模型的建立称离散建模.由于计算机科学是一种以由于计算机科学是一种以离散对象为研究目标的学离散对象为研究目标的学科科, 因此因此, 离散建模特别适离散建模特别适合于计算机科学领域合于计算机科学领域.46 每台计算机是一个顶点每台计算机是一个顶点. 如果两台计算机有直接连接，如果两台计算机有直接连接，则对应顶点有一条边则对应顶点有一条边v如何找到两台计算机之间的最短路由？（最短路径问题）如何找到两台计算机之间的最短路由？（最短路径问题）v如何找到连接所有计算机的代价最小的网络如何找到连接所有计算机的代价最小的网络? ?（最小生成
33、树问题）（最小生成树问题）v如何在两台计算机之间传输最大量的信息如何在两台计算机之间传输最大量的信息? ? （网络最大流问题（网络最大流问题 ）应用应用47旧金山旧金山丹佛丹佛亚特兰大亚特兰大纽约纽约芝加哥芝加哥25345959571855860191349760722最短通路问题最短通路问题洛杉矶洛杉矶2451908迈阿密迈阿密834波士顿波士顿6061090为航线系统建模的带权图为航线系统建模的带权图: 里程里程在波士顿与洛杉矶之间以空中距离计算的在波士顿与洛杉矶之间以空中距离计算的最短通路是什么？最短通路是什么？48旧金山旧金山丹佛丹佛亚特兰大亚特兰大纽约纽约芝加哥芝加哥4:051:30
34、2:202:552:100:501:151:551:50最短通路问题最短通路问题洛杉矶洛杉矶3:502:10迈阿密迈阿密2:00波士顿波士顿1:402:45为航线系统建模的带权图为航线系统建模的带权图:飞行时间飞行时间在波士顿与洛杉矶什么样的航班组合的总在波士顿与洛杉矶什么样的航班组合的总飞行时间最短？飞行时间最短？49旧金山旧金山丹佛丹佛亚特兰大亚特兰大纽约纽约芝加哥芝加哥$129$69$89$99$79$39$39$79$59最短通路问题最短通路问题洛杉矶洛杉矶$129$69迈阿密迈阿密$89波士顿波士顿$99$99在波士顿与洛杉矶之间以空中距离计算的在波士顿与洛杉矶之间以空中距离计算的最
35、短通路是什么？最短通路是什么？为航线系统建模的带权图为航线系统建模的带权图:票价票价50旧金山旧金山丹佛丹佛达拉斯达拉斯纽约纽约芝加哥芝加哥13729571855860191349722最短通路问题最短通路问题洛杉矶洛杉矶6459081376波士顿波士顿1235为计算机网络建模的带权图为计算机网络建模的带权图: 距离距离连接旧金山的计算机与纽约的计算机，连接旧金山的计算机与纽约的计算机，哪一段电话线有最短的总距离？哪一段电话线有最短的总距离？79851旧金山旧金山丹佛丹佛达拉斯达拉斯纽约纽约芝加哥芝加哥6秒秒4秒秒5秒秒3秒秒2秒秒3秒秒4秒秒最短通路问题最短通路问题洛杉矶洛杉矶4秒秒6秒秒7
36、秒秒波士顿波士顿5秒秒为计算机网络建模的带权图为计算机网络建模的带权图: 响应时间响应时间哪一段电话线给出旧金山与纽约之哪一段电话线给出旧金山与纽约之间通信的最短响应时间？间通信的最短响应时间？5秒秒52旧金山旧金山丹佛丹佛达拉斯达拉斯纽约纽约芝加哥芝加哥$1200$1000$1500$900$300$400$700最短通路问题最短通路问题洛杉矶洛杉矶$600$500$1400波士顿波士顿$1100为计算机网络建模的带权图为计算机网络建模的带权图: 月租费月租费连接旧金山的计算机与纽约的计算连接旧金山的计算机与纽约的计算机所需要的最便宜的一组电话线是机所需要的最便宜的一组电话线是什么？什么？$
37、80053图图G带有顶点带有顶点 a=v0, v1, . ,vn=z 和权和权w(vi, vj), 其中若其中若(vi, vj) 不不是是G中的边中的边, 则则 w(vi, vj)= 迪克斯屈拉算法迪克斯屈拉算法(现在初始化标记现在初始化标记, 使得使得a的标记为的标记为0而所有其余标记为而所有其余标记为,而而S是空集合是空集合)for i=1 to n L(vi) = L(a) = 0S = abcde5432z8210610545428210613ea0c2(a)dz4(a)b迪克斯屈拉算法迪克斯屈拉算法(续续)While u S u=不属于不属于S的的L(u)最小的一个顶点最小的一个顶点
38、; S=SuFor 所有不属于所有不属于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)d10(a,c)z3(a,c)b迪克斯屈拉算法迪克斯屈拉算法(续续)While u S u=不属于不属于S的的L(u)最小的一个顶点最小的一个顶点; S=SuFor 所有不属于所有不属于S的顶点的顶点v if L(u)+w(u,v
39、)芝加哥芝加哥-纽约纽约598.5.2 根树及其应用n根树及其分类根树及其分类n最优树与哈夫曼算法最优树与哈夫曼算法n最佳前缀码最佳前缀码60根树的定义根树的定义有向树有向树: 略去方向后为无向树的有向图略去方向后为无向树的有向图根树根树: 有一个顶点入度为有一个顶点入度为0, 其余的入度其余的入度均为均为1的非平凡的有向树的非平凡的有向树树根树根: 有向树中入度为有向树中入度为0的顶点的顶点树叶树叶: 有向树中入度为有向树中入度为1, 出度为出度为0的顶点的顶点内点内点: 有向树中入度为有向树中入度为1, 出度大于出度大于0的顶点的顶点分支点分支点: 树根与内点的总称树根与内点的总称顶点顶点
40、v的层数的层数: 从树根到从树根到v的通路长度的通路长度树高树高: 有向树中顶点的最大层数有向树中顶点的最大层数61实例实例根树的画法根树的画法: :树根放上方树根放上方, ,省去所有有向边上的箭头省去所有有向边上的箭头右图中右图中 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. 树高为树高为462家族树家族树把根树看作一棵把根树看作一棵家族树家族树:若顶点若顶点a邻接到顶点邻接到顶点b, 则称则称b是是a的的儿子儿子, a是是b的的父亲父亲若若
41、b和和c为同一个顶点的儿子为同一个顶点的儿子, 则称则称b和和c是是兄弟兄弟若若a b且且a可达可达b, 则称则称a是是b的的祖先祖先, b是是a的的后代后代r元树元树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子63最优最优2元树元树定义定义8.6 设设2元树元树T有有t片树叶片树叶v1, v2, , vt, 树叶的权分别为树叶的权分别为w1, w2, , wt, 称称 为为T的权的权, 记作记作W(T), 其中其中l(vi)是是vi的层数的层数. 在所有有在所有有t片树叶片树叶, 带权带权w1, w2, , wt 的的 2元元树中树中, 权最小的权最小的2元树称为元树称为最优
42、最优2元树元树)()(1itiivlwtW 例如例如134 561345613456W(T1)=6 3+3 3+4 2+5 2+1 2=47W(T2)=54W(T3)=4364求最优求最优2元树的算法元树的算法哈夫曼哈夫曼(Huffman)算法算法给定实数给定实数w1, w2, , wt 作作t片树叶片树叶, 分别以分别以w1, w2, , wt为权为权 在所有入度为在所有入度为0的顶点的顶点(不一定是树叶不一定是树叶)中选出两个权最小中选出两个权最小的顶点的顶点, 添加一个新分支点添加一个新分支点, 以这以这2个顶点为儿子个顶点为儿子, 其权等其权等于这于这2个儿子的权之和个儿子的权之和 重
43、复重复, 直到只有直到只有1个入度为个入度为0 的顶点为止的顶点为止 W(T)等于所有分支点的权之和等于所有分支点的权之和65实例实例例例 求以求以1,3,4,5,6为权的最优为权的最优2元树元树, 并计算它的权并计算它的权解解步骤一步骤一 作作5片树叶片树叶, 分别以分别以1,3,4,5,6为权为权13456步骤二步骤二134456在所有入度为在所有入度为0的顶点的顶点(不一定是树叶不一定是树叶)中选出中选出两个权最小的顶点两个权最小的顶点, 添加一个新分支点添加一个新分支点, 以这以这2个顶点为儿子个顶点为儿子, 其权等于这其权等于这2个儿子的权之个儿子的权之和和66步骤三步骤三13445
44、8步骤四步骤四13448611566751344861119步骤五步骤五W(T)=4+8+11+19=42W(T)=13+33+42+52+62=426851344861119W(T)=42最优最优2元树可能不唯一元树可能不唯一, 但不同最优但不同最优2元树权的值一样元树权的值一样. .4134596191069最佳前缀码最佳前缀码定义定义8.7 设设 = 1 2 n-1 n是长度为是长度为n的符号串的符号串, 1 2 k称作称作 的长度为的长度为k的的前缀前缀, k=1,2,n 1. 若非空字符串若非空字符串 1, 2, , m中任何两个互不为前缀中任何两个互不为前缀, 则称则称 1, 2,
45、 , m为为前缀码前缀码只出现两个符号只出现两个符号(如如0与与1)的前缀码称作的前缀码称作2元前缀码元前缀码例如例如 0, 10, 110, 1111 , 10, 01, 001, 110 是是2元前缀码元前缀码 0, 10, 010, 1010 不是前缀码不是前缀码编码必须是前缀码编码必须是前缀码. 若编码不是前缀码若编码不是前缀码, 会产生歧义会产生歧义. 如如a-0, b-10, c-010, d-1010, 则则1010解码不唯一解码不唯一,可以解码为可以解码为bb或或d.70用用2元树产生元树产生2元前缀码的方法元前缀码的方法例如例如前缀码前缀码 00, 11, 011, 0100
46、 对每个分支点对每个分支点, 若关联若关联2条边条边, 则给左边标则给左边标0, 右边标右边标1; 若只若只关联关联1条边条边, 则可以给它标则可以给它标0(看作左边看作左边), 也可以标也可以标1(看作右看作右边边). 将从树根到每一片树叶的通路上标的数字组成的字符将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处串记在树叶处, 所得的字符串构成一个前缀码所得的字符串构成一个前缀码.71实例实例例例 在通信中在通信中,设八进制数字出现的频率设八进制数字出现的频率(%)如下如下: 0: 25, 1: 20, 2: 15, 3: 10, 4: 10, 5: 10, 6: 5, 7: 5采
47、用采用2元前缀码元前缀码, 求传输数字最少的求传输数字最少的2元前缀码元前缀码 (称作称作最佳最佳前缀码前缀码), 并求传输并求传输100个按上述比例出现的八进制数字需个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的要多少个二进制数字？若用等长的 (长为长为3) 的码字传输需的码字传输需要多少个二进制数字要多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2元树元树. 这里这里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.72编码编码:0-01 1-112-0013-1004-101
48、5-00016-000007-0000101234567八进制数字出现的频率八进制数字出现的频率(%):0: 25, 1: 20, 2: 15, 3: 10, 4: 10, 5: 10, 6: 5, 7: 573传传100个按比例出现的八进制数字所需二进制数字个数为：个按比例出现的八进制数字所需二进制数字个数为：2 100 25% + 2 100 20% + 3 100 15% + 3 100 10%+ 3 100 10% + 4 100 10% + 5 100 5% + 5 100 5% = 285 前缀码编码前缀码编码: 0-01(25%), 1-11(20%), 2-001(15%), 3-100(10%), 4-101(10%), 5-0001(10%), 6-00000(5%), 7-00001(5%)或计算或计算最优最优2元树的权：元树的权：W(T)=28574采用等长采用等长(长为长为3)码，可以编码如下：码，可以编码如下：0-000(25%), 1-001(20%), 2-010(15%), 3-011(10%), 4-100(10%), 5-101(10%), 6-110(5%), 7-111(5%)传传100个按比例出现的八进制数字所需二进制数字个数为：个按比例出现的八进制数字所需二进制数字个数为：3 100=300
