图论模型

本讲的主要内容
图论的一些简单实例
图论基础
图论的应用
1、图论的基本概念
问题1(哥尼斯堡七桥问题):
能否从任一陆地出发通过每座桥恰好一次而回到出发点？
4
欧拉指出：
如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.
2、一个简单的例子
印刷电路板将布线区域划分为n×m个方格阵列
精确的电路板布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。
布线时电路只能沿直线或直角布线。
为避免线路相交，已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。
3、引例
现有6个人，任意两人之间或者相互认识，或者相互不认识，证明这6个人中，或者有3个人彼此都认识，或者有3个人彼此不认识
思路一
只有6个人，人数非常少，可以枚举任意两人之间的关系，然后判断每一种情况是否符合题意。如果所有情况都满足，则命题成立。
虽然只有6个人，但是这样做的时间复杂度可不低，枚举次数为215
只能借助计算机了。。。
有没有人可以直接证明的办法呢？
思路二
有了图论这个强大的工具，我们还是像往常一样，以人为顶点，关系为边，建图。但是为了以后的直观，这里图的建立有一点小小的不同：
如果两个人之间相互认识，则在这两个人(顶点)间连一条红色边，如果两个人不认识，则在这两个人(顶点)间连一条蓝色边(下面会看到这样做的好处)
那么这样我们就得到了一个由红边和蓝边组成的6阶完全图
我们实际上要证明的就是这个图中或者存在一个红三角形(认识)，或者存在一个蓝三角形(不认识)
任取一个顶点v0，由它连出5条边到其它的顶点，这五条边只有红色和蓝色两种
根据抽屉原理，肯定有一种颜色的边有3条或3条以上,不妨设为红色
vi
v0
vj
vk
如果vi,vj,vk之间的边都是蓝边，则图中存在一个蓝三角形
如果至少有1条为红边，那么它总会与v0发出的两条红边组成一个红三角形。
这样就证明了这个命题。
4、 商人们怎样安全过河
问题(智力游戏)
   3名商人
   3名随从
随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.
但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?
问题分析
多步决策过程
决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员
要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.
模型构成
xk~第k次渡河前此岸的商人数
yk~第k次渡河前此岸的随从数
xk, yk=0,1,2,3;
k=1,2, 
sk=(xk , yk)~过程的状态
S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}
S ~ 允许状态集合
uk~第k次渡船上的商人数
vk~第k次渡船上的随从数
dk=(uk , vk)~决策
D={(u , v) u+v=1, 2} ~允许决策集合
uk, vk=0,1,2;
k=1,2, 
sk+1=sk dk
+(-1)k
~状态转移律
求dkD(k=1,2, n), 使skS, 并按转移律由 s1=(3,3)到达 sn+1=(0,0).
多步决策问题
模型求解
穷举法 ~ 编程上机
图解法
状态s=(x,y) ~ 16个格点
允许决策 ~ 移动1或2格; k奇,左下移; k偶,右上移.
s1
sn+1
d1, ，d11给出安全渡河方案
评注和思考
规格化方法,易于推广
考虑4名商人各带一随从的情况
允许状态
S={(x , y) x=0, y=0,1,2,3;
x =3, y=0,1,2,3; x=y=1,2}
22
图的定义
图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.
定义1 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中
① V称为G的顶点集, V≠, 其元素称为顶点或结点, 简称点;
② E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边.
如果V = {v1, v2, … , vn}是有限非空点集, 则称G为有限图或n阶图.
23
如果E的每一条边都是无向边, 则称G为无向图(如图1); 如果E的每一条边都是有向边, 则称G为有向图(如图2); 否则, 称G为混合图.
图
1
图
2
并且常记
V = {v1, v2, … , vn}, |V | = n ;
E = {e1, e2, … , em}(ek=vivj ) , |E | = m.
称点vi , vj为边vivj的端点. 在有向图中, 称点vi , vj分别为边vivj的始点和终点. 该图称为(n,m)图
24
对于一个图G = (V, E ), 人们常用图形来表示它, 称其为图解. 凡是有向边, 在图解上都用箭头标明其方向.
例如, 设V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}, 则G = (V, E ) 是一个有4个顶点和6条边的图, G的图解如下图所示.
25
一个图会有许多外形不同的图解, 下面两个图表示同一个图G = (V, E )的图解.其中
V = {v1 , v2 , v3 , v4},
E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}.
这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.
26
有边联结的两个点称为相邻的点, 有一个公共端点的边称为相邻边. 边和它的端点称为互相关联. 常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 对于有向图,还有出度和入度之分.
用N(v)表示图G中所有与顶点v相邻的顶点的集合.
d(v1)= d(v3)= d(v4)=4,
d(v2)=2.
握手定理：
我们今后只讨论有限简单图：
(1) 顶点个数是有限的;
(2) 任意一条边有且只有两个不同的点与它相互关联;
(3) 若是无向图, 则任意两个顶点最多只有一条边与之相联结;
(4) 若是有向图, 则任意两个顶点最多只有两条边与之相联结. 当两个顶点有两条边与之相联结时，这两条边的方向相反.
如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.
28
定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络),
记为G = (V, E , F ).
定义3 任意两点均有通路的图称为连通图.
定义4 连通而无圈的图称为树, 常用T表示树.
29
例 一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.
解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24 =16 种状态.在河东岸的状态类似记作.
由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的.
以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.
根据此图便可找到渡河方法.
30
(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)
(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)
(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0)
(1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)
河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜)
将10个顶点分别记为A1, A2, …, A10 ,则渡河问题化为在该图中求一条从A1到A10的路.
从图中易得到两条路：
A1 A6 A3 A7 A2 A8 A5 A10;
A1 A6 A3 A9 A4 A8 A5 A10.
2017/8/16
图的矩阵表示
⑴ 邻接矩阵 邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A = (aij )n×n , 其中
32
无向图G的邻接矩阵A是一个对称矩阵.
⑵ 权矩阵一个n阶赋权图G = (V, E, F)的权矩阵A = (aij ) n×n , 其中
有限简单图基本上可用权矩阵来表示.
2017/8/16
33
无向图G的权矩阵A是一个对称矩阵.
34
⑶ 关联矩阵 一个有m条边的n阶有向图G的关联矩阵A = (aij )n×m , 其中
若vi是ej的始点;
若vi是ej的终点;
若vi与ej不关联.
有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个 - 1.
2017/8/16
35
一个有m条边的n阶无向图G的关联矩阵A = (aij )n×m , 其中
若vi与ej关联;
若vi与ej不关联.
无向图的关联矩阵每列的元素中有且仅有两个1.
36
2、最短路径算法
定义1 设P(u, v) 是赋权图G = (V, E , F) 中从点u到v的路径, 用E(P) 表示路径P(u, v)中全部边的集合, 记
则称F (P)为路径P(u, v) 的权或长度(距离).
定义2 若P0 (u, v) 是G 中连接u, v的路径, 且对任意在G 中连接u, v的路径P (u, v)都有
F (P0)≤F(P),
则称P0 (u, v) 是G 中连接u, v的最短路.
37
重要性质：
若v0 v1 … vm 是图G中从v0到vm的最短路, 则1≤k≤m, v0v1 … vk 必为G中从v0到vk的最短路.
即：最短路是一条路，且最短路的任一段也是最短路.
求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.
这两种算法均适用于有向非负赋权图.
下面分别介绍两种算法的基本过程.
南京信息工程数学系 费文龙
Dijkstra算法
指标（a为起点）    设T为V的子集，P=V-T且a∈T，对所有t∈T，设 l(t)表示从a到t的所有通路中距离最短的一条的长度，且这条路径中不包含T中其他的结点，则称l(t)为t关于集合P的指标，若不存在这样的路径，这记l(t)=∞
注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含T中其他的节点。
定理1  若t是T中关于P由最小指标的结点，则l(t)是a和t之间的最短距离。
定理2  设 T为V的子集，P=V-T，设    (1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的点构成,    (2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点, 即:l(x)=min(l(t)) (t T),    (3)令P'=P {x},T'=T-{x},l'(t)表示T'中结点t关于P'的指标,则  l'(t)=min{l(t),l(x)+w(x,t)}
南京信息工程数学系 费文龙
Dijkstra算法（求a点到其他点的最短路径）
算法步骤如下：
1. 首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。
2. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
　　若存在，d(V0,Vi)为弧上的权值
　　若不存在，d(V0,Vi)为∝
3. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
4. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的
　　距离值缩短，则修改此距离值
　　重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止）
南京信息工程数学系 费文龙
A B C D E F G H
A 0 2 ∞ ∞ ∞ ∞ 6 ∞
B 2 0 7 ∞ ∞ 1 3 ∞
C ∞ 7 0 4 3 ∞ ∞ ∞
D ∞ ∞ 4 0 5 ∞ ∞ 2
E ∞ ∞ 3 5 0 2 ∞ 2
F ∞ 1 ∞ ∞ 2 0 1 ∞
G 6 3 ∞ ∞ ∞ 1 0 4
H ∞ ∞ ∞ 2 2 ∞ 4 0
例 求下图中A点到其他点的最短路.
41
Floyd算法（求任意两点的最短路径）
设A = (aij )n×n为赋权图G = (V, E, F)的权矩阵, dij表示从vi到vj点的距离, rij表示从vi到vj点的最短路中前一个点的编号.
① 赋初值. 对所有i, j, dij = aij, rij = j. k = 1. 转向②.
② 更新dij , rij . 对所有i, j, 若dik + dk j＜dij , 则令dij = dik + dkj , rij = k, 转向③;
③ 终止判断. 若k = n终止; 否则令k = k + 1, 转向②.
最短路线可由rij得到.
南京信息工程数学系 费文龙
0 1 2 3 4 5 6 7
0 0 2 8 1 ∞ ∞ ∞ ∞
1 2 0 6 ∞ 1 ∞ ∞ ∞
2 8 6 0 7 5 1 2 ∞
3 1 ∞ 7 0 ∞ ∞ 9 ∞
4 ∞ 1 5 ∞ 0 3 ∞ 8
5 ∞ ∞ 1 ∞ 3 0 4 6
6 ∞ ∞ 2 9 ∞ 4 0 3
7 ∞ ∞ ∞ ∞ 8 6 3 0
例 求下图中任意两点间的最短路.
43
以下仅从图上进行直观操作.
根据若dik + dkj＜dij , 则令dij = dik + dkj .将原来的赋权值改变为|v2v4|=4,|v5v6|=3.
再依次改变为|v1v2|=5,|v0v2|=7.
接下来根据若dij > dik + dkj ,则删除vi到vj的连线.
2017/8/16
44
从上图中容易得到任意两点间的最短路.
例如,v1到v6的路有三条：
v1v0v3v2v6(长度为12),
v1v4v5v2v6(长度为7),
v1v4v7v6(长度为12).
45
例 设备更新问题
某企业每年年初,都要作出决定,如果继续使用旧设备,要付维修费；若购买一台新设备,要付购买费.试制定一个5年更新计划,使总支出最少.
已知设备在每年年初的购买费分别为11,11,12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18.
解 设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V={v1, v2, … , v6},点vi表示第i 年年初购进一台新设备,虚设一个点v6表示第5年年底. E ={vivj | 1≤i＜j≤6}.
46
这样上述设备更新问题就变为：在有向赋权图G = (V, E, F )(图解如下)中求v1到v6的最短路问题.
2017/8/16
47
由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5 ,v1到v6 ,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到
从上图中容易得到v1到v6只有两条路：
v1v3v6和v1v4v6.
而这两条路都是v1到v6的最短路.
48
3、最小生成树
由树的定义不难知道, 任意一个连通的(n,m)图G适当去掉m - n +1条边后, 都可以变成树, 这棵树称为图G的生成树.
设T是图G的一棵生成树, 用F(T)表示树T中所有边的权数之和, F(T)称为树T的权.
一个连通图G的生成树一般不止一棵, 图G的所有生成树中权数最小的生成树称为图G的最小生成树.

求最小生成树问题有很广泛的实际应用. 例如, 把n个乡镇用高压电缆连接起来建立一个电网, 使所用的电缆长度之和最短, 即费用最小, 就是一个求最小生成树问题.
2017/8/16
49
Kruskal算法：从未选入树中的边中选取权重最小的且不构成回路的边加入到树中.（判断回路比较麻烦）
Prim算法：把结点分成两个集合，已加入树中的(P)和未加入树中的(Q)，然后每次选择一个点在P中一个点在Q中的权重最小的边，加入树中，并把相应点加入P中。
其最小生成树如下：
类似地,可定义连通图G 的最大生成树.
2017/8/16
50
例 选址问题
现准备在 n 个居民点v1, v2, … , vn中设置一银行.问设在哪个点,可使最大服务距离最小? 若设置两个银行,问设在哪两个点?
模型假设 假设各个居民点都有条件设置银行,并有路相连,且路长已知.
模型建立与求解 用Floyd算法求出任意两个居民点vi , vj 之间的最短距离,并用dij 表示.
51
求k,使
即若设置一个银行,则银行设在 vk 点,可使最大服务距离最小.
⑵ 设置两个银行,假设银行设在vs , vt 点使最大服务距离最小.
则s,t 满足：
进一步,若设置多个银行呢？
南京信息工程数学系 费文龙
4、遍历性问题
一、欧拉图
G=(V,E)为一连通无向图
经过G中每条边至少一次的回路称为巡回；
经过G中每条边正好一次的巡回称为欧拉巡回；
存在欧拉巡回的图称为欧拉图。
二、中国邮递员问题（CPP－chinese postman problem）
一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？
这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。
南京信息工程数学系 费文龙
解法：
若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。
若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。
具体解法：Fleury算法+Edmonds最小对集算法
2017/8/16
南京信息工程数学系 费文龙
54
三、哈密尔顿图
G=(V,E)为一连通无向图
经过G中每点一次且正好一次的路径称为哈密尔顿路径；
经过G中每点一次且正好一次的回路称为哈密尔顿回路；
存在哈密尔顿回路的图称为哈密尔顿图。
四、旅行商问题（TSP－traveling salesman problem）
一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？ 即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路）
对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。
TSP问题的解法属于NP完全问题，一般只研究其近似解法
南京信息工程数学系 费文龙
55
最邻近算法
(1) 选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2) 找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3) 重复(2)直到所有的结点都加入到路径中.(4) 将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.

其他数值算法： 人工神经元方法， 遗传算法等等
什么是网络?
网络: 一个通过链接互相关联的实体的集合.
互为朋友的人
互相链接的计算机
互相指向的网页
互相作用的蛋白质
过去的网络
图在过去被用作为现有网络制作模型 (举例来说. 有公交网络, 社会网络)
通常这些网络都很小
网络可以通过目视检查进行研究从而可以发现大量信息
现在的网络
更多的、更大型的网络出现了
科技进步的产物
例如：互联网，网页
我们收集更多、更好、更复杂数据的能力
例如： 基因调控网络
由数以千计、数以万计甚至数以亿计的结点所组成的网络
不可能形象化
因特网地图
因特网
网络的类型
社会网络
知识 (信息) 网络
科学网络
生物网络
社会网络
链接表示社会中的互动
熟人的网络
协作网络
演员的网络
合作作者的网络
导演的网络
电话呼叫网络
e-mail 网络
IM 网络
蓝牙网络
性网络
主页/博客网络
知识（信息）网络
结点代表信息, 链接是信息的联系
引文网络 (有向无循环的)
网络 (有向的)
点对点网络
词网络
基于信任的网络
图形软件
科学网络
为商品分配所建的网络
互联网
路由器标准, AS 标准
能量格
航班网络
电话网络
交通网络
公路，铁路，行人交通
生物网络
网络代表生物系统
蛋白质相互作用网络
基因调控网络
基因共同表达网络
代谢路径
食物网
神经网络
理解大型的图
关于现实生活网络的数据有哪些？?
我们可以解释网络是怎样产生的吗？
关于网络性质的研究
1999年左右
Watts and Strogatz, Dynamics and small-world phenomenon（动力学和小世界现象）
Faloutsos3, On power-law relationships of the Internet Topology（基于权利-法律关系的互联网拓扑）
Kleinberg et al., The Web as a graph（作为一张图的互联网）
Barabasi and Albert, The emergence of scaling in real networks（现实网络中标度的出现）
现实网络的性质
大多数结点只有少数的邻居 (度), 但也有一些结点有很高的度数 (度的幂律分布)
无标度网络
如果一个结点 x 连接着 y和 z,那么y 和 z 就很可能是连接的
高聚类系数
大多数结点平均只相距几条边的距离
小世界网络
各个不同领域的网络 (从因特网到生物网络) 有着相同的性质
是否有可能有一个统一的基本生成过程？
小世界网络
例如：六度分离理论
但是有超过六十亿人口生存在这个世界上！
小世界网络
(a) 蛋白质 (b) 神经元 (c) 互联网
生成随机图
经典图形理论模型 (Erdös-Renyi)
每条边的独立产生概率为P

很好的研究模型，但是:
大多数顶点的度大致上相同
两个结点相连的概率与它们是否共有一个邻居结点无关
平均路径短
现实网络建模
现实生活网络不是随机的
我们是否可以定义一个模型，它能够产生与现实生活中相似的具有统计性能的图?
一系列关于随机图的模型
网络的作用过程
理解网络的结构为什么重要?

流行病学: 病毒在无标度网络中传播地更快
随机接种疫苗的结点无法正常工作，但有针对性的疫苗接种是非常有效的
网络结构
随机网络
无标度网络
网络结构
随机网络VS无标度网络
网络
网络结构
网络搜索
第一代搜索引擎: 万维网只是作为一个文件的集合
因为垃圾邮件发送者，无实质内容

------【以上为无格式内容概要，如需完整内容请下载】------