运筹学第六章图与网络分析a管理精品资料

min T (v j) T （ v j） ,L （ v i） d ij j
3. 在与固定标号点相邻的临时标号点中选取 具有最小标号的点vi给予固定标号，即:
L(vi)=min｛ T(vj) ｝ 返回第2步。 4. 当vn得到固定标号时，计算结束。 注： 固定标号L(vi)表示v1到vi的最短距离， 临时标号T(vj)表示v1到vi距离的上界。
能一笔画的图一定是欧拉圈或含有欧拉链。 定理：连通的多重图G是欧拉图的充要条件是G 中无奇点。 推论：连通的多重图G有欧拉链的充要条件是G 中恰有两个奇点。
第二节 树图和图的最小部分树
树图：无圈的连通图称为树图，记为T(V,E)。 2-1 树的性质 性质1：任何树中必存在至少两个次为1的点（悬 挂点）。
若一个简单图中任意两点之间均有边相连，
则称该图为完全图。
对含有n个顶点的完全图，其边数有
Cn2
1n(n1) 2
条。
如果图的顶点能分成两个互不相交的非空
集合V1和V2 ，使在同一集合中任意两个顶点 都不相邻，则称该图为偶图（或二分图）。
若偶图的顶点集合V1、V2之间的每一对不 同顶点之间都有一条边相连，则称该图为完全 偶图。在完全偶图中， V1若有m个顶点， V2 有n个顶点，则其边数共有m×n条。
临时标号
v2（5） v3（2） v4（∞） v5（∞） v6（∞） v7（∞） v2（5） v4（9） v5（∞） v6（6） v7（∞） v4（7） v5（12） v6（6） v7（∞） v4（7） v5（7） v7（12）
v5（7） v7（12）
v7（10）
❖ Dijkstra 算 法 仅 适 合 于 所 有 的 权
Hale Waihona Puke 3-2 求任意两点间最短距离的矩阵算法(Floyd) 设邻接矩阵为D,计算D1=D+D, D2= D1 +D ,
D3= D2 +D ,… 。若Dm+1= Dm ，则Dm中的元 素值即为各点间的最短距离。
Dk+1= Dk +D算法： 例4：
D1=D+D=
+
=
d i(k j) m r d i(ik r 1 ) n d rj
第一节 图的基本概念
一、图的概念
1. 图（无向图） 图是由点与边组成的集合，记为：G=(V,E)，
其中V≠Φ，表示图G中点的集合，E表示图G中 边的集合。图中点的个数记为p，称为图的阶； 图中边的条数记为q。
2. 端点、关联边、相邻 若边e可以表示为e=（vi，vj)，则称vi和vj
是边e的端点；边e称为点vi和vj的关联边。 若点vi、vj与同一条边关联，称点vi和vj相
7. 子图，部分图 对图G1=｛ V1，E1 ｝和图G2=｛ V2，
E2 ｝ ，若有V1V2和 E1E2 ，则称G1是 G2的一个子图。
若有 V 1V2和 E1E2 ，则称G1是G2 的一个部分图。
定理 ：在图G中，所有顶点次之和等于边数
的两倍。即：
d(v) 2q
vV
定理 ：在任一图中，奇点的个数必为偶数。
v1 10 0 5 2 7 7 6 10 v2 8 5 0 7 2 5 4 8 v3 7 2 7 0 6 5 4 8 v4 7 7 2 6 0 3 2 6 v5 7 7 5 5 3 0 1 3 v6 6* 6 4 4 2 1 0 4 v7 10 10 8 8 6 3 4 0
（2）找出与v1相邻的点中距离最小的一个， 设为vr，
将L1r= L11+ d1r的值标注在点vr旁的小 方框内，此时， vr也已经标号； （3）从已标号点出发，找出与已标号点相
邻的所有未标号点vp，若有 L 1 p m p L 1i 1 d n 1 p ,L 1 r d rp
则将L1p的值标在vp旁的小方框内，此时，点 vp已得到标号； （4）重复第（3）步，直到vn得到标号。
固定标号
1. v1（0） 2. 3. 2. v1（0） v3（2） 4. 5. 3. v1（0） v3（2） v2（5） 6. 7. 4. v1（0） v3（2） v2（5） 8. v6（6） 9. 5. v1（0） v3（2） v2（5） 10. v6（6） v4（7） 11. 6 v1（0） v3（2） v2（5） 12. v6（6） v4（7） v5（7） 13. 7. v1（0） v3（2） v2（5） 14. v6（6） v4（7） v5（7） 15. v7（10）
次为0的点称为孤立点。 次为1的点称为 悬挂点。
.v6
5. 链，圈，连通图 图中由相邻的点和互不相同的边组成的
交替序列μ称为链。 若链中的所有顶点也不相同，则该链称
为路。 起点与终点重合的链称为圈。起点与终
点重合的路称为回路。 若图中任意两个顶点之间都至少存在一
条链，则称该图为连通图。
6. 完全图，偶图
V4 8 0 2 3 -7 -7 -7
V5 -1 0 1 -3 -3
V6 1 0 1 7 -1 -1 -1
V7 -1 0 5 -5 -5
V8 -3 -5 0 6 6
❖ 为了求出从v1到各个点的最短路，一般采
用反向追踪的方法：如果已知L(vs,vj),那么寻 求一个点vk,使得L(vs,vk)+wkj=L(vs,vj),然后记 录 下 (vk,vj) 。 再 看 L(vs,vk), 寻 求 一 个 点 vi, 使 得 L(vs,vi)+wiK=L(vs,vk)… 依 次 类 推 ， 一 直 到 达 L(vs,v1) 为 止 。 这 样 ， 从 vS 到 vj 的 最 短 路 是 （vs,…vi,vk,vj）。 ❖ 在 本 例 中 , 由 表 知 ， L(v1,v8)=6, 由 于 L(v1,v6)+d68=(-1)+7 记 录 下 v6 , 由 于 L(v1,v3)+d36=L(v1,v6),j 记 录 下 v3 , 由 于 L(v1,v1)+d13=L(v1,v3), 于 是 ， 从 v1 到 v8 的 最 短 路是(v1,v3,v6,v8)。
1.若点vi到点vj之间有一条弧，则令权数为dij， 否则，令dij=+∞。 2.由于从vs到vj的最短路是从vs点出发，沿着这 条路到某个点vi,再沿弧(vi,vj)到点vj。显然， 从vs到vi必定是从vs到vj的最短路，否则从vs到 vj的这条路将不是最短路。于是，从vs到vj的最 短距离L(vs,vj)满足以下条件，
－3
v3
2
1
1 v6
－3 7
v8
8 －5 2 3
1
－5
v4
－1
v7
终 点
dij
L(t)(vs,vj)
起 V1 V2 V3 V4 V5 V6 V7 V8 t=1 t=2 t=3 t=4
点
V1 0 -1 -2 3 0 0 0 0
V2 6 0 2 -1 -5 -5 -5
V3 -3 0 -5 1 -2 -2 -2 -2
作业： P172 6.11 6.13
修正狄克斯特拉（标号）算法： 步骤： 1. 对起点v1给予固定标号L(v1)=0，其余点为 临时标号，并记为：
T(vj
)
d1j
v1与vj相邻 (j=1,2...n) v1与vj不相邻
2. 设vi是刚刚得到固定标号的点L(vi) ，修改与 其相邻的临时标号点vj ：
性质2：具有n个顶点的树的边数恰好为(n-1)条。 性质3：任何具有n个顶点、（n-1)条边的连通图 是树。
2-2 图的最小部分树（最短树） 如果G1是G2的部分图，又是树图，则称G1
是G2的部分树（或支撑树）。 G2的树枝总长最 小的部分树称为该图的最小部分树。
定理1. 图中任一个点i，若j是与i相邻点中距离 最近的，则边(i, j)必含在该图的最小部分树内。 推 则论 两： 集合把之图间的连所线有的点最分短成边V一和定V 包两含个在集最合小，部 分树内。
L(vs，vj)=min{L(vs，vi)+dij}, i=1,…,p
i
这个关系式L(vs，v1)…L(vs，vp)可利用如
下的递推公式求解
L(1)(vs，vj)=dsj ,j=1…p L(t)(vs,vj)=miin{L(t-1)(vs，vi)+ dij},t=2,3…
3.当计算到第K步时,若对一切的j=1…p,有
L(k)(vs，vj)=L(k-1)(vs，vj)
则 L(k)(vs ， vj),j=1…p, 就 是 从 vs 到 各 点 vj
的最短路径。
结论
❖ 设C是赋权函数有向图D中的一个回路。如果回路C的 权S（C）是负数那么称C是D中的一个负回路。
可以证明以下的结论：
1.如果赋权有向图D不含有负回路，那么从vs到任 一点的最短路至多包含P-2个中间点，并且必可取为
例: 在如下图所示的赋权有向图中求从v1到各
点的最短路。
解:利用上述递推公式，将求解结果列出如 下表所示。
可以看出，当t=4时，有：
L(t)(vs,vj)=L(t-1)(vs,vj) j=1…8 。 因 此 ， 表 中的最后一列，就是从v1到v1,v2,..,v8的最短
路权。
v2
－1
v5
6
v1
－1 －2
例：有八种化学药品，某些不能放入同一个仓 库，用连线表示。见下图。 （v1) （ v2， v4，v7) （v3，v5) （v6，v8)
例：四色问题。
8. 同构 对图G1=｛ V1，E1 ｝和图G2=｛ V2，
E2 ｝ ，如果顶点集合V1与V2之间以及边的集 合E1与E2之间都建立了一一对应关系，并且 图G1的两顶点之间的边对应于图G2对应顶点 的边，则称图G1与图G2是同构的。
9. 赋权图：对一个无向图G的每一条边（vi， vj) ，相应地有一个数wij，则称这样的图G为 赋权图（也称网络图，记为N)，wij称为边（vi， vj) 上的权。