当前位置:文档之家› 第8章 图与网络分析

第8章 图与网络分析


0
1 0 0 0
0
0 0 0 0
0
0 0 0 1 1
0
0 0 0 0
1
0 1 0
0
0 1 1 0
0
0
1
v6
v7 v8
0 1 0
0 1 0
图与网络模型Graph Theory
最小树问题
二、树(Tree)和最小树



树是图论中一类重要的图,实际中有很多系统的结构都是树。 树——连通且不含圈的图,简记为 T 。 下面的说法是等价的: T是一个树。 T无圈,且 m = n-1。 T连通,且 m = n-1。 T 无圈,但每加一条新的边即出现唯一一个圈。 T连通,但每舍去一 条边就不连通。 T中任意两点,有唯一的一条链相连。 T是边 数最少的连通图。 图的生成树——若G图的一个点生成子图是一个树,则称此树是G图的 一个生成树。 树的权——若Tk是加权图G的一棵树,则树T的全部边的权之和称为树 Tk的权,记为 ( Tk )= (e); e Tk 最小树——T*是加权图G的一棵最小树,即( T* )=min{ (Tk) }
终止原则: 1)当P1j(k)= P1j(k+1)可停止,最短路P1j*= P1j(k) 2)当P1j(t-1)= P1j(t-2)时,再多迭代一次P1j(t) ,若P1j(t) = P1j(t-1) ,则原问题无解,存在负回路。
例: 求下图所示有向图中从v1到各点的 最短路。
v2
2 v1 -3 5
v6 e10 v7
v3
v8
1
0 0 1 0 0 0
0
1 0 1 0 0 0
1
0 0 1 0 0 2
0
0 0 0 1 1 0
1
1 0 0 0 1 1
0
0 1 0 0 1 0
0
0 1 0 1 0 0
0
2 0 1 0 0 0
A=(aij) nn=
v4 v5 v6 v7 v8
图与网络模型Graph Theory
图与网络模型Graph Theory
最短路问题
三、路(Path)和最短路
最短路问题是网络分析中应用最广泛的问题之一。尽管前面介绍 了用动态规划方法求解,但有时却较困难,此时图论的方法却十分有 效。 最短路问题的一般描述: G = (V,E)是连通图,图中各边(vi,vj)有权lij(=表示vi,vj间 无边),vs 、vt为图中任意两指定点,求一条路 µ ,使其是从 vs到 vt的 所有路中最短(路中各边的权之和最小)的一条路。即
18
10 10
图与网络模型Graph Theory
图与网络的基本概念
将此问题通过图的模型描述: 下图中,点——各城市,带箭头连线——从箭尾城市到箭头城市已订 购有机票,带箭头连线旁的数字——机票数量。

西 重 郑 8 昆 郑州办事处已订 有的到北京的 机票数量。

上 武 广 沈

图与网络模型Graph Theory
图与网络模型Graph Theory
最短路问题
v1,u1 =(M,W,G,H); v2,u2 =(M,W,G);
v3,u3 =(M,W,H);
v5,u5 =(M,G)。
v4,u4 =(M,G,H);
此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。
v1 v2 v3 v4 v5


aij =
k 0
当且仅当vi与vj之间有条边时 其它
图与网络模型Graph Theory
图与网络的基本概念
邻接矩阵
v1 e1 v2 e2
v1 v1 v2 v3 0 v2 1 v3 0 v4 0 v5 1 v6 0 v7 0 v8 0
v4 e3 e5 e6 e7 e8 v5
e9 e12 e11 e4
连通图
不连通图
图与网络模型Graph Theory
图与网络的基本概念
3、图与矩阵
在图与网络分析的应用中,将面临一个问题——如何分析、计算一 个较大型的网络,这当然需借助快速的计算工具——计算机。那么,如 何将一个图表示在计算机中,或者,如何在计算机中存储一个图呢?现 在已有很多存储的方法,但最基本的方法就是采用矩阵来表示一个图, 图的矩阵表示也根据所关心的问题不同而有——邻接矩阵、关联矩阵、 权矩阵等。 邻接矩阵——对于图G=(V,E),| V |=n, | E |=m,有nn阶方矩阵 A=(aij) nn,其中
图与网络模型Graph Theory
图与网络的基本概念
子图——


真子图—— 生成子图—— 点生成子图—— 边生成子图—— 点的次—— 奇次点—— 偶次点—— 链—— 圈—— 路—— 回路—— 赋权图—— 2、连通图 在众多各类图中有一类在实际应用中占有重要地位的图 连通图——在图中,任意两点间至少存在着一条链
图与网络的基本概念
一、图及其分类和术语




1、 图论中所研究的图并非几何学中的图,也不是绘画中的图。在这 里我们所关心的仅仅是图中有多少个点,点与点之间有无线来连接, 也就是说我们研究的是某个系统中的元素——点,以及这些元素之间 的某种关系——连线。 定义:图——一个图G是一个有序二元组(V,E),记为G=(V,E) 其中(1) V是一个有限非空的集合,其元素称为G的点或顶点,而称V 为G的点集 V={v1,v2,···,vn};(2)E是V中元素的无序对(vi,vj)所 构成的一个集合,其元素称为G的边,一般表示为 e =(vi,vj),而称E 是G的边集。 边(无向边)——没有方向的连线 弧(有向边)——带有方向的连线 无向图—— 有向图—— 简单图—— 多重图—— 完全图—— 二部图(偶图,双图)——
图与网络模型Graph Theory
引言

十八世纪的哥尼斯堡城中流过一条河(普雷.格尔河),河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样 一个游戏:一个游者怎样才能一次连续走过这 7 座桥,回到原出发点, 而每座桥只允许走一次。没有人想出走法,又无法说明走法不存在, 这就是著名的“哥尼斯堡 7 桥”难题。
k
图与网络模型Graph Theory
最小树问题
破圈法,避圈法求生成树:
生成树T
图G
生成树T
图与网络模型Graph Theory
最小树问题
破圈法,避圈法求最小生成树:
1
生成树T
4 1 2 4 5 5 3 2 1 1 3 4 4 2 5 1
1
2
1
1
2 3 2
1 1 2 1 1
图G
生成树T
2 3 2
u5
u4
u3
u2
u1
图与网络模型Graph Theory
最短路问题

在 E.W.Dijkstra 算法中必须满足一个条件 —— 在图 G 中所有边的权 lij ≥ 0。若在图 G 中存在有负 权边(当然,这种情形只针对有向图而言)时必 须对E.W.Dijkstra 算法加以修改 —— 称为修改的 E.W.Dijkstra 算法。
4 -2 v 3
6 v6 -3 2 4
v5
3 v8
4
v4
-1
v7
7
wij
v1 0 2 5 v2 0 -2 v3 0 v4 4
v5 v6 -3 4 6 0 0 7 -3 0 2 3 0
d(t)(v1,vj)
0 0 2 0 0 2 2 0 0 0 2
v1 v2 v3 v4 v5 v6 v7 v8 t=1 t=2 t=3 t=4 t=5 t=6
Y(T标号)
2 0
6
2 ∞ 5
7 2
2 10 ∞ 7
5
起点到 该点的 最短距 离的上 界
人、狼、羊、草渡河游戏
一个人带着一条狼、一只羊、一筐白菜过河蛤由于船
太小,人一次只能带一样东西乘船过河。狼和羊、羊 和白菜不能单独留在同岸,否则羊或白菜会被吃掉。 人—— M(Man), 狼—— W(Wolf), 羊—— G(Goat),草—— H(Hay)。 点—— vi 表示河岸的状态,边—— ek 表示由状态 vi 经一次渡河到状态 vj ,权——边 ek 上的权定为 1。 我们可以得到下面的加权有向图:
A D C B
图与网络模型Graph Theory
引言
“哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给 予了完满的解决,这是图论的第一篇论文。在后来的两百年间图论的 发展是缓慢的,直到 1936 年匈牙利数学家 O.Kö nig写出了图论的第一 本专著《有限图与无限图的理论》。 在图论的发展过程中还有两位著名科学家值得一提,他们是克希 霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重 要的贡献,而化学家凯莱在对碳氢化合物的同分异构体的数量进行计 数时推动了图论中树的计数问题的研究。 图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想” 了——历史上许许多多数学猜想之一。它描述对一张地图着色的问题, 曾经有一位数学家这样说:“对于这个问题,一位数学家可以用不到 五分钟的时间向马路上任何一位行人讲述清楚它,然后,两人都明白 这一问题,但是,两人都无能为力。”幸运的是在 1970‘s 终于由美国 的两位数学家借助大型计算机将其证明了。

图与网络模型Graph Theory
图与网络的基本概念
各办事处已订购机票情况表
成都 成都 重庆 武汉 上海 西安 郑州 8 重庆 10 武汉 5 10 10 15 6 14 8 8 上海 15 西安 8 6 郑州 沈阳 昆明 12 15 广州 10 北京 30 25
相关主题