02 最小树和最小树形图.ppt

网络优化第2章最小树与最小树形图(workOptimization清华大学数学科学系谢金星清华大学课号:40420213(本),70420133(研)1最小树问题的例子例公路连接问题某一地区有n个主要城市,现准备修建高速公路把这些城市连接起来,(费用)wij(>0),那么应任何决定在哪些城市间修建高速公路,使得总成本最小?,该子图必须是无圈的无圈连通图称为树,– 无圈连通图称为树(tree).无圈图(即若干棵树的并)称为森林或者简称林(forest).如果一个图的支撑子图是一棵树,则称这棵树为该图的支撑树或者生成树(spanningtree),并称支撑树中的弧为树弧(treearc),而不属于支撑树中的弧为非树弧(nontreearc).树是一类既简单而又非常重要的图形,在计算机科学、有机化学、电网络分析、,–(非同构的):共有6种弧的条数=节点数-- G=(N,E)为一个图,|N|=n,则下列命题等价:G是一棵树;G连通,且|E|=n-1;G无圈,且|E|=n-1;G的任何两个顶点之间存在唯一的一条路;G连通,且将G的任何一条弧删去之后,该图成为非连通图;6)G无圈,且在G的任何两个不相邻顶点之间加入一条弧之后,- G=(N,E,W)为一个无向网络,W为权函数,即W:E→R(这里R表示实数集合).G中权最小(大)的弧称为最小(大)=(N1,E1)为G的一个子图,子图H的权定义为H所包含的所有弧的权之和,记为W(H),即W(H)=.弧e=(i,j)上的权常记为W(e),We或w(e),wij等如果T*是G的一棵生成树,且对G的任何一棵生成树T都有W(T*)≤W(T),则T*称为网络G的最小支撑树或者最小生成树(MST:minimumspanningtree),-,如果用二维矩阵的每一行记录一种蛋白质氨基酸序列,,再存贮行与行之间的一部分差异信息,,给定差异信息cij,如何确定存贮哪些行之间的差异元素,使得存贮空间尽可能少呢?这一问题可以用最小树问题来描述:我们把矩阵每行作为一个节点构成一个完全图,第i个节点对应于矩阵第i行,并令弧(i,j),实际上只需要存贮一行的元素,-观察:支撑树删去一条树弧后形成两棵子树,*是最小树的充要条件是:对T*中的任何一条弧,将该弧从T*中删除后形成的割中,“割最优条件”T*必要性:很容易用反证法证明。ee’设w(e)>w(e’),令T’=T*-e+e’,则w(T*)>w(T’)8T*-*是生成树并满足定理中的条件但不是最小树,T*\T0,将e从T*,该圈必然包括割中一条与e不同的弧e’,由假设,w(e)w(e’).最小树的“割最优条件”重复这一过程,最后可以得到T*也是最小树e’由T0为最小树,w(e)w(e’),则w(e)=w(e’),因此,T1=T0-e’+e也是最小树,与T*-观察:支撑树加上一条非树弧后包含一个唯一的圈T**是最小树的充要条件是:对属于G但不属于T*的任何一条弧,将该弧加入T*后形成的圈中,:很容易用反证法证明。e’e若w(e)<w(e’),令T’=T*-e’+e,则w(T*)>w(T’),矛盾。最小树的“圈最优条件”10