图是一种数据结构和模型,在计算机中存储图的最简单有效方式就是矩阵。矩阵作为表达图有效工具和手段,也便于运用代数的方法研究图的性质(这才是重点!),例如,我们可以通过矩阵计算结果,判定图的连通性/可达性等问题。
一、邻接矩阵(adjacency matrix)
定义1 设 G = (V,E)是一个图,节点集合$ V = { v_1, v_2, \dots, v_n}$,令 $ A(G) = [a_{ij}]_{n\times n}$,其中:
\[a_{ij} =\begin{cases} 1 \quad &若[v_i, v_j] \in E\\ 0\quad &若[v_i, v_j] \notin E \end{cases} \]则称A(G)为\(G\) 的**邻接矩阵。
【例1】设G1 是有向图、G2 是无向图,分别如下图(a)和(b)所示,写出G1,G2 的邻接矩阵。
**解: **
\(A(G_1)\) | \(A(G_2)\) |
---|---|
$\begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix} $ | \(\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{bmatrix}\) |
当结点编号次序不同时,同一个图所得的邻接矩阵可能不同,但可以通过有限次的行、列变换而得到相同的邻接矩阵(同构的图?)。
通过图的邻接矩阵运算,可以判断图的一些性质。设G=(V,E) 是有向图, $|V| = n $ ,\(A\)是G 的邻接矩阵。
1.1 \(AA^T\)的元素的意义
可知,\(b_{ij} = \sum^n_{k = 1} a_{ik} a_{jk}\) ,如上图所示,则在G中恰好有\(b_{ij}\)个结点,从\(v_i\) 和\(v_j\) 均有边引出到这些节点\(v_{k_1}, v_{k_2}, \dots, v_{k_n}\)。特别地,当\(i =j\)时\(b_{ij}\)表示 \(v_i\)的出度。
1.2 \(A^{2} = A\times A\)的元素的意义
若有\(b_{ij} = \sum^n_{k = 1} a_{ik}a_{kj}\),则从\(v_i\) 到\(v_j\) 长度为2 的路有\(b_{ij}\) 条。特别地,当\(i=j\)时\(v_i\) 到自身长度为2 的回路有 $b_{ij} $条。
1.3 有向图的路(path)
【例2】对于有向图G=(V,E),用 G 的邻接矩阵计算从顶点 \(v_3\)到 \(v_1\) 的所有有向通路 。
解:图G 的邻接矩阵为:
由\(A[3][1] = 0\) 知(下标从1开始),从顶点\(v_3\)到 \(v_1\)没有长度为 1 的通路。再计算$A^2 $:
\[\begin{aligned} A^2[3][1] &= A[3][1] \times A[1][1] + A[3][2] \times A[2][1] \\ &+ A[3][3] \times A[3][1] + A[3][4] \times A[4][1] \\ &= 0 \times 0 + 1 \times 0 + 0\times 0 + 1 \times 1 = 1 \end{aligned}\]得到从顶点\(v_3\) 到\(v_1\)的长度为 2 的有向路为\((v_3, v_4, v_1)\)。显然,它也是一条通路。再计算\(A^3\):
\[A^3 =\begin{bmatrix} 1 & 2 & 0 & 1\\ 1 & 2 & 2 & 2 \\ 1 & 3 & 1 & 2 \\ 1 & 2 & 1 & 2 \end{bmatrix} \]由 $ A^3[3][1] = 1 $知,从顶点 \(v_3\) 到\(v_1\) 的长度为3的路有1条。根据计算过程:
\begin{aligned} A^3[3][1] &= A^2[3][1] \times A[1][1] + A^2[3][2] \times A[2][1] \\ &+ A^2[3][3] \times A[3][1] + A^2[3][4] \times A[4][1] \\ &= 1 \times 0 + 1 \times 0 + 1\times 0 + 1 \times 1 = 1 \end{aligned}
得到从顶点\(v_3\)到\(v_1\) 的长度为3的有向路为:从顶点\(v_3\) 到\(v_4\) 的一条长度为2的路接上\((v_4, v_1)\) 。再根据计算过程:
\begin{aligned} A^2[3][4] &= A[3][1] \times A[1][4] + A[3][2] \times A[2][4] \\ &+ A[3][3] \times A[3][4] + A[3][4] \times A[4][4] \\ &= 0 \times 0 + 1 \times 1 + 0\times 1 + 1 \times 0 = 1 \end{aligned}
得到从顶点\(v_3\) 到\(v_4\) 的一条长度为2 的有向路是\((v_3,v_2, v_4)\)。所以,从顶点\(v_3\) 到\(v_1\) 的长度为 3的有向路是 \((v_3, v_2, v_4, v_1)\) 。显然,它也是一条通路。
因为对于4个节点的有向图,当路的长度超过3 时,必定不是通路,所以从顶点\(v_3\) 到\(v_1\) 的通路共有两条:\((v_3, v_4, v_1)\)和$(v_3, v_2, v_4, v_1) $ 。
二、可达矩阵
定义2 设G=(V,E)是一个图,节点集合\(V = \{ v_1, v_2, \dots, v_n\}\),令\(P(G) =[p_{ij}]_{n \times n}\) ,其中:
\[p_{ij} =\begin{cases} 1 \quad &若从 v_i可达 v_j\\ 0 \quad &若从 v_i不可达 v_j \end{cases} \]则称 \(P(G)\) 为G 的可达矩阵。
可达矩阵用于描述一个图中,任一节点到另一节点之间是否存在路。由于在图中「两个结点之间有路」,则「必存在长度小于等于 \(n−1\) 的通路」。另外,一般认为「同一个结点到自身可达」。因此,可用以下公式计算 $$P(G) = [p_{ij} ]_{n\times n} = A^0 \lor A^1 \lor \cdots \lor A^{n - 1}$$
其中,\(A^0\) 是$ n\times n$的单位矩阵, \(∨ \lor ∨\) 是析取(或逻辑加/并)运算。即「顶点 \(v_i\)到达\(v_j\)有长度为零的路、或有长度为1 的路、……、或有长度为 \(n−1\) 的路」,这些路可能是通路、可能不是,但其中至少存在一条通路。
【例4】设有向图D=(V,E),请回答下列问题。
(1)图 D 中\(v_1\)到\(v_3\) 长度为3的通路有多少条?
(2)图 D 是哪种类型的连通图?
解:
(1) D 的邻接矩阵及其幂次为:
\(A^0\) | \(A^1\) | \(A^2\) | \(A^3\) |
---|---|---|---|
$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $ | \(\begin{bmatrix} 0 & 1 & 1 & 1\\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix}\) | \(\begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}\) | \(\begin{bmatrix} 0 & 1 & 1 & 2\\ 1 & 0 & 1 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}\) |
由 \(A^3[1][4] = 2\) 知, $v_1 $ 到\(v_4\) 共有两条长度为3的路,计算过程如下:
\begin{aligned} A^3[1][4] &= A^2[1][1] \times A[1][4] + A^2[1][2] \times A[2][4] \\ &+ A^2[1][3] \times A[3][4] + A^2[1][4] \times A[4][4] \\ &= 1 \times 1 + 0 \times 0 + 1 \times 1 + 1 \times 0 = 2 \end{aligned}
\begin{aligned} A^2[1][1] &= A[1][1] \times A[1][1] + A[1][2] \times A[2][1] \\ &+ A[1][3] \times A[3][1] + A[1][4] \times A[4][1] \\ &= 0 \times 0 + 1 \times 1 + 1 \times 0 + 1 \times 0 = 1 \end{aligned}
\begin{aligned} A^2[1][3] &= A[1][1] \times A[1][3] + A[1][2] \times A[2][3] \\ &+ A[1][3] \times A[3][3] + A[1][4] \times A[4][3] \\ &= 0 \times 1 + 1 \times 1 + 1 \times 0 + 1 \times 0 = 1
\end{aligned}
即这两条长度为 3 的路为\((v_1,v_2, v_1, v_4)\)和\((v_1,v_2, v_3, v_4)\) 。其中\((v_1,v_2, v_3, v_4)\) 是一条通路,所以 D 中 \(v_1\)到\(v_4\)长度为 3的通路有一条。
(2)计算 D 的可达矩阵。显然D 不是强连通的,因为\(v_3\)到 $ v_1$是不可达的;D是单侧连通的(即对于任意顶点偶对,至少一个节点到另一个节点是可达的)。
\(P\) | \(P^T\) | \(P\or P^T\) |
---|---|---|
\(P = A^0 \lor A^1 \lor A^2 \lor A^3 =\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}\) | \(\begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}\) | \(\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}\) |
三、赋权矩阵
加权有向图的带权邻接矩阵
若为有向图D=(V,E)的每条边赋予一个权数,则称D为加权有向图。
设D=(V,E)是一个简单加权有向图,$V={ν_1,ν_2,...,ν_n\},则D的邻接矩阵 \(A=(a_{ij})_{n×n}\),其中
【例5】给出有向图D=(V,E)的赋权矩阵。
图D | 权矩阵 |
---|---|
![]() |
![]() |
四、关联矩阵
4.1 无向图的关联矩阵
设 G=(V,E)是一个无向图,\(V=\{v_1,v_2,...,v_n\}\),\(E=\{e_1,e_2,...,e_m \}\),则 G的关联矩阵 \(M=(m_{ij})_{n×m}\),
其中
无向图的关联矩阵每一列的元素之和为2,且第\(i\)行的元素之和是\(ν_i\)的次数,简单图的关联矩阵是(0,1)矩阵。
【例6】给出无向图D=(V,E)的关联矩阵。
无向图 | 关联矩阵 |
---|---|
![]() |
![]() |
4.2 有向图的关联矩阵
设 G=(V,E)是一个有向图,\(V=\{v_1,v_2,...,v_n\}\),\(E=\{e_1,e_2,...,e_m\}\),则 G的关联矩阵\(M=(m_{ij})_{n×m}\),
其中