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

全栈程序员-站长 • 2025年7月2日下午7:22 • 未分类 • 阅读 6

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

类似地，有向图 $D$ 的关联矩阵 $\mathbf M(D)=(m_{ij})_{n\times\varepsilon}$ 的元素 $m_{i\times j}$ 定义为：

m i j = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 1, - 1, 0, v i 是 有 向 边 a j 的 始 点 v i 是 有 向 边 a j 的 终 点 v i 是 有 向 边 a j 的 不 关 联 点

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

示例，求图中有向图的邻接矩阵和关联矩阵。
这里写图片描述

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

⎡ ⎣ ⎢ ⎢ ⎢ 0001101010000010 ⎤ ⎦ ⎥ ⎥ ⎥

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

关联矩阵:

⎡ ⎣ ⎢ ⎢ ⎢ 1 - 1 00 0 - 1 10 001 - 1 - 1 001 10 - 1 0 ⎤ ⎦ ⎥ ⎥ ⎥

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

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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/222914.html原文链接：https://javaforall.net

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

关于作者

全栈程序员-站长

发表回复

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

关于作者

全栈程序员-站长

相关推荐

Anaconda环境下Tensorflow的安装与卸载

Hadoop生态圈hive应用

无法删除文件.dll访问被拒绝

leetcode-38外观数列

Postman报错：Error: getaddrinfo ENOTFOUND

bind函数的作用

发表回复