数学建模第四章 图与网络模型及方法
BrotherCall
·
·
个人记录
基础概念
无向图：G = (V , E)
有向图：D = (V , A)
有向边又称为弧。
弧 $a_k = (v_i , v_j)$ 表示 $v_i \to v_j$，$v_i$ 称为始端，$v_j$ 称为末端或终端。$a_k$ 称为 $v_i$ 的出弧，也称为 $v_j$ 的入弧。
环：即自环。
重边：端点是同一对顶点的多条边
简单图：无环无重边。
完全图：任意两顶点均相邻的简单图。
赋权图：带权的图。
子图：点集边集都被包含。
生成子图：在是子图的情况下点集相同。
道路：$W = v_0e_1v_1e_2\cdots e_kv_k$。
迹：各边相异。
轨道：各顶点相异。
回路：起点和终点重合的道路。
圈：起点和重点重合的轨道。
连通的：顶点 $u$ 到顶点 $v$ 有道路。
连通图：任意两点连通的图。
连通分支：分连通图中的连通子图。
## 矩阵表示
### 邻接矩阵
**无向图**邻接矩阵 $W = (w_{ij})_{n\times n}
w_{ij} =
\begin{cases}
1 & 顶点\ v_i\ 与\ v_j\ 相邻 \\
0 & i=j\ 或顶点\ v_i\ 与\ v_j\ 不相邻
\end{cases}
有向图邻接矩阵 W = (w_{ij})_{n\times n}
w_{ij} =
\begin{cases}
1 & 弧(v_i,v_j) \in A\\
0 & i=j\ 或顶点\ v_i\ 到 \ v_j\ 无弧 \\
\end{cases}
无向赋权图 W = (w_{ij})_{n\times n}
w_{ij} =
\begin{cases}
顶点\ v_i\ 与 \ v_j\ 之间的边权\\
0(或\infty) & i=j\ 或顶点\ v_i\ 与\ v_j 之间无边 \\
\end{cases}
Matlab
graph % 无向图
diagraph %有向图