图论(简化)

一、图论算法

1. Relaxation(松弛操作)：

procedure relax(u,v,w:integer);//多数情况下不需要单独写成procedure。

begin

if dis[u]+w

begin

dis[v]:=dis[u]+w;

pre[v]:=u;

end

end;

2. Dijkstra

1) 适用条件&范围：

a) 单源最短路径(从源点s到其它所有顶点v);

b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)

c) 所有边权非负(任取(i,j)∈E都有Wij≥0);

2) 算法描述：

a) 初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s};

b) For i:=1 to n

1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}

2.S=S+{u}

3.For V-S中每个顶点v do Relax(u,v,Wu,v)

c) 算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点

3) 算法优化：

使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。

使用Fibonacci Heap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用Radix Heap可以达到O(E+V㏒C)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。

4) 程序：

注：程序使用二叉堆

3. Bellman-Ford

1) 适用条件&范围：

a) 单源最短路径(从源点s到其它所有顶点v);

1 子图

子图(subgraph) H  G  V(H)  V(G) , E(H)  E(G) 。

真子图 H  G。

母图（super graph）。

生成子图（spanning subg.）  H  G 且V(H) = V(G) 。

生成母图。

基础简单图 （underlying simple g.）。

导出子图（induced subg.）G[V’], (非空V’ V )

 以V’为顶点集，以G中两端都在V’上的边全体为边集构成的G的子图。

边导出子图 G[E’] 非空E’  E

 以E’为边集，以E’中所有边的端点为顶点集的的子图。

G[{c, d, e}]G[{f, c]}

例。

eabcdfghG=(V, E)xwvyuG[{u,w,x,y}]G[{u,w,x}]

以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算：

G - V’  去掉V’及与V’相关联的一切边所得的剩余子图。

 即 G[V \ V’]

G - E’  从中去掉E’ 后所得的生成子图

例。G - {b, d, g}, ( = G[E \ {b, d, g}] )

G - {b, c, d, g}, (  G[E \ {b, c, d, g}] )

G - {a, e, f, g}. (  G[E \ {a, e, f, g}] )

注意 G[E \ E’] 与G - E’ 虽有相同的边集，但两者不一定相等 ： 后者一定是生成子图，而前者则不然。

上述四种运算是最基本取子图运算，今后老要遇到，一定要认真掌握好。关于子图的一些定义还有：

G + E’  往G上加新边集E’ 所得的（G的母）图。

1. 3 图论

图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应用。但很多图论问题虽易表达，却难以求解，其中有相当多的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MPI编程实现，包括传递闭包、连通分量、最短路径和最小生成树等。

1.1 传递闭包

设A是一个含N个顶点的有向图G的布尔邻接矩阵(Boolean Adjacent Matrix)，即元素aij=1当且仅当从顶点i到j有一条有向边。所谓A的传递闭包（Transitive Closure），记为A+，是一个N×N的布尔矩阵，其元素bij=1当且仅当：①i=j；或②从i出发存在有向路径到j，又称为顶点i到j可达。从G的布尔邻接矩阵A求出G的传递闭包，就称为传递闭包问题。

传递闭包问题有很强的应用背景，在科学计算中广泛存在。传递闭包问题的经典解法之一就是利用布尔矩阵的乘法来求解。本节将把这一算法分别在串行和并行机上实现。

1.1.1 传递闭包串行算法

利用布尔矩阵相乘求解传递闭包问题的原理为：对于布尔矩阵(A+I)k中的任一元素bij，bij=1表示从i到j存在长度小于等于k的可达路径，否则，bij=0。显然对于k=1，(A+I)1中bij=1当且仅当从i到j路径长度为0（i=j）或为1（从i到j存在有向边）；(A+I)2中，bij=1当且仅当从i到j路径长度小于等于2；((A+I)2) 2中，bij=1当且仅当从i到j路径长度小于等于4，等等。因为任意两点间如果存在可达路径，长度最多为N-1，所以k≥N-1时，(A+I)k就是所求的传递闭包A+。于是(A+I)矩阵的㏒N次自乘之后所得的矩阵就是所求的传递闭包。

根据前面的叙述，很自然的有下面的传递闭包串行算法15.1，其时间复杂度为O(N3㏒N)。

算法 15.1传递闭包串行算法

输入：图G的布尔邻接矩阵A

输出：A的传递闭包M

图论的基本概念与应用

图论作为一门理论研究和应用探索的数学学科，不仅在学术和工程领域发挥着巨大作用，而且在现代科技和日常生活中也处处体现。本文将简单介绍图论的基本概念、应用领域，以及一些相关案例。

一、基本概念

图论的研究对象是图。图是由一些点和连接这些点的线组成的，表示事物之间的某种关系，如网络中的路由、社交网络中的朋友等等。根据点与线的不同特征，图被分为有向图和无向图。

有向图中的边是有方向的，表示两个节点之间是起点和终点的关系。无向图中的边没有方向，表示两个节点之间是双向的。图的另一个重要概念是网络，网络是在边上赋予权值用以表示边的强度或距离的图。

在图论中，我们常用的还有度数和路径的概念。度数是一个点相邻边的数量，路径是由若干个顶点和它们之间的边所构成的序列，且顶点之间按照连接的顺序排列。

二、应用领域

图论被广泛应用于计算机科学、运筹学、生物学、化学、经济学等领域。在计算机科学中，图论被用于构建搜索引擎、路由算法等多个方面。

在运筹学中，最短路径算法、匹配算法、流量分配算法等问题可通过图论求解。生物学中，图以蛋白质相互作用网、基因调控网等方式表现生物体内的复杂关系。

在化学中，图被用于描述分子之间的行为和作用。在经济学中，图常常被用于解决网络流量调度和供应链计算。

三、相关案例

1. 社交网络

在社交网络中，我们可以将人视为节点，人与人之间的关系视为边，从而构建出一个网络模型。通过对网络模型的分析，可以发现一些有趣的现象或规律，比如弱连接理论、六度分离理论等，这些理论不仅仅能被应用于社交网络，还可以用于其他领域的研究。

2. 铁路路径优化

一个问题是如何生成铁路的最短路径，它既可以被看作是一个有向图问题，也可以看作是一个网络流问题。由于铁路上存在许多互联的节点，因此在这种情况下，图论技术可以用于优化路径，解决径路选择和路径总长度最小化等问题。

3. 分子结构预测

化学家常常利用图论的相关技术来模拟和预测分子的结构。在这种情况下，节点表示原子，边表示原子之间的化学键。通过对分子结构的图论分析，可以预测分子的稳定性、性质等。