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

全栈程序员-用户IM • 2022年10月29日下午4:46 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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的顶点

示例，求图所示简单图的邻接矩阵？
这里写图片描述

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

⎡ ⎣ ⎢ ⎢ ⎢ 0111101011011010 ⎤ ⎦ ⎥ ⎥ ⎥

$\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的关联矩阵