邻接矩阵与关联矩阵「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

【邻接矩阵】

定义：
设无向图$G=(V,E)$,其中顶点集$V={v_1,v_2,...,v_n}$，边集$E={e_1,e_2,...,e_\varepsilon}$。用$a_{ij}$表示顶点$v_i$与顶点$v_j$之间的边数，可能取值为0,1,2,…，称所得矩阵$\mathbf A=\mathbf A(G)=(a_{ij})_{n\times n}$为图G的邻接矩阵

若干性质

• $\mathbf A(G)$为对称矩阵
• 若G为无环图，则$\mathbf A(G)$中第i行（列）的元素之和等于顶点$v_i$的度
• 两图G和H同构的充要条件是存在置换矩阵P使得$\mathbf A(G)=\mathbf P^T\mathbf A(H)\mathbf P$

类似地，有向图D的邻接矩阵$\mathbf A(D)=(a_{ij})_{n\times n}$, $a_{ij}$表示从始点$v_i$到终点$v_j$的有向边的条数，其中$v_i$和$v_j$为D的顶点

示例，求图所示简单图的邻接矩阵？

解：根据定义，可求得该无向图的邻接矩阵为

$$\begin{bmatrix}0 & 1 & 1 & 1 \\1 & 0 & 1 & 0 \\1 & 1 & 0 & 1 \\1 & 0 & 1 & 0 \\\end{bmatrix}$$

注：邻接矩阵是描述图的一种常用的矩阵表示。

【关联矩阵】

定义：
设任意图$G=(V,E)$，其中顶点集$V={v_1,v_2,...,v_n}$，边集$E={e_1,e_2,...,e_\varepsilon}$。用$m_{ij}$表示顶点$v_i$与边$e_j$关联的次数，可能取值为0,1,2,…，称所得矩阵$\mathbf M(G)=(m_{ij})_{n\times \varepsilon}$为图G的关联矩阵

类似地，有向图$D$的关联矩阵
M(D)=(mij)n×ε

$\mathbf M(D)=(m_{ij})_{n\times\varepsilon}$的元素$m_{i\times j}$定义为：

$$m_{ij}=\begin{cases}1, & v_i是有向边 a_j的始点 \\[3ex]-1, & v_i是有向边 a_j的终点 \\[2ex]0, & v_i是有向边 a_j的不关联点\end{cases}$$

示例，求图中有向图的邻接矩阵和关联矩阵。

解：根据定义，可求得该有向图的邻接矩阵:

$$\begin{bmatrix}0 & 1 & 1 & 0 \\0 & 0 & 0 & 0 \\0 & 1 & 0 & 1 \\1 & 0 & 0 & 0 \\\end{bmatrix}$$

关联矩阵:

$$\begin{bmatrix}1 & 0 & 0 & -1 & 1 \\-1 & -1 & 0 & 0 & 0 \\0 & 1 & 1 & 0 & -1 \\0 & 0 & -1 & 1 & 0 \\\end{bmatrix}$$

注：关联矩阵是描述图的另一种矩阵表示。