《(1.3.5)--ch7-7离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.3.5)--ch7-7离散数学离散数学.pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 7-7.树与生成树树与生成树 定义定义7-7.1 一个一个连通且无回路连通且无回路的无向图称为的无向图称为树树,常用常用T表示表示.树中度数为树中度数为1的结点称为的结点称为树叶树叶.树中度数大于树中度数大于1的结点称为的结点称为分枝点分枝点或或内点内点.一个无回路的无向图称为一个无回路的无向图称为森林森林,若它若它的的每个连通分每个连通分图图是树是树.性质性质:树是简单图树是简单图.(a)和和(b)是树是树,(c)是森林是森林.平凡图称为平凡图称为平凡树平凡树 定理定理7-7.1 给定图
2、给定图T,则以下关于树的定义是等价的则以下关于树的定义是等价的 (1)T无回路且为连通图无回路且为连通图;(2)T无回路且无回路且e=v-1,其中其中e是边数是边数,v是结点数是结点数;(3)T连通且连通且e=v-1;(4)T无回路无回路,但增加一条新边但增加一条新边,得到一条且仅有一条回路得到一条且仅有一条回路;(5)T 连通连通,但删去任何一条边后便不连通但删去任何一条边后便不连通;(6)T的每一对结点之间有唯一一条路的每一对结点之间有唯一一条路.证明证明.(1)(2)(对结点数对结点数v 2用归纳法用归纳法.)1)如果如果v=2,由于由于T无回路且连通无回路且连通,故必有故必有e=1 e
3、=v-1.2)设设v=k时结论成立时结论成立.当当v=k+1时时,再将顶点再将顶点u及其关联边加回得到原图及其关联边加回得到原图T,由于树连通而无回路由于树连通而无回路,所以至少有一个度数为所以至少有一个度数为1的结点的结点u,在在T中删去中删去u及其关联边及其关联边,便得到便得到k个结点的连通且无回路的图个结点的连通且无回路的图.由归纳假设它有由归纳假设它有k-1条边条边,所以所以T中含有中含有k+1个顶点个顶点 和和k条边条边,符合公式符合公式 e=v-1.(2)(3)(反证法反证法)设设T无回路且无回路且e=v-1,要证要证T连通且连通且e=v-1.若若T 不连通不连通,设它有设它有k
4、2 个分支个分支T1,T2,Tk,因每个分支都是无回路的连通图因每个分支都是无回路的连通图,故若设故若设Ti有有vi个结点和个结点和ei条边条边,则由上证知则由上证知ei=vi-1,1,从而对图从而对图T 有有 1kiiee 1(1)kiivvk 矛盾！矛盾！(3)(4)设设T连通且连通且e=v-1,要证要证T无回路无回路,但增加一条新边但增加一条新边,得到一条且仅有一条回路得到一条且仅有一条回路.1)当当v=2时时,e=1,故必无回路故必无回路;且若增加一边且若增加一边,恰好得一条回路恰好得一条回路.2)设设v=k-1时命题成立时命题成立.当当v=k时时,因为因为T连通连通,e=k-1 故对
5、故对 u V,deg(u)1.且至少有一个结点且至少有一个结点u0其度数其度数deg(u0)=1.否则对否则对 u V,deg(u)22e=deg(v)2v,与条件与条件e=v-1矛盾矛盾.删去点删去点u0及与它关联的那条边得到图及与它关联的那条边得到图T*,显然图显然图T*是连通图是连通图 且满足且满足e*=v*-1,由归纳假设由归纳假设,T*无回路无回路,向向T*中加入中加入u0及与它关联及与它关联 那条边得到图那条边得到图T,故故T必无回路必无回路.若在连通图若在连通图T中增加新边中增加新边(ui,uj),则该边与则该边与T中结点中结点ui到到uj的一条路构成一条回路的一条路构成一条回路
6、,且该回路唯一且该回路唯一.否则否则删去此新边删去此新边,T中必有回路中必有回路,矛盾！矛盾！(4)(5)设设T无回路无回路,但增加一条新边但增加一条新边,得到一条且仅一条回路得到一条且仅一条回路.要证要证T 连通连通,但删去任何一条边后便不连通但删去任何一条边后便不连通;若若T不连通不连通,则必存在结点则必存在结点 ui 和和uj,它们之间没有路它们之间没有路.向图中添加新的边向图中添加新的边(ui,uj),将不会产生回路将不会产生回路,这与条件矛盾这与条件矛盾.由于由于T无回路无回路,所以删去任一边所以删去任一边,图便不连通图便不连通.(5)(6)因为因为T是连通图是连通图,故它的任意两个
7、结点间必有一条路故它的任意两个结点间必有一条路.若存在两点他们之间存在多于一条的路若存在两点他们之间存在多于一条的路,则则T 中必有回路中必有回路,则删去该回路一条边后则删去该回路一条边后,图仍连通图仍连通.矛盾！矛盾！设设T 连通连通,但删去任何一条边后便不连通但删去任何一条边后便不连通,要证要证T的每的每 一对结点之间有唯一一条路一对结点之间有唯一一条路.(6)(1)设设T的每一对结点之间有唯一一条路的每一对结点之间有唯一一条路,要证要证T无回路且无回路且为连通图为连通图.任意一对结点之间有唯一一条路任意一对结点之间有唯一一条路,故故T连通连通.若若T有回路有回路,则回路上任意一对结点之间
8、有两条路则回路上任意一对结点之间有两条路.矛盾！矛盾！定理定理7-7.2 任一棵树中至少有两片树叶任一棵树中至少有两片树叶.例例1 设设T是一棵树是一棵树,有两个有两个2度结点度结点,一个一个3度结点度结点,三个三个4度结度结点点,T 有几片树叶有几片树叶？解解.设树设树T有有x片树叶片树叶,则则T的结点数的结点数 n=2+1+3+x T的边数的边数 m=n-1=5+x 又由又由 12deg()niimv 得得 2 (5+x)=2 2+3 1+4 3+x 所以所以 x=9,即树即树T有有9片树叶片树叶.树的术语与性质思维形式注记图树的术语与性质思维形式注记图 树树 树的定义树的定义 树的性质树
9、的性质 6 6个等价命题个等价命题 任何树至少有两片叶子任何树至少有两片叶子 相关术语相关术语 树叶树叶 分枝点分枝点 森林森林 定义定义7-7.2 给定图给定图G=.若若G的的生成子图生成子图T是树是树,则称则称T是是 G的的生成树生成树.T中的边称为中的边称为树枝树枝;图图G的不在生成树中的边称为的不在生成树中的边称为弦弦.所有弦的集合称为生成树的所有弦的集合称为生成树的补补.图图(b)(c)是是(a)的生成树的生成树 定理定理7-7.3 连通图至少有一棵生成树连通图至少有一棵生成树.证明证明:若若G 中无回路中无回路,则则G本身就是一棵生成树本身就是一棵生成树.若若G中有回路中有回路,删
10、去回路上的一条边得到图删去回路上的一条边得到图G1,G1仍是连通的且与仍是连通的且与G有有相同的结点集相同的结点集.若若G1还有回路还有回路,就再删去此回路上的一条边得到图就再删去此回路上的一条边得到图G2,G2是连通的且与是连通的且与G有相同的结点集有相同的结点集.续行此法续行此法,直到得到连通图直到得到连通图T,它无回路且与它无回路且与G有相同的结点集有相同的结点集,T 就是就是G的生成树的生成树.推论推论1.无向图无向图G=有生成树有生成树 G是连通的是连通的.推论推论2.设设n阶无向连通图阶无向连通图G有有m条边条边,则则m n-1.注注.设设G是一个有是一个有n个结点个结点m条边的连
11、通图条边的连通图,它的生成树有它的生成树有 n-1条边条边.故必须从故必须从G中删去中删去m-(n-1)条边才能得到它的生成树条边才能得到它的生成树.数数m-n+1称为称为图图G的秩的秩.由证明知由证明知:一般来说一般来说,一个图的生成树不是唯一个图的生成树不是唯一的一的.1)例例.2)破圈法破圈法 避圈法避圈法 每次选取每次选取G中一条与已选取的边不构成回路的边中一条与已选取的边不构成回路的边,选取边的总数为选取边的总数为n-1 每次删除回路中的一条边每次删除回路中的一条边,删除的边的总数为删除的边的总数为m-n+1 定理定理7-7.4 图图G的一条回路和图的一条回路和图G的任意一棵生成树的
12、任意一棵生成树 T 的补的补 至少有一条公共边至少有一条公共边.定理定理7-7.5 图图G的一个边割集和图的一个边割集和图G的任意一棵生成树至少的任意一棵生成树至少 有一条公共边有一条公共边.证明证明.若存在若存在G的一条回路和的一条回路和T的补没有公共边的补没有公共边,则该回路则该回路一定包含在一定包含在T中中,与与T是树矛盾是树矛盾.证明证明.若若G的边割集与的边割集与T没有公共边没有公共边,那么删去这个边割集后那么删去这个边割集后所得子图必包含该生成树所得子图必包含该生成树,这意味着删去边割集后这意味着删去边割集后G仍然是连仍然是连通的通的,与边割集的定义矛盾与边割集的定义矛盾.例例2.
13、某地要兴建某地要兴建5个工厂个工厂,拟修筑道路连接这拟修筑道路连接这5处处.经勘测其经勘测其道路可依如下图所示的图的无向边铺设道路可依如下图所示的图的无向边铺设.为使这为使这5处都有道路处都有道路相通相通,问至少要铺几条路问至少要铺几条路?v1 v2 v3 v4 v5 e6 e1 e2 e3 e4 e5 解解 这实际上是求这实际上是求G的生成树的边数问题的生成树的边数问题 在图中在图中,n=5,则则n-1=5-1=4,所以至少要修所以至少要修4条路才行条路才行.定义定义2.给每条边赋与权的图给每条边赋与权的图G=称为称为加权图加权图,记为记为G=,其中其中W表示各边权的集合表示各边权的集合.定
14、义定义1.设设G是有是有n个结点的连通图个结点的连通图,对其每一条边对其每一条边e指定一指定一 个正数个正数C(e),称之为边称之为边e的的权权(权可以表示长度权可以表示长度,运输量运输量,费用等费用等).图图G的所有的生成树中的所有的生成树中,树权最小树权最小的那棵树称为的那棵树称为 定义定义7-7.3 设设G=是加权的连通图是加权的连通图,对任意边对任意边e E,其权其权w(e)0,令令T=是是G的一棵的一棵加权生成树加权生成树.其所有枝上的权的总和其所有枝上的权的总和w(e),称为树称为树T的的权权,记为记为w(T).定义定义3.是是G的的最小生成树最小生成树.求最小生成树问题是有实际意
15、义的求最小生成树问题是有实际意义的 如要建造一个连接若干城市的铁路网络如要建造一个连接若干城市的铁路网络,已知城市已知城市vi 和和vj 之间之间直达铁路的造价直达铁路的造价,设计一个总造价为最小的铁路网络设计一个总造价为最小的铁路网络,就是求最就是求最小生成树小生成树TG 1)在在G中选取最小权边中选取最小权边,置边数置边数i1.2)当当in1时时,结束结束.否则否则,转转3).3)设已选择边为设已选择边为e1,ei,在在G中选取不同于中选取不同于e1,ei的边的边ei+1,使使 e1,e2,ei,ei+1无回路且无回路且 ei+1是满足此条件的最小权边是满足此条件的最小权边.4)置置i为为
16、i1,转转2)设设G是有是有n个结点的连通图个结点的连通图,以下以下 定理定理7-7.6(Kruskal算法算法)算法产生的是图算法产生的是图G的最小生成树的最小生成树.注注:由于由于Kruskal算法在求最小生成树时算法在求最小生成树时,初始状态为初始状态为n个结点个结点,然后逐步加边然后逐步加边,这个过程中一直要避免回路的产生这个过程中一直要避免回路的产生,所以又称其所以又称其为“为“避圈法避圈法”.例例3.求图求图(0)中有权图的最小生成树中有权图的最小生成树 例例4.求图求图7.5.5中有权图中有权图G的最小生成树的最小生成树.例例5.下图所示的赋权图下图所示的赋权图G表示七个城市表示
17、七个城市a,b,c,d,e,f,g及架及架起城市间直接通讯线路的预测造价起城市间直接通讯线路的预测造价.试给出一个设计方案使得试给出一个设计方案使得各城市间能够通讯且总造价最小各城市间能够通讯且总造价最小,并计算出最小造价并计算出最小造价.解解:该问题相当于求图的最小生成树该问题相当于求图的最小生成树,此图的最小生成树为此图的最小生成树为 因此如图因此如图TG架线使各城市间能够通讯架线使各城市间能够通讯,且总造价最小且总造价最小,最小最小造价为造价为:w(T)=134892348 最小生成树的思维形式注记图最小生成树的思维形式注记图 生成树生成树 定义：无向图的定义：无向图的生成子图若是树生成子图若是树该树为原图的生成树该树为原图的生成树 最小生成树最小生成树 定义定义:树权最小树权最小 构造最小生成树算法构造最小生成树算法 性质：连通无向图至少有一个性质：连通无向图至少有一个生成树生成树 克鲁斯卡尔算法克鲁斯卡尔算法(避圈法避圈法)破圈法破圈法 小结小结 1、树、生成树和最小生成树的概念树、生成树和最小生成树的概念 2、掌握、掌握树的六种等价定义、树的六种等价定义、最小生成树的算法最小生成树的算法.