郑州网站免费制作/百度竞价是什么

简介

图论是一个非常著名的领域，实际上，在现实生活中，万物相互依存，彼此限制，这纷繁复杂的关系形成的是一个复杂的网络。其复杂度几乎是不可测量，这也许就是大自然的美妙之处。不过，在研究某些特定问题中的复杂关系时，我们还是有方法的，那就是图论，图论可以将非常复杂的关系可视化，用结点表示客观对象，用边表示对象与对象的关系，这样就将问题抽象成了一个图，使得我们可以用图的性质和结论来解决问题。常见的图论问题主要有：求一个最短路，求最小生成树，求最短回路，最大流、最小流问题。这里重点介绍一些概念，简单介绍算法的使用。

基本概念

图论(Graph theory) 以图为研究对象，研究顶点和边组成的图形的数学理论和方法。图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形。图论中的图通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用边表示相应两个事物间的关系。

无向图

无向图的构成有三部分：顶点集（V），边集（E），关联函数（${\phi }_G(e)=xv=vx$，其中$e\in E,x、v\in V$）。显然这里的这三个部分将一个图中最主要的东西清楚的表达了出来，其中，顶点集和边集容易理解，关联函数是一个从边集到顶点集的映射，表示讲边和它两端的顶点联系起来。

环：当一条边的两个端点重合时，这就形成了一个环。连杆：我们常识中的边就是连杆，在一个图中，除了环之外都是连杆。重边：两条边的具有相同的两个顶点。重边也是连杆。

有向图

有向图的构成有三个部分：**顶点集（V），弧集（A），关联函数（${\phi }_G(a)=<x,v>$，其中$a\in A，x、v\in V$）。这三个部分和无向图的三个部分是非常类似的，不过有一点不同的是有向图的关联函数中顶点是有序的，这也就是有向图的方向所在。

子图

听名字就应该知道，这是一个基于集合子集定义的概念，关于图的构成中，我们有三个集合，但是子图的定义是在顶点集和边集的子集上定义的。对于$G$的子图$H$数学表示如下：$$V(H)\subset V(G)\wedge E(H)\subset E(G)$$通俗来讲：子图就相当于在原图中去掉了一些边和顶点，而原图也是一个子图。

特殊的图

完全图，完全二分图，星图，连通图，不连通图，路，圈，数等。
完全图就是指图中的每一个顶点到其他每个顶点都有边，连通图就是指从图的每个顶点都能够到达其他顶点。不连通图就是存在一个不能到达的顶点就是不连通的。这里简单的介绍了一些常用的图，从名字上很容易理解这个概念，这些特殊图的意义就是他们有一些很好的性质，这些性质便于对实际问题建模或者是解决实际问题。所以下面的问题应运而生，如果构造特殊的图，如何判断特殊的图，这是比较复杂的数学问题，但是有成熟的知识体系可以参考，日后根据需求再深入研究。

图的数据结构

图的数据结构可以称之为图的矩阵表示（因为矩阵是一种数学工具，又可以称为图的数学表示）。在我们的直觉中，图是有非常直观的图像的，但是当我们使用图论解决问题的时候，还是得用数学形式。

主要有关联矩阵和邻接矩阵。在无向图中，关联矩阵中的数字表示边与顶点的关联次数，邻接矩阵中的值表示从顶点到顶点的边的数量，若顶点存在环的话，则该顶点到本身的边有两条。在有向图中稍微有些不同，有向图的关联矩阵中数字的取值有三种{1，-1,0}，1表示与之相关联的边的头，-1表示与之相关联的边的尾，0表示不存在边与顶点关联。邻接矩阵中的数字取值有两种{0,1}，0表示不存在顶点到顶点的边，1表示存在顶点到顶点的边。这里借助具体的图理解比较容易。

度

度时顶点的一个性质。度：表示与顶点相连的边的条数，如$d_G(v)$表示与定点$v$相连的边的条数。在有向图中还有入度和出度的概念，出度如$d^{-}(v)$表示以顶点$v$为尾的边的个数，入度如$d^{+}(v)$表示以顶点$v$为头的边的个数。其实这里可以顾名思义，概念非常简单。

另外还有

• 点度中心度，值就是点的入度。$$C_D(v)=d^{+}(v)$$
• 接近中心度，某个点到其他所有点的距离的和的倒数，距离越大，说明该点与其他点越不接近，则倒数就会越小，接近中心度就越小。$$C_D(v)=\frac{1}{{\sum }_{u\in V}d(u,v)}$$
• 中间中心度，表示一个结点作为其他两个结点的最短路径的中间点的比例或者是频率。比如：在两个点中间的最短路径有3点，其中点$v$最为中间点的有两条，则点$v$的中间中心度为$\frac{2}{3}$。$$C_B(v)=\sum _{s̸=t̸=v\in V}\frac{{\sigma }_{st}(v)}{{\sigma }_{st}}$$
• 特征向量中心度，鉴于线性代数的差距，这里先不介绍这个，等日后查阅资料再补充

常见问题

稀疏矩阵

我们可以发现，在实际中，在邻解矩阵中，一行经常会有很多0出现，而有用的数据却是非常的少。但是由于矩阵的庞大，会影响计算速度和时间，所以在进行计算的时候我们一般都是使用的稀疏矩阵。所谓稀疏矩阵就是将满矩阵中有用的数据提取出来，将它的行数和列数所表示的序数对与它的矩阵的数值形成一一对应的映射关系，将这种映射关系的数据结构称为稀疏矩阵。这样在稀疏矩阵中，我们所进行计算的就都是有用的元素的了。

matlab函数

计算稀疏矩阵
使用的命令就是sparse，参数$w$表示原矩阵，$W$表示稀疏矩阵。

W = sparse(w) 

计算最短路
参数$W$是稀疏矩阵，1,6表示起止点。参数’Directed’，0 表示该图是无向图（0或false）。返回值Dist是最短路的距离，Path是最短路径。

%    a b c d e f
w = [0 0 0 0 0 0    % a2 0 0 0 0 0    % b3 6 0 0 0 0    % c0 5 0 0 0 0    % d0 3 1 1 0 0    % e0 0 0 2 4 0];  % f
W = sparse(w);      % 计算稀疏矩阵% 计算最短路， 而且是无向图
[Dist,Path] = graphshortestpath(W, 1, 6,'Directed',0);

计算最小生成树
这里使用的$w$是图的边权矩阵。返回值中ST表示的就是最小生成树的稀疏矩阵。

% 原矩阵
w = [ 0   4  inf  5  inf  3          % w(i,j)表示边权，inf表示没有边4   0   5  inf  3   3inf  5   0   5   3  inf5  inf  5   0   2   4inf  3   3   2   0   13   3  inf  4   1   0];% 计算稀疏矩阵
W = sparse(w);  % 计算最小生成树
[ST, pred] = graphminspantree(W);

最短回路
参数dist表示的是图的距离矩阵，特别的是这个距离矩阵在每个点上都有值。返回值order表示的是最短回路的点的顺序，totaldist是最短回路的距离。最短回路又称最小汉密顿路。

[order,totdist] = minhamiltonpath(dist);

总结

这里介绍的内容和程序比较简单，但是其中的数学原理是非常复杂的。另一方面在实际应用中，将问题抽象成图，根据需要划分子图，将方案可视化都是比较复杂的步骤，需要自己根据实际的问题进行作业。以上的内容一定要在实际中加强，在实际中深入，理解其本质。

案例分析

待之后做完案例后继续更新。。。。