图论算法简介

图论起源于哥尼斯堡七桥问题

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

概念、算法

图（无向图）的构成

图的构成： 顶点集 边集 关联函数
顶点集V(G): 图G中所有顶点的集合
边集E(G): 图G中所有边的集合
关联函数φ_G： φ_G:E(G)→V(G)
环： 端点重合为一点的边。
连杆： 端点不重合的边。
重边： 具有相同的两个端点的边。

上图就可以描述成：
 V(G)={u,v,w,x,y}
 E(G)={a,b,c,d,e,f,g,h}
  φ_G(e)=vx或xv（无向）
 b为环
 a为连杆
 d、f为重边
有向图和无向图差别就在路线上是否有箭头。

图（有向图）的构成

有向图构成： 顶点 弧集 关联函数
顶点集V(G): 图 G 中所有顶点的集合。
弧集 A(G)： 图 G 中所有弧的集合。
关联函数 φ_G： φ_G : A(a) →V(G)
上图就可以描述成：
 V(G)={u,v,w,x,y}
 A(G)={a,b,c,d,e,f,g,h}
  φ_G(a)=uv
子图： 在原图上去掉一些边和节点的图。
完全图： 图中任意两点都有边相连。
完全二分图： 节点可以被分为两部分，它们之间任意两个节点都有边相连。
星图： 为完全二分图演化出来的，当其中一个集合中只有一个节点的时候，就是星图。
**连通图：**点与点直接可以通过若干边就能到达。
**不连通图：**点与点之间存在无法通过边到达的情况。

图与网络的数据结构

无向图关联矩阵/邻接矩阵

关联矩阵 M = (m_ve)， m_ve ∈{0,1,2}表示边 e 与顶点 v 关联的次数。

邻接矩阵 A = (a_uv)， a_uv 表示是否存在从顶点 u 到 v 的弧。

有向图关联矩阵/邻接矩阵

关联矩阵 M = (m_va)， m_va∈(1,−1,0)分表示弧 a 与顶点 v关联的关系（尾、头、其它）。

邻接矩阵 A = (a_uv)， a_uv表示是否存在从顶点 u 到 v 的弧。

顶点的度和中心度

度d_G(v)： G 中 与 v 关 联 的 边 数，d_G(v) = d^-(v) + d⁺(v)。
出度d^-(v) : 以 v 为弧尾，起始于该点的弧数。
入度 d⁺(v): 以 v 为弧头，终止于该点的弧数。

这里d^-(v)= 3；d⁺(v)=2。
点度中心度
接近中心度
一个顶点到其他所有顶点的距离和的倒数

中间中心度
作为最短路径中间节点的频率

特征向量中心度

matlab中包含的与图论相关的一些函数

调用这些函数/工具箱前的准备

无向图做一个下三角矩阵即可


可以看到写成的矩阵含有很多的0，因此也可以改写成稀疏矩阵

两种矩阵类型可以通过full和sparse函数相互转化。

网络分析工具箱

不是自带的，好像需要下载

教程中大概讲了一个赈灾巡查的案例，提到了使用启发式算法和图论模型结合优化方案。感觉这是一个比较好的例子，同时对于我来说也比较复杂，我会单独写一篇对这个案例算法优化的讨论。