# 图的矩阵表示

# 邻接矩阵 (adjacency matrix 或 connection matrix)

设 G=(V,E) 是一简单图 (有向或无向)，|V|=n ，并且设$V=\{v_1,v_2...v_n\}$ 已被强行命名。则定义 n 阶方阵
$A=(a_{ij})_{n\times n}$, 其中:

$$a_{ij}= \begin{cases} 1，&若(v_i,v_j)\in E\\ 0，&若(v_i,v_j)\notin E \end{cases}$$

为图 G 的邻接矩阵。

图 G 是无向图$\iff$ 其邻接矩阵是对称矩阵。

结论：

1. 每个简单 (有向或无向) 图都与一 个主角线元素全为零的 0～1 方阵对应；每个主角线元素全为零的 0～1 方阵都与一 个简单图对应；
2. 对于一个$(n,m)-$ 图来说，由于 n 个结点有$n!$ 种强行命名法，故应有$n!$ 个邻接矩阵。从《线性代数》的知识可知：矩阵的行与列顺序对调，是对矩阵进行了所谓的基本初等变换。而对矩阵施行基本初等变换，不会改变矩阵的本质性质 —— 即这$n!$ 个主角线元素全为零的 0～1 方阵都表示同一个图
3. 两个简单图同构$\iff$ 其邻接矩阵经过行与列的顺序对调后，相同；
4. 一图 G 是零图$\iff$ 其邻接矩阵 A 是全 0 矩阵；
5. 图 G 是完全图$\iff$ 其邻接矩阵 A 除主对角线外均是 1
6. 在有向图 G 的邻接矩阵 A 中
   其行和等于对应结点的出度。即$\displaystyle \sum_{k=1}^n a_{ik}=\overleftarrow{dev}(v_i)$
   其列和等于对应结点的进度。即$\displaystyle \sum_{k=1}^n a_{ki}=\overrightarrow{dev}(v_i)$
   同一编号的行和列的和相加等于对应结点的度。即
   $\displaystyle \sum_{k=1}^n a_{ik}+\sum_{k=1}^n a_{ki}=\sum_{k=1}^n (a_{ki}+a_{ik})=dev(v_i)$
   全部 1 的个数等于边数。即$\displaystyle \sum_{j=1}^n \sum_{i=1}^na_{ij}=m$
7. 在无向图 G 的邻接矩阵 A 中
   其行和等于对应结点的度。即$\displaystyle \sum_{k=1}^n a_{ik}=dev(vi)$
   其列和等于对应结点的度。即$\displaystyle \sum_{k=1}^n a_{ik}=dev(vi)$
   全部 1 的个数等于边数的 2 倍。即$\displaystyle \sum_{j=1}^n \sum_{i=1}^na_{ij}=2m$

# 关联矩阵 (incidence matrix)

设 G=(V,E) 是一简单图 ( 有向或无向 )，|V|=n，|E|=m ， 并且设$V=\{v_1,v_2,...,v_n\}$ ， $E=\{e_1,e_2,...,e_m\}$ 已被强行命名。则 定义$n\times m$ 阶矩阵$B=(b_{ij})_{n\times m}$ 为图 G 的关联矩阵。其中：(1) 若 G 是有向图，则

$$b_{ij}= \begin{cases} 1,&如果结点v_i是边e_j的起点 \\ 0,&如果结点v_i与边e_j的不关联\\ -1,&如果结点v_i是边e_j的终点 \end{cases}$$

(2) 若 G 是无向图，则

$$b_{ij}= \begin{cases} 1,&如果结点v_i与边e_j的关联 \\ 0,&如果结点v_i与边e_j的不关联 \end{cases}$$

有向图的关联矩阵的特点是每列一个正 1，一个负 1。这正好对应相应边的起点和终点。

# 可达矩阵 (reachable matrix)

设 G=(V,E) 是一简单图 (有向或无向)，|V|=n ，并且设$V=\{v_1,v_2...v_n\}$ 已被强行命名。则定义 n 阶方阵
$R=(r_{ij})_{n\times n}$, 其中:

$$r_{ij}= \begin{cases} 1，&若从结点v_i可达结点v_j\\ 0，&若从结点v_i不可达结点v_j \end{cases}$$

为图 G 的可达矩阵

1. 对于有向图
   从结点$v_i$ 可达结点$v_j \iff$ 从结点$v_i$ 到结点$v_j$ 至少有一条有向路
   从结点$v_i$ 不可达结点$v_j\iff$ 从结点$v_i$ 到结点$v_j$ 没有有向路
2. 对于无向图
   从结点$v_i$ 可达结点$v_j \iff$ 从结点$v_i$ 到结点$v_j$ 至少有一条路
   从结点$v_i$ 不可达结点$v_j\iff$ 从结点$v_i$ 到结点$v_j$ 没有路

# 邻接矩阵的布尔幂

设 G=(V,E) 是一简单图 (有向或无向)，n 阶方阵 A 是图 G 的邻接矩阵。则递归的定义邻接矩阵 A 的布尔幂

1. $A^{(1)}=A$
2. $A^{(m+1)} =A^{(m)}\land A$
   其中：$\displaystyle a^{(m+1)}=\bigvee^n_{k=1}(a_{ik}^{(m)}\land a_{ki})(1\leqslant i \leqslant n,1\leqslant j \leqslant n)$

这里$\land$ 和$\lor$ 都是二元布尔运算：布尔乘和布尔和

可达矩阵的计算方法一：(矩阵幂算法)
可达矩阵

$$R=A\lor A^{(2)}\lor A^{(3)}\lor A^{(4)} \cdots \lor A^{(n)}$$

这里$\lor$ 是布尔和

# 可达矩阵与图的连通性

1. 有向图 G 强连通$\iff$ 可达矩阵 R 是全 1 矩阵；
2. 有向图 G 单向连通$\iff R\land R^T$ 除主对角线外均是 1；
3. 有向图 G 弱连通$\iff$ 由矩阵$A_1=A\land A^T$ 所确定的可达矩阵 R 是全 1 矩阵；
4. 有向图 G 中有有向圈$\iff$ 可达矩阵 R 的某些主对角线元素$r_{ii} =1$

# 带权图的最短路径

# 带权图 (weighted digraph)

设$G=(V,E)$ 是一简单图。称一元函数 $ w:E\to R^+$ 为图 G 的权函数，使得对于每一条边$e\in E$，均有一正实数$w(e)\in R^+$ 与之对应，称图 G 为带有权 w 的图，简称为带权图。并记为$G=(V,E, w)$。

带权图有时也称为网络 (network)。

# 最短路 (shortest path)

设$G=(V,E)$ 是一带权图。

1. 设$P=(e_{i1}, e_{i2},..., e_{ik})$ 是 G 中的一条路。则路 P 的路长定义为：
   $\displaystyle w(p)=\sum^k_{j=1}w(e_{ij})$
2. 从结点 u 到结点 v 的最短路$P_0$ 是满足下述条件的路
   $w (P_0)=min {w§ |P 为从 u 到 v 的路} $。

当带权图中各边的权值都为 1 时，则路长的定义就退化为 §3 一般图的路长定义了。

# Dijkstra 算法

略