网络规划_运筹学.ppt

第五章 网络规划;5.1 图论基础;引例（2）铁路运输网络图;——如果图中两点之间的联线无方向之别，称之为无向边，相应的图称为无向图，记为G=（V，E）。;——如果图中两点之间的联线有方向之别，称之为有向边（一般用箭头表示方向）， 相应的图称为有向图，记为D=（V，E）。;二、无向图G=（V，E）相关概念;二、无向图G=（V，E）相关概念;二、无向图G=（V，E）相关概念;三、有向图D=（V，E）相关概念;三、有向图 D=（V，E）相关概念;三、有向图D=（V，E）相关概念;四、同构图;五、树及其性质;(3)根树：若有向图T中顶点x到任意其他顶点v 都恰有一条初等链，则T为以x为根的根树。 (4)有向树：若有向图T中顶点x到任意其他顶点 v都恰有一条路径，则称T为以x为根的有向树。 ;（二）树的基本性质 （1）T连通且无回路； （2）T无回路且有条边； （3）T连通且有(n-1)条边； （4）T无回路，但不相邻的两个顶点联以一边 恰得一个回路； （5）T连通，但去悼的任意一条边，T就不连通； （6）T的任意顶点之间恰有一条初等链。;5.2 最小生成树问题; (1)设G=(V,E)是连通赋权无向图,任意e?E（G）,赋予非负权W(e)=Wij?0。若T=(V,E’)是G图的一个生成树，称E’中所有边的权之和 W（T）= 为生成树T的权。 (2)如果T*为连通赋权无向图G的生成树，且 W（T*）= min{W(T)|T为图G的生成树} 则称T*为图G的最小生成树。; 设无向图G=（V，E）中各个顶点表示某区所属10个街道的位置，边的权表示两个街道之间的距离。现在计划建设连通各个街道的电话网。问如何规划电话网，既保证任意街道之间可以通话，又使总的电话线路里程最短？;三、最小生成树算法;（二） T*算法（1）：避圈法（Kruskal算法） 1)算法思想： （1）生成树无回路且边数为n-1; (2) 在无回路的条件下优先生长权最小的边。 ——将图G的m条边按权的递增顺序排列； w(e1)?w(e2)?…w(ek)?w(ek+1)?…w(em) ——选取ei进入边集ET,不使其导出子图 T (ET)有回路,i=1,2,…,。 （3）如果ET的边数|ET|=n-1，则T=(ET)为连 通赋权无向图G=(V,E)的最小生成树T*. ; 2)标号避圈法 ——采用顶点标号法判断ei加入后，相关子图是否存在回路： （1）初始标号：任意vi ? V，l(vi)=i； （2）当e=（u,v)加入T，则 l(u)=l(v)=min{l(u),l(v)}； 对T中的其他边e’=(s,t), l(s)=l(t)=min{l(s),l(t)}; G中其余顶点标号不变。 （3）若e=（u,v)两端顶点标号相同，则e不能进 入T，否则出现回路C。;（四） T*算法（2）：破圈法 （1）见圈即破； （2）去除圈中最长边； （3）直至图中不再含圈。;5.3 中国邮递员问题;问题的目标？;问题的目标？;二、相关基本概念;三、相关基本定理;（1）连通无向图G为欧拉图，当且仅当 G中无奇点。 （2）连通无向图G含有欧拉链，当且仅 当G中恰有2个奇点，分别为欧拉 链的起终点。;基本推论;四、欧拉环游算法;——生长规则： 假设已经生成链Qk=Vi0ej1Vi1...Vik-1ejkVik， 若添加顶点Vik的一条关联边ejk+1继续生长，ejk+1 应满足以下条件之一（即保证生长过程中图Gk=G-Qk连通）： （1） ejk+1为Gk 中顶点Vik的唯一一条关联边； （2） ejk+1 为Gk 中顶点Vik的多条关联边中的 任意一条“非割边”；;（1）初始化： k=0，任取欧拉图G的顶点Vi0，令Q0=Vi0 （2）生长第(k+1)边： 设生长链Qk=Vi0ej1Vi1...Vik-1ejkVik，在连通图 Gk=G-Qk添加顶点Vik的一条关联边ejk+1继续生长， ejk+1 满足以下条件之一： （a）ejk+1为Gk 中顶点Vik的唯一一条关联边； （b）ejk+1 为Gk 中顶点Vik的多条关联边中的