matlab图论模型和算法

图论算法简介

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

要求从以点出发走过所有的路径。

图论 (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函数相互转化。

网络分析工具箱

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

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