运筹学网络分析

地理位置、地理实体、地理区域，譬如，山顶、河流汇聚点、车站、 地理位置、地理实体、地理区域，譬如，山顶、河流汇聚点、车站、 码头、村庄、城镇等——点 码头、村庄、城镇等 点 它们之间的相互联系，譬如，构造线、河流、交通线、 它们之间的相互联系，譬如，构造线、河流、交通线、供电与通讯 线路、人口流、物质流、资金流、信息流、技术流等 线路、人口流、物质流、资金流、信息流、技术流等——点与点的 点与点的 连线。 连线。 一个由基本流域单元组成的复杂的流域地貌系统， 一个由基本流域单元组成的复杂的流域地貌系统，如果舍弃各种复 杂的地貌形态，各条河流 杂的地貌形态，各条河流——线，河流分岔或汇聚处 线 河流分岔或汇聚处——点，流域 点 地貌系统——水系的基本结局（树）。 水系的基本结局（ 地貌系统 水系的基本结局
（4 ）环 的两个端点相同， 若e的两个端点相同，即u＝v，则称为环。 的两个端点相同 ＝ ，则称为环。 （5）多重边 若连接两个端点的边多于一条以上， 若连接两个端点的边多于一条以上，则称为 多重边。 多重边。 （6）多重图 含有多重边的图，称为多重图。 含有多重边的图，称为多重图。 （7）简单图 无环、无多重边的图，称为简单图。 无环、无多重边的图，称为简单图。
（13）基础图 13）
从一个有向图D＝（ ， ） 从一个有向图 ＝（V，A）中去掉所有边上的箭头所 ＝（ 得到的无向图，就称为D 的基础图，记之为G（ ）。 得到的无向图，就称为 的基础图，记之为 （D）。
（14）截 14）
如果从图中移去边的一个集合将增加亚图的数目时， 如果从图中移去边的一个集合将增加亚图的数目时， 被移去的边的集合就称为截。 被移去的边的集合就称为截。
需要说明的是——图的定义只关注点之间是否 图的定义只关注点之间是否 需要说明的是 连通，而不关注点之间的连结方式。 连通，而不关注点之间的连结方式。对于任何一个 图的画法并不唯一。 图的画法并不唯一。

一、树的概念及性质 例：已知有五个城市，要在它们之间架设电话线，要 求任何两个城市都可以互相通话（允许通过其它城市） ，并且电话线的根数最少。
v2
v3
v1
v5
v4
9
1.树的定义 ：连通且不含圈的无向图称为树。 次为1的点称为树叶，次大于1的点称为分枝点，树的边称 为树枝。
v2 v4 v2 v1 v4
d1 j = min( d1i wij )
i
设任一点vi到任一点 vj都有一条弧，如果（vi, vj）不是弧，则添 22 加弧（vi, vj），令wij=+∞
迭代过程：
①初始条件： t=1,d1j(1)=w1j (j=1,2,…,n) ，如果 v1 与 vj间 无边，其最短路长记为+∞ ②t=2,3,…
3
悬挂边：悬挂点的关联边
定理1：图G=(V,E)中，所有点的次之和是边数 的两倍，即
Σd(v)=2q vV
定理2：任一图中，奇点的个数为偶数。
给定一个图G=(V,E)，一个点边的交错序列(vi1, ei1, vi2, ei2,…,vik-1,eik-1,vik)，如果满足eit=[vit,vit+1] (t=1,2,…,k1)，则称为一条联结vi1和vik的链，记为(vi1,vi2,…,vik)， 称点vi2, vi3,…,vik-1为链的中间点。
2．最小支撑树（最小树）
具有最小权的支撑树称为最小支撑树。
13
3．求最小支撑树的方法
（1）避圈法 在图中选一条权数最小的边，在以后的每步中，总从未被选 取的边中选一条权数最小的边，并使之与已选取的边不构成圈（ 权数相同时，任选一条），直到选够n-1条边为止。
3
2
4 1 5

vV1 vV2 vV
由于2m为偶数, 而 d (v )是若干个偶数之和, 也是偶数.
vV2
所以 d (v )必为偶数,即 | V1 | 是偶数.
有向图中,以vi为始点的边数称为点vi的出次, 用d (vi )表示, 以vi为终点的边数称为点vi的入次, 用d (vi )表示, vi点的出次与入次之和就是该点的次.
六、第10章 图与网络分析
图与网络的基本知识 树及最小树问题 最短路问题 最大流问题 最小费用最大流问题
(Graph Theory and Network Analysis)
A
C
D
问题：一个游者怎样才 能一次连续走过这七座 桥且每座桥只走一次， 回到原出发点。
A
B
哥尼斯堡“七桥”难 题 欧拉用A,B,C,D四点表示河的 两岸和小岛，用两点间的联 线表示桥。七桥问题变为： 从A,B,C,D任一点出发，能否 通过每条边一次且仅一次， 再回到该点?
无路可通.那么加上一边( u, v )也不会形成圈, 与已知矛盾. 再证每舍去一边便不连通.若T中有一边( u, v ), 舍去( u, v )后
图T ( u, v )仍然连通, 那么T T ( u, v )由于无圈是一棵树
但T 加一边( u, v )后就是T 仍无圈, 与( 4)中树每加一新边必
从T中去掉(v , u)边及u点不会影响T的连通性, 得图T , T 为树 只有k 1个顶点, 所以有k 2条边, 再把(v , u)，u加上去,可知
当T 有k个顶点时有k 1条边.
( 2) (3)
只需证明T 是连通图.
l
反证法.设T 不连通, 可以分为l个连通分图( l 2), 设第i个
e4

第5章 图论与网络分析
网络分析
➢ 图的基本概念 ➢最小支撑树问题 ➢ 最短路径问题 ➢网络最大流问题
图论起源：哥尼斯堡七桥问题
A
A
C
D
C
D
B
B
问题：一个散步者能否从任一块陆地出发;走过七 座桥;且每座桥只走过一次;最后回到出发点
结论：每个结点关联的边数均为偶数
§1 图的基本概念
1图
由点和边组成;记作G=V;E;其中 V=v1;v2;……;vn为结点的集 合;E=e1;e2;……;em 为边的集合; 点表示研究对象 边表示研究对象之间的特定关系
例 ： G1为不连通图; G2为连通图
G1
G2
5 支撑子图
图G=V;E和G'=V ' ;E ';若V =V ' 且E ' E ;则 称G' 为
G的支撑子图;
例 ：G2为G1的支撑子图
v5
v5
v1
v4 v1
v4
v2
v3
G1
v2
v3
G2
例 ： G2 是G1 的子图；
v2
e1 v1
e6 e7
e2
v3
e8 e9
两条以上的边都是权数最大的边;则任意去掉其 中一条： ③若所余下的图已不含圈;则计算结束;所余下的图 即为最小支撑树;否则;返问①;
例 求上例中的最小支撑树
v1
5
v2
7.5 4
5.5
3
v5
2
解：
v3 3.5 v4 v1
5
v2
75 4
55
3
v5
2
v3 3 5 v4
算法2避圈法：从某一点开始;把边按权从小到大 依次添入图中;若出现圈;则删去其中最大边;直至 填满n1条边为止n为结点数 ;