9.1-无向树.ppt

第第4篇篇 图论基础图论基础o 第第9章章 树树离散数学离散数学第第9章章 树树约定：本章所谈的回路都指初级回路或简单回路。约定：本章所谈的回路都指初级回路或简单回路。约定：本章所谈的回路都指初级回路或简单回路。约定：本章所谈的回路都指初级回路或简单回路。oo树、森林树、森林树、森林树、森林n n无向树的性质无向树的性质无向树的性质无向树的性质oo生成树生成树生成树生成树n n最小生成树最小生成树最小生成树最小生成树n n求最小生成树求最小生成树求最小生成树求最小生成树oo有向树、根树有向树、根树有向树、根树有向树、根树n n几类特殊的根树几类特殊的根树几类特殊的根树几类特殊的根树oo二叉树二叉树二叉树二叉树n n最优树最优树最优树最优树n n用用用用HuffmanHuffman算法构造最优树算法构造最优树算法构造最优树算法构造最优树oo二元前缀码二元前缀码二元前缀码二元前缀码n n最优二叉树的应用：最优二叉树的应用：最优二叉树的应用：最优二叉树的应用：HuffmanHuffman编码编码编码编码9.1 无向树无向树一、基本概念一、基本概念一、基本概念一、基本概念o无向树无向树无向树无向树（简称（简称（简称（简称树树树树）：连通且不含有回路的无向图，常）：连通且不含有回路的无向图，常）：连通且不含有回路的无向图，常）：连通且不含有回路的无向图，常用用用用T T表示。表示。表示。表示o森林森林森林森林：每个连通分支都是树的无向图。：每个连通分支都是树的无向图。：每个连通分支都是树的无向图。：每个连通分支都是树的无向图。o叶结点叶结点叶结点叶结点（简称（简称（简称（简称叶叶叶叶）：在树）：在树）：在树）：在树T T中，度数为中，度数为中，度数为中，度数为1 1的结点。的结点。的结点。的结点。o内部结点内部结点内部结点内部结点（或（或（或（或分支结点分支结点分支结点分支结点，简称，简称，简称，简称分支点分支点分支点分支点）：在树）：在树）：在树）：在树T T中，中，中，中，度数大于度数大于度数大于度数大于1 1的结点。的结点。的结点。的结点。树？树？森林？森林？叶？叶？内部结点？内部结点？二、无向树的性质二、无向树的性质定理定理定理定理 9.1 9.1 对于树对于树对于树对于树T=T=，|V|=n|V|=n，|E|=m|E|=m，下列性，下列性，下列性，下列性质质质质成立且相互等价：成立且相互等价：成立且相互等价：成立且相互等价：T T中中中中无回路无回路无回路无回路且边数且边数且边数且边数m=n-1m=n-1；T T是是是是连通图连通图连通图连通图且边数且边数且边数且边数m=n-1m=n-1；T T中中中中无回路无回路无回路无回路，但，但，但，但在在在在T T的的的的任何任何任何任何不相邻结点之间增加一不相邻结点之间增加一不相邻结点之间增加一不相邻结点之间增加一条边，就得到条边，就得到条边，就得到条边，就得到唯一唯一唯一唯一的一条基本回路的一条基本回路的一条基本回路的一条基本回路。T T是连通图，但是连通图，但是连通图，但是连通图，但删去任何一条边删去任何一条边删去任何一条边删去任何一条边后，所得到的后，所得到的后，所得到的后，所得到的图图图图不连通不连通不连通不连通。T T中中中中每对结点之间有唯一的一条基本通路。每对结点之间有唯一的一条基本通路。每对结点之间有唯一的一条基本通路。每对结点之间有唯一的一条基本通路。o树是树是树是树是“最小的连通图最小的连通图最小的连通图最小的连通图”o树是树是树是树是“最大的无回路图最大的无回路图最大的无回路图最大的无回路图”o重点：如果重点：如果重点：如果重点：如果T=T=是是是是树树树树，则则则则|E|=|V|-1|E|=|V|-1二、无向树的性质（续）二、无向树的性质（续）证明证明证明证明 （1 1）由树的定义来推证性质）由树的定义来推证性质）由树的定义来推证性质）由树的定义来推证性质。由树的定义可知，。由树的定义可知，。由树的定义可知，。由树的定义可知，T T 中无回路。中无回路。中无回路。中无回路。o对结点数对结点数对结点数对结点数n n进行归纳。进行归纳。进行归纳。进行归纳。o当当当当n n=1=1时，时，时，时，m m=0=0，则，则，则，则m m=n n 1 1成立。成立。成立。成立。o设设设设 n n=k k时，成立。那么，当时，成立。那么，当时，成立。那么，当时，成立。那么，当n n=k k+1 +1 时，因为树是时，因为树是时，因为树是时，因为树是连通且无回路，所以至少有一个度数为连通且无回路，所以至少有一个度数为连通且无回路，所以至少有一个度数为连通且无回路，所以至少有一个度数为1 1的结点的结点的结点的结点v v，否，否，否，否则，如果所有结点的度数都至少为则，如果所有结点的度数都至少为则，如果所有结点的度数都至少为则，如果所有结点的度数都至少为2 2，那么必然存在，那么必然存在，那么必然存在，那么必然存在回路，这与树的定义矛盾。从树中删除结点回路，这与树的定义矛盾。从树中删除结点回路，这与树的定义矛盾。从树中删除结点回路，这与树的定义矛盾。从树中删除结点v v和以和以和以和以v v为为为为端点的边，则得到端点的边，则得到端点的边，则得到端点的边，则得到k k个结点的树个结点的树个结点的树个结点的树T T*。根据假设，。根据假设，。根据假设，。根据假设，T T*有有有有(k k 1)1)条边。现将结点条边。现将结点条边。现将结点条边。现将结点v v和以和以和以和以v v为端点的边添加到为端点的边添加到为端点的边添加到为端点的边添加到T T*上上上上还原成树还原成树还原成树还原成树T T，则，则，则，则T T有有有有(k k+1)+1)个结点和个结点和个结点和个结点和k k 条边，故，条边，故，条边，故，条边，故，m m=n n 1 1成立。成立。成立。成立。二、无向树的性质（续）二、无向树的性质（续）（2 2）由性质由性质由性质由性质来推证性质来推证性质来推证性质来推证性质。o采用反证法。若采用反证法。若采用反证法。若采用反证法。若T T 不是连通图，设不是连通图，设不是连通图，设不是连通图，设T T有有有有k k个连通分支个连通分支个连通分支个连通分支T T1 1、T T2 2、T Tk k（k k 2 2），其结点数分别为），其结点数分别为），其结点数分别为），其结点数分别为n n1 1、n n2 2、n nk k，边数分别为，边数分别为，边数分别为，边数分别为mm1 1、mm2 2、mmk k，则有，则有，则有，则有o这与这与这与这与m m=n n 1 1相矛盾，故，相矛盾，故，相矛盾，故，相矛盾，故，T T 是连通图且是连通图且是连通图且是连通图且m m=n n 1 1。二、无向树的性质（续）二、无向树的性质（续）（3 3）由性质由性质由性质由性质来推证性质来推证性质来推证性质来推证性质。oo对结点数进行归纳。对结点数进行归纳。对结点数进行归纳。对结点数进行归纳。oo当当当当n n=2=2时，时，时，时，m m=n n 1 1 =1=1，由，由，由，由T T的连通性质，的连通性质，的连通性质，的连通性质，T T没有回路。如果两个结点之没有回路。如果两个结点之没有回路。如果两个结点之没有回路。如果两个结点之间增加一条边，就只能得到唯一的一个基本回路。间增加一条边，就只能得到唯一的一个基本回路。间增加一条边，就只能得到唯一的一个基本回路。间增加一条边，就只能得到唯一的一个基本回路。oo假设假设假设假设n n=k k时，命题成立。则当时，命题成立。则当时，命题成立。则当时，命题成立。则当n n=k k+1+1时，因为时，因为时，因为时，因为T T是连通的并有是连通的并有是连通的并有是连通的并有(n n 1)1)条条条条边，所以每个结点的度数都至少为边，所以每个结点的度数都至少为边，所以每个结点的度数都至少为边，所以每个结点的度数都至少为1 1，且至少有一个结点的度数为，且至少有一个结点的度数为，且至少有一个结点的度数为，且至少有一个结点的度数为1 1。否则，。否则，。否则，。否则，如果每个结点的度数都至少为如果每个结点的度数都至少为如果每个结点的度数都至少为如果每个结点的度数都至少为2 2，那么必然会有结点的总度数，那么必然会有结点的总度数，那么必然会有结点的总度数，那么必然会有结点的总度数2 2mm 2 2n n，即即即即mm n n。这与。这与。这与。这与m m=n n 1 1相矛盾，所以，至少有一个结点相矛盾，所以，至少有一个结点相矛盾，所以，至少有一个结点相矛盾，所以，至少有一个结点v v的度数为的度数为的度数为的度数为1 1。oo删除结点删除结点删除结点删除结点v v及其关联的边，得到图及其关联的边，得到图及其关联的边，得到图及其关联的边，得到图T T*，由假设知，图，由假设知，图，由假设知，图，由假设知，图T T*无回路。现将结点无回路。现将结点无回路。现将结点无回路。现将结点v v及其关联的边添加到图及其关联的边添加到图及其关联的边添加到图及其关联的边添加到图T T*，则还原成，则还原成，则还原成，则还原成T T，所以，所以，所以，所以，T T没有回路。没有回路。没有回路。没有回路。oo在连通图在连通图在连通图在连通图T T中，任意两个结点中，任意两个结点中，任意两个结点中，任意两个结点v vi i和和和和v vj j之间必存在一条通路，且是基本通路。之间必存在一条通路，且是基本通路。之间必存在一条通路，且是基本通路。之间必存在一条通路，且是基本通路。如果这条基本通路不唯一，则如果这条基本通路不唯一，则如果这条基本通路不唯一，则如果这条基本通路不唯一，则T T中必有回路，这与已知条件矛盾。进一步中必有回路，这与已知条件矛盾。进一步中必有回路，这与已知条件矛盾。进一步中必有回路，这与已知条件矛盾。进一步地，如果在连通图地，如果在连通图地，如果在连通图地，如果在连通图T T中，增加一条边中，增加一条边中，增加一条边中，增加一条边(v vi i,v vj j)，则边，则边则边，则边(v vi i,v vj j)与与与与T T中结点中结点中结点中结点v vi i和和和和v vj j之之之之间的一条基本通路，构成一个基本回路，且该基本回路必定是唯一的。否间的一条基本通路，构成一个基本回路，且该基本回路必定是唯一的。否间的一条基本通路，构成一个基本回路，且该基本回路必定是唯一的。否间的一条基本通路，构成一个基本回路，且该基本回路必定是唯一的。否则，当删除边时，则，当删除边时，则，当删除边时，则，当删除边时，T T中必有回路，这与已知条件矛盾。中必有回路，这与已知条件矛盾。中必有回路，这与已知条件矛盾。中必有回路，这与已知条件矛盾。二、无向树的性质（续）二、无向树的性质（续）（4 4）由性质由性质由性质由性质来推证性质来推证性质来推证性质来推证性质。o如果如果如果如果T T 不是连通图，则存在两个结点不是连通图，则存在两个结点不是连通图，则存在两个结点不是连通图，则存在两个结点v vi i和和和和v vj j，在结点，在结点，在结点，在结点v vi i和和和和v vj j之间没有通路，如果增加边之间没有通路，如果增加边之间没有通路，如果增加边之间没有通路，如果增加边(v vi i,v vj j)，不产生回路，不产生回路，不产生回路，不产生回路，这与性质这与性质这与性质这与性质矛盾，因此，矛盾，因此，矛盾，因此，矛盾，因此，T T 是连通图。是连通图。是连通图。是连通图。o因为因为因为因为T T 中没有回路，所以删除任意一条边，所得到的中没有回路，所以删除任意一条边，所得到的中没有回路，所以删除任意一条边，所得到的中没有回路，所以删除任意一条边，所得到的图必定不是连通图。图必定不是连通图。图必定不是连通图。图必定不是连通图。二、无向树的性质（续）二、无向树的性质（续）（5 5）由性质由性质由性质由性质来推证性质来推证性质来推证性质来推证性质。o在连通图在连通图在连通图在连通图T T中，任意两个结点中，任意两个结点中，任意两个结点中，任意两个结点v vi i和和和和v vj j之间必存在一条通之间必存在一条通之间必存在一条通之间必存在一条通路，且是基本通路。如果这条基本通路不唯一，则路，且是基本通路。如果这条基本通路不唯一，则路，且是基本通路。如果这条基本通路不唯一，则路，且是基本通路。如果这条基本通路不唯一，则T T中必有回路，删除回路上任意一条边，图仍然是连中必有回路，删除回路上任意一条边，图仍然是连中必有回路，删除回路上任意一条边，图仍然是连中必有回路，删除回路上任意一条边，图仍然是连通的，这与性质通的，这与性质通的，这与性质通的，这与性质矛盾。所以，矛盾。所以，矛盾。所以，矛盾。所以，T T 中任意每对结点之中任意每对结点之中任意每对结点之中任意每对结点之间有唯一的一条基本通路。间有唯一的一条基本通路。间有唯一的一条基本通路。间有唯一的一条基本通路。二、无向树的性质（续）二、无向树的性质（续）（6 6）由性质由性质由性质由性质来推证树的定义。来推证树的定义。来推证树的定义。来推证树的定义。oT T 中任意每对结点之间有唯一的一条基本通路，所以，中任意每对结点之间有唯一的一条基本通路，所以，中任意每对结点之间有唯一的一条基本通路，所以，中任意每对结点之间有唯一的一条基本通路，所以，T T 是连通图。是连通图。是连通图。是连通图。o如果如果如果如果T T 中有回路，那么回路上任意一对结点之间有两中有回路，那么回路上任意一对结点之间有两中有回路，那么回路上任意一对结点之间有两中有回路，那么回路上任意一对结点之间有两条基本通路，这与题设条件矛盾。所以，图是连通条基本通路，这与题设条件矛盾。所以，图是连通条基本通路，这与题设条件矛盾。所以，图是连通条基本通路，这与题设条件矛盾。所以，图是连通的且无回路，是树。的且无回路，是树。的且无回路，是树。的且无回路，是树。二、无向树的性质（续）二、无向树的性质（续）定理定理定理定理9.29.2oo设设设设T=T=为为为为n n（n n 2 2）阶树，则）阶树，则）阶树，则）阶树，则T T中中中中至少有至少有至少有至少有2 2个个个个叶结点。叶结点。叶结点。叶结点。oo证明：证明：证明：证明：(思路思路思路思路)关键是应用关键是应用关键是应用关键是应用|E|=|V|-1|E|V|-1 练习练习 已知树已知树已知树已知树T T中有度数为中有度数为中有度数为中有度数为4 4、3 3和和和和2 2的分支结点各的分支结点各的分支结点各的分支结点各1 1个，其余个，其余个，其余个，其余结点均为叶结点，求树结点均为叶结点，求树结点均为叶结点，求树结点均为叶结点，求树T T中叶结点的数目？中叶结点的数目？中叶结点的数目？中叶结点的数目？解解解解 设树设树设树设树T T中叶结点的数目为中叶结点的数目为中叶结点的数目为中叶结点的数目为x x，则树，则树，则树，则树T T的结点数目为的结点数目为的结点数目为的结点数目为(x x+3)+3)。由树的性质知，树由树的性质知，树由树的性质知，树由树的性质知，树T T中边的数目为中边的数目为中边的数目为中边的数目为 (x x+3)+3)1=1=x x+2+2。由握手定理知：由握手定理知：由握手定理知：由握手定理知：2(2(x x+2)=4+2)=4 1+31+3 1+21+2 1+1+x x 1 1可以解出：可以解出：可以解出：可以解出：x x=5=5。练习练习 画出所有非同构的画出所有非同构的画出所有非同构的画出所有非同构的6 6 6 6阶树。阶树。阶树。阶树。解：解：解：解：三、赋权树三、赋权树o边赋权树（简称为赋权树）：对于树边赋权树（简称为赋权树）：对于树边赋权树（简称为赋权树）：对于树边赋权树（简称为赋权树）：对于树T T=，其中，其中，其中，其中，V V=v v1 1,v v2 2,v vn n，E E=e e1 1,e e2 2,e emm，通过函数，通过函数，通过函数，通过函数WW：E ER R（实数集）对（实数集）对（实数集）对（实数集）对T T中的任意边中的任意边中的任意边中的任意边e e=(=(v vi i,v vj j)标注一个属性标注一个属性标注一个属性标注一个属性w w(v vi i,v vj j)，所得到的树。，所得到的树。，所得到的树。，所得到的树。o记为记为记为记为T T=。o称函数称函数称函数称函数WW为图为图为图为图G G的权函数，的权函数，的权函数，的权函数，w w(e e)称为边称为边称为边称为边e e上的权，简记为上的权，简记为上的权，简记为上的权，简记为w wij ij；o树树树树T T中所有边的权的总和，即，中所有边的权的总和，即，中所有边的权的总和，即，中所有边的权的总和，即，称为赋权树，称为赋权树，称为赋权树，称为赋权树T T的权值。的权值。的权值。的权值。三、赋权树（续）三、赋权树（续）oo例例例例如如如如：在在在在赋赋赋赋权权权权树树树树T T1 1中中中中，w w(v v1,1,v v2)2)=2=2、w w(v v1,1,v v5)5)=3 3、w w(v v5,5,v v4)4)=2 2、w w(v v5,5,v v9)9)=5 5、w w(v v5,5,v v6)6)=2 2、w w(v v4,4,v v8)8)=1 1、w w(v v6,6,v v3)3)=1 1、w w(v v6,6,v v7)7)=3 3、w w(v v6,6,v v10)10)=1 1，赋赋赋赋权权权权树树树树T T1 1的的的的权权权权值值值值为为为为2 2+3 3+2+5+2+1+1+3+1=202+5+2+1+1+3+1=20；oo在在在在赋赋赋赋权权权权树树树树T T2 2中中中中，w w(v v1,1,v v2)2)=2=2、w w(v v2,2,v v3)3)=2 2、w w(v v2,2,v v5)5)=3 3、w w(v v3,3,v v4)4)=1 1、w w(v v3,3,v v6)6)=2 2、w w(v v5,5,v v7)7)=5 5、w w(v v5,5,v v8)8)=1 1、w w(v v5,5,v v9)9)=1 1，赋赋赋赋权权权权树树树树T T2 2的的的的权权权权值值值值为为为为2 2+2 2+3 3+1 1+2 2+5 5+1 1+1 1=1717。四、生成树四、生成树 设设设设GG是无向连通图是无向连通图是无向连通图是无向连通图；o如果如果如果如果T T是是是是GG的生成子图的生成子图的生成子图的生成子图，且，且，且，且T T为树为树为树为树，则称，则称，则称，则称T T是是是是GG的的的的生成树生成树生成树生成树 (Spanning tree)(Spanning tree)。o将图将图将图将图GG在在在在T T中的边称为中的边称为中的边称为中的边称为树枝树枝树枝树枝，将不在，将不在，将不在，将不在T T中的边称为中的边称为中的边称为中的边称为T T的的的的弦弦弦弦。oT T的所有弦导出的的所有弦导出的的所有弦导出的的所有弦导出的GG的子图称为的子图称为的子图称为的子图称为T T的的的的余树余树余树余树。四、生成树四、生成树(续续)例例例例.o图图图图G G1 1、G G2 2和和和和G G3 3是图是图是图是图G G的生成子图，并且是图的生成子图，并且是图的生成子图，并且是图的生成子图并且是图G G的生成的生成的生成的生成树，图树，图树，图树，图G G4 4、G G5 5和和和和G G6 6分别是生成树分别是生成树分别是生成树分别是生成树G G1 1、G G2 2和和和和G G3 3的余树。的余树。的余树。的余树。从图中可以看出，余树从图中可以看出，余树从图中可以看出，余树从图中可以看出，余树G G4 4和和和和G G6 6中含有回路，它们都不中含有回路，它们都不中含有回路，它们都不中含有回路，它们都不是树；余树是树；余树是树；余树是树；余树G G5 5是一棵树。是一棵树。是一棵树。是一棵树。一个无向连通图的生成树不一定唯一个无向连通图的生成树不一定唯一；生成树的余树不一定是树，也一；生成树的余树不一定是树，也不一定连通。不一定连通。四、生成树（续）四、生成树（续）例例例例.nT T中的树枝：中的树枝：中的树枝：中的树枝：nT T的弦：的弦：的弦：的弦：o如果如果如果如果GG为为为为n n阶阶阶阶mm条边，则条边，则条边，则条边，则T T有多少条树枝？多少条弦？有多少条树枝？多少条弦？有多少条树枝？多少条弦？有多少条树枝？多少条弦？e1,e2,e7,e4,e5e1,e2,e7,e4,e5e3,e6,e8e3,e6,e8四、生成树（续）四、生成树（续）定理定理定理定理9.3 9.3 任何无向连通图都存在生成树任何无向连通图都存在生成树任何无向连通图都存在生成树任何无向连通图都存在生成树。证明：证明：证明：证明：oo若连通图若连通图若连通图若连通图GG没有回路，则它本身就是一棵生成树。没有回路，则它本身就是一棵生成树。没有回路，则它本身就是一棵生成树。没有回路，则它本身就是一棵生成树。oo若若若若GG至少有一个回路，删去回路上的一条边，得到至少有一个回路，删去回路上的一条边，得到至少有一个回路，删去回路上的一条边，得到至少有一个回路，删去回路上的一条边，得到GG1 1，它，它，它，它仍然是连通的，并与仍然是连通的，并与仍然是连通的，并与仍然是连通的，并与GG有相同的结点集合。有相同的结点集合。有相同的结点集合。有相同的结点集合。n n若若若若GG1 1没有回路，则没有回路，则没有回路，则没有回路，则GG1 1就是就是就是就是GG的生成树；的生成树；的生成树；的生成树；n n若若若若GG1 1仍然有回路，再删去仍然有回路，再删去仍然有回路，再删去仍然有回路，再删去GG1 1回路上的一条边。回路上的一条边。回路上的一条边。回路上的一条边。oo重复上面的步骤，直到得到一个连通图重复上面的步骤，直到得到一个连通图重复上面的步骤，直到得到一个连通图重复上面的步骤，直到得到一个连通图T T，它没有回路，所，它没有回路，所，它没有回路，所，它没有回路，所以以以以T T是树。又由于是树。又由于是树。又由于是树。又由于T T与与与与GG有相同的结点集，因此有相同的结点集，因此有相同的结点集，因此有相同的结点集，因此T T为为为为GG的生成的生成的生成的生成树。树。树。树。oo连通图的生成树连通图的生成树连通图的生成树连通图的生成树不唯一不唯一不唯一不唯一。oo若若若若GG是连通无向图，则其任何一条回路至少包含一条弦。是连通无向图，则其任何一条回路至少包含一条弦。是连通无向图，则其任何一条回路至少包含一条弦。是连通无向图，则其任何一条回路至少包含一条弦。四、生成树（续）四、生成树（续）推论推论推论推论1 1 设无向连通图设无向连通图设无向连通图设无向连通图G G中有中有中有中有n n个结点和个结点和个结点和个结点和mm条边，则条边，则条边，则条边，则mm n n 1 1。oo证明证明证明证明 由定理由定理由定理由定理9.39.3知，知，知，知，G G中存在生成树中存在生成树中存在生成树中存在生成树T T，且生成树，且生成树，且生成树，且生成树T T的树枝数的树枝数的树枝数的树枝数为为为为mm =n n 1 1。因此，。因此，。因此，。因此，mm mm =n n 1 1。证毕。证毕。证毕。证毕。推论推论推论推论2 2 设无向连通图设无向连通图设无向连通图设无向连通图G G中有中有中有中有n n个结点和个结点和个结点和个结点和mm条边，条边，条边，条边，T T是是是是G G的生成树，的生成树，的生成树，的生成树，T T*是是是是T T的余树则的余树，则的余树，则的余树，则T T*中有中有中有中有(mm n n+1)+1)条边。条边。条边。条边。oo证明证明证明证明 由定理由定理由定理由定理9.39.3知，知，知，知，G G中存在生成树中存在生成树中存在生成树中存在生成树T T，且生成树，且生成树，且生成树，且生成树T T的树枝数的树枝数的树枝数的树枝数为为为为mm =n n 1 1。设。设。设。设T T*是是是是T T的余树，那么，的余树，那么，的余树，那么，的余树，那么，T T*中的边的数目为：中的边的数目为：中的边的数目为：中的边的数目为：mm mm =mm n n+1+1。证毕。证毕。证毕。证毕。四、生成树（续）四、生成树（续）例：求图例：求图例：求图例：求图GG的生成树。的生成树。的生成树。的生成树。五、最小生成树五、最小生成树 对于无向连通赋权图对于无向连通赋权图G=o图图G的最小生成树的最小生成树：权值最小的赋权生成树。：权值最小的赋权生成树。o最小生成树的求解方法：最小生成树的求解方法：n避圈法避圈法避圈法避圈法n破圈法破圈法破圈法破圈法求最小生成树求最小生成树 (方法一方法一)KruskalKruskal避圈算法避圈算法避圈算法避圈算法 (从边的角度从边的角度从边的角度从边的角度)(1)(1)将各条边按照权值从小到大的顺序排列；将各条边按照权值从小到大的顺序排列；将各条边按照权值从小到大的顺序排列；将各条边按照权值从小到大的顺序排列；(2)(2)依次依次依次依次选取权值最小选取权值最小选取权值最小选取权值最小并且并且并且并且没有造成回路的边没有造成回路的边没有造成回路的边没有造成回路的边；(3)(3)总共选取总共选取总共选取总共选取n-1n-1条边条边条边条边（n n为图中的结点数）。为图中的结点数）。为图中的结点数）。为图中的结点数）。求最小生成树求最小生成树(方法二方法二)破圈法破圈法破圈法破圈法 (从边的角度从边的角度从边的角度从边的角度)每次删去回路中权最大的边。每次删去回路中权最大的边。每次删去回路中权最大的边。每次删去回路中权最大的边。举例举例 某新建城区，要铺设供应居民住宅小区某新建城区，要铺设供应居民住宅小区某新建城区，要铺设供应居民住宅小区某新建城区，要铺设供应居民住宅小区A A、B B、C C、D D、E E、F F和和和和G G的煤气管道，各个居民住宅小区之间铺设煤的煤气管道，各个居民住宅小区之间铺设煤的煤气管道，各个居民住宅小区之间铺设煤的煤气管道，各个居民住宅小区之间铺设煤气管道的费用由图气管道的费用由图气管道的费用由图气管道的费用由图9.89.8所示赋权图给出，试给出费用最省所示赋权图给出，试给出费用最省所示赋权图给出，试给出费用最省所示赋权图给出，试给出费用最省的煤气管道铺设方案，使煤气能供应到各个住宅小区。的煤气管道铺设方案，使煤气能供应到各个住宅小区。的煤气管道铺设方案，使煤气能供应到各个住宅小区。的煤气管道铺设方案，使煤气能供应到各个住宅小区。即最小费即最小费用为：用为：1+1+2+2+3+4=13作业作业oP360第第1大题大题第第3大题大题第第6大题大题第第8大题大题第第13大题大题：注只要求对注只要求对G1求解所有非同构的生成树。求解所有非同构的生成树。第第16大题大题第第17大题大题