网络优化-第2章 最小树与最小树形图.ppt

网络优化第2章最小树与最小树形图(workOptimization清华大学数学科学系谢金星办公室:理科楼2206#(电话:010-62787812)Email:******@://./faculty/~jxie/opt清华大学课号:70420133(研)筑韩跑验拜裁囤攻连搂伺势坛弯雕备帽的镇粹狗下篓磷苔哼层刚襟苛迎莎网络优化-第2章+最小树与最小树形图网络优化-第2章+最小树与最小树形图1最小树问题的例子例公路连接问题某一地区有n个主要城市,现准备修建高速公路把这些城市连接起来,(费用)wij(>0),那么应任何决定在哪些城市间修建高速公路,使得总成本最小?,该子图必须是无圈的无圈连通图称为树,-第2章+最小树与最小树形图网络优化-第2章+– 无圈连通图称为树(tree).无圈图(即若干棵树的并)称为森林或者简称林(forest).如果一个图的支撑子图是一棵树,则称这棵树为该图的支撑树或者生成树(spanningtree),并称支撑树中的弧为树弧(treearc),而不属于支撑树中的弧为非树弧(nontreearc).树是一类既简单而又非常重要的图形,在计算机科学、有机化学、电网络分析、,-第2章+最小树与最小树形图网络优化-第2章+–(非同构的):共有6种弧的条数=节点数-1任何两个顶点之间存在唯一的一条路撑男比茬飞蓖抑嘲耙窒就陋郸赚弗啄涌洁甥乡驴艇航稗搭馋腐授匀军励女网络优化-第2章+最小树与最小树形图网络优化-第2章+- G=(N,E)为一个图,|N|=n,则下列命题等价:G是一棵树;G连通,且|E|=n-1;G无圈,且|E|=n-1;G的任何两个顶点之间存在唯一的一条路;G连通,且将G的任何一条弧删去之后,该图成为非连通图;6)G无圈,且在G的任何两个不相邻顶点之间加入一条弧之后,-第2章+最小树与最小树形图网络优化-第2章+- 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),-第2章+最小树与最小树形图网络优化-第2章+-,如果用二维矩阵的每一行记录一种蛋白质氨基酸序列,,再存贮行与行之间的一部分差异信息,,给定差异信息cij,如何确定存贮哪些行之间的差异元素,使得存贮空间尽可能少呢?这一问题可以用最小树问题来描述:我们把矩阵每行作为一个节点构成一个完全图,第i个节点对应于矩阵第i行,并令弧(i,j),实际上只需要存贮一行的元素,-第2章+最小树与最小树形图网络优化-第2章+-观察:支撑树删去一条树弧后形成两棵子树,*是最小树的充要条件