2 . 关联与相邻 关联（边与点关系）：若e是v1 , v2二点间的边，
记e [v1 , v2 ], 称v1 (或v2 )与e关联。
邻接（边与边、点与点）：点v1与v2有公共边， 称v1与v2相邻； 边e1与e2有公共点，称e1与e2相邻。
图在计算机中的表示： 关联矩阵：n *m或者是m*n 1 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1
2016/6/12
2、最小支撑树问题
某一地区有若干个主要城市，现准备修建高速公 路把这些城市连接起来，使得从其中任何一个城 市都可以经高速公路直接或间接到达另一个城市 。假定已经知道了任意两个城市之间修建高速公 路成本，那么应如何决定在哪些城市间修建高速 公路，使得总成本最小？
2016/6/12
3、 指派问题 Assignment problem
Y
N
Y {aj} ∪ S构成回路？ N j=j+1 ei+1=aj i=i +1 S={ei+1} ∪ S j=j+1 END T*=S 打印T*
2016/6/12
用避圈法解例2
v2
2
v1• 3 5 1
v3
2
7 5 3 5 v5
v6 1 7
5
v7
v4
最小部分树如图上红线所示； 最小权和为14。
思考：破圈法是怎样做的呢？ ——见圈就破，去掉其中权最大的。
2016/最小路
P：Vs…Vj…Vk…Vt，则P不仅是从Vs到Vt的最小路，而且从 Vs到P中任意中间点的最短路也在P上，为此可采用如下求 解步骤： ⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路， 然后由中间点再逐步过渡到终点Vt。 ⑵ 在计算过程中，需要把V中“经判断为最短路P途径之点i” 和“尚未判断是否为最短路P途径之点j”区分开来，可设 置集合I和J,前者归入I，后者归入J，并令算法初始时，I 中仅包含Vs，其他点全在J中，然后随着求解过程的进行， I中的点逐渐增加（相应J中的点逐渐减少），直到终点Vt 归入I（相应J=φ），此时迭代结束。I称为已标号集合,J 称为未标号集合。
2016/6/12
⑶ 为区分中间点 Vk 是否已归入 I 中以及逆向求解最 短路的方便，可在归入I中的点Vj上方给予双标号 （ lj, Vk），此中lj表示从Vs到 Vj最短路的距离， 而Vk则为从Vs到Vj最短路P中Vj的前一途径点。
⑷ 为在计算机上实现上述求解思想，还需引入G 中 各点间一步可达距离阵D=(dij)n×n，其中|V|=n
（3）在树中不相邻2点间添1边，恰成1圈；
（4）若树T有n个顶点，则T有n-1条边。
6.图的支撑树
若图G=（V，E）的子图T=（V，E’）是树， 则称T为G的支撑树。 特点——边少、点不少。
性质：G连通，则G必有支撑树。 证：破圈、保连通。
二、网络分析
网络——赋权图，记D=（V，E，C），其中C={c1，…，cn}， ci为边ei上的权（设ci 0 ）。
图论与网络分析
(Graph Theory and Network Analysis)
一、图论的基本概念 二、网络分析算法 三、Matlab实现
涉及网络优化的数学建模问题
1、最短路问题 货柜车司机奉命在最短的时间内将一车货物 从甲地运往乙地。从甲地到乙地的公路网纵 横交错，因此有多种行车路线，这名司机应 选择哪条线路呢？假设货柜车的运行速度是 恒定的，那么这一问题相当于需要找到一条 从甲地到乙地的最短路。
网络分析主要内容: 最小支撑树
最短路
最大流。
一. 最小支撑树问题
问题：求网络D的支撑树，使其权和最小。
方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。
Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7, 48-50.
一家公司经理安排 N 名员工去完成 N 项任务，每 人一项。由于各员工的特点不同，不同的员工 去完成同一项任务时所获得的回报不同。如何 分配工作方案可以使总回报最大？
2016/6/12
4、中国邮递员问题 Chinese postman problem
一名邮递员负责投递某个街区的邮件。如何为 他（她）设计一条最短的投递路线（从邮局出 发，经过投递区内每条街道至少一次，最后返 回邮局）？ 我国管梅谷教授1960年首先提出， 国际上称之为中国邮递员问题。
• 原理： Bellman最优化原理 若 P是网络 G中从 Vs到 Vt 的一条最短路，Vl是 P 中除Vs与 Vt 外 的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到 Vl的最短路。 证明（反证）：
若P1 不是从Vs 到Vl 的最短路，则存在另一条 Vs 到Vl 的路 P2 使 W(P2)<W(P1)， 若 记 路 P 中 从 Vl 到 Vt 的 路 为 P3。 则 有 W(P2)+W(P3)<W(P1)+ W(P3)=W(P)，此说明G中存在一条从Vs 沿P2到Vl沿P3再到Vt的更短的一条路，这与P使G中从Vs到Vt 的一条最短路矛盾。
5. 树
例1 已知有5个城市，要在它们之间架设电 话线网，要求任2城市都可通话（允许通过其它城 市），并且电话线的根数最少。
v1 v2 v3 v4 v5
树——无圈的连通图，记为T。
特点：连通、无圈。
v1
v2 v3 v4
v5
树的性质：（1）树的任2点间有且仅有1链；
（2）在树中任去掉1边，则不连通；
圈：封闭的链。
连通图：图G中任二点间至少存在一条链。
4. 有向图与无向图
图G (V , E ), 也可记G (vk ,[vi , v j ]).若点对[vi , v j ]无序， 称G为无向图；否则称G为有向图。为区别起见，称有向图 的边为弧，记（vi , v j ), 在图上用箭线表示。
比较：
无向图：边[v i ,v j ]，链 有向图：弧（v i ,v j ），路
，圈 ，回路
有向图的存储： 行为起点，列为终点 aij 1 存在弧vi v j 赋权图：边有长度
v1 8 3 v3 4 7 v5 2
1 v2
v4
赋权图在Matlab中的存储：
W= .41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21; DG=sparse 6 1 2 2 3 4 4 5 5 6 1 , 2 6 3 5 4 1 6 3 4 3 5 , W ； view(biograph(DG,[],'ShowWeights ','on ')) UG tril DG DG ' view(biograph(UG,[],'ShowWeights ','on '))
e5
e7 v4
e5
v4
简单图：无自环、无重边的图。
• |V|=n表示图G中节点个数为n，此节点个数 n也称为图G的阶 • |E|=m表示图G中边的个数为m • 任一顶点相关联的边的数目称为该顶点的 度 • 完全图：任意两点有边相连，用 K n 表示 完全图的边，和每点的度是多少？
2016/6/12
2016/6/12
5 、旅行商问题 Traveling salesman problem
一名推销员准备前往若干城市推销产 品。如何为他设计一条最短的旅行 路线？ （从驻地出发，经过每个城 市恰好一次，最后返回驻地）
2016/6/12
6、运输问题 Transportation problem
某种原材料有 M个产地，现在需要将原材料从产 地运往 N个使用这些原材料的工厂。假定 M个产 地的产量和 N家工厂的需要量已知，单位产品从 任一产地到任一工厂的运费已知，那么如何安排 运输方案可以使总运输成本最低？
wij，i能一步到达j d ij j ，i不能一步到达
2016/6/12
Dijkstra 算法
由图G建立一步可达距离阵D=(dij)n×n
给V1(Vs)括号(l1,Vk)=(0,s)给出已标号集合 I和未标号集合J的元素
对于给定的I和J，确定集合A={aij |Vi∈I，Vj ∈J}
2016/6/12
一、图论的基本概念
1 . 图与子图
图G (V , E )，其中V v1 , , vn 为顶点集， E e1 ,, em 为边集。
子图G1 (V1 , E1 ), 其中V1 V , E1 E。
如 G： e1 v1 e2 e3 e4 v2 e6 v3 G1： v1 e2 e3 e4 v2 e6 v3
1 1
3. 考虑所有这样的边 [v ,v ], 其中v V 1 ,v V 1 , 挑选 其中权最小的；
4. 重复3，直至全部顶点属于 V 1 (即V 1 )。
对G中各边按权大小顺序排列，不妨设为W1≤ W2≤ … ≤ Wm
填写Wj对应的各边aj S=φ ，i = 0，j=1
|S| = n-1
v2
2
v1 3 5 1
v3
2
7 5 3 5 v5
v6 1 7
5
v7
v4
• 2. 方法：Dijkstra算法（Dijkstra，1959）
Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271.