网络优化最小树与最小树形图.ppt

定义2.3 有向图G=（V，A）若满足： （1）不包含有向圈； （2）存在一个顶点i使得d - (i)=0（即顶点i没有入弧），而对其余顶点j有d - (j)=1（即顶点j有且只有一条入弧）； 则称G为以i为根（Root）的树形图（Arborescence），也称有根树（Rooted Tree）或外向树（Out-Tree）. 定义2.4 如果一个有向图的支撑子图是一个树形图，则称该树形图为该有向图的支撑树形图(或生成树形图). 有向网络中权最小的支撑树形图称为该网络的最小树形图. 2.3最小树形图 – 定义 定义2.5 设v是网络N的任意一个节点，在所有指向v的入弧中，权最小的弧称为v的最小入弧. 由最小入弧组成的有向圈称为最小入弧圈. 若网络N的每个节点取最小入弧组成的子图是支撑树形图，则它就是最小树形图. (书上说法有误) 如果在网络N中，从每个节点取一条最小入弧，组成的子图是否就是最小树形图？ 2.3最小树形图 从树形图的根到每一个节点有且仅有一条有向路，这条路的长度称为该节点的代（即该节点关于根节点的层数）. 树形图在去掉每条弧的方向后，得到的无向基本图是一棵树，因此具有n个节点的树形图包含n-1条弧. 引理2.2 网络N每个节点取一最小入弧，组成的图记为H，则 （1）若|H|n-1， （2）若|H|=n-1 ， （3）若|H|=n ， 2.3最小树形图 – 引理 证明(略) H a 最小树形图是否一定是Ｈ，或Ｈ去掉一条弧？ 则N没有支撑树形图； 且H不含有向圈，则H是N的最小树形图; 设a是H中权最大的弧，且H\a不含有向圈，则H\a是N的最小树形图. 定理2.3 设C是网络N的最小入弧圈，如果N存在支撑树形图，则存在N的最小树形图T满足| C \ T |=1. 证明 假设定理不成立，在N的最小树形图中找一棵T使得| C \ T | 最小. 2.3最小树形图 – 定理 　　由于树形图不含有向圈，因此| C \ T |=ｋ?２.　 　　记C中不在T上的弧依次为　　　　　,　　　　　, …, 　　　　　　　　　则C中余下的弧组成的有向路　　　　,　　　　, …, 　　　　都属于T. 不妨设 v’1是所有k个节点{v’1 ,v’2 ,… ,v’k}在T 中代数最小的节点，则 v’1在T 中不会是 v’2的后代 但由于v2在T 中是v’1的后代，所以 v2在T 中不会是 v’2的后代. C * 网 络 优 化 第2章 最小树与最小树形图 （第1讲） Network Optimization 清华大学数学科学系 谢金星 办公室：理科楼2206# （电话：010 Email:jxie@ /faculty/~jxie/courses/netopt 清华大学课号研） 最小树问题的例子 例 公路连接问题 某一地区有n个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市i和j之间修建高速公路的成本（费用）wij (0), 那么应任何决定在哪些城市间修建高速公路，使得总成本最小？ 高速公路网正好构成这个完全图G的一个连通的支撑子图T. 为了使得总建设成本最小, 该子图必须是无圈的 无圈连通图称为树，上面这样一类问题称为最小树问题. 2.1树的基本概念 – 定义 定义2.1 无圈连通图称为树（tree）. 无圈图（即若干棵树的并）称为森林或者简称林（forest）. 如果一个图的支撑子图是一棵树，则称这棵树为该图的支撑树或者生成树(spanning tree)，并称支撑树中的弧为树弧（tree arc），而不属于支撑树中的弧为非树弧（nontree arc）. 树是一类既简单而又非常重要的图形，在计算机科学、有机化学、电网络分析、最短连接及渠道设计等领域都有广泛的应用. 在本节及下一节中，我们假设所讨论的图与网络都是无向的. 2.1树的基本概念 – 例 例2.1 含6个顶点的树 (非同构的)： 共有6种 弧的条数 = 节点数 - 1 任何两个顶点之间存在唯一的一条路 2.1树的基本概念 - 树的等价定义 引理2.1 G=(N, E)为一个图，|N|=n，则下列命题等价: G是一棵树； G连通，且|E|=n-1； G无圈，且|E|=n-1； G的任何两个顶点之间存在唯一的一条路； G连通，且将G的任何一条弧删去之后，该图成为非连通图； 6) G无圈，且在G的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈. 2.1树的基本概念 - 最小树的定义 定义2.2 G=（N，E，W）为一个无向网络，W为权函数, 即W: