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

全栈程序员-站长 • 2022年10月29日下午4:46 • 未分类 • 阅读 0

【邻接矩阵】

定义：
设无向图 $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

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

相关推荐

J2ME中的Hashtable和Vector

阿里云MQTT服务器搭建与测试(全图文，非常详细)「建议收藏」

Java集合篇：Vector

负载均衡的算法有哪些_acwing是什么

phpstorm ctrl+shift+F键不管用，不弹出搜索弹框

Linux系统(Centos)安装tomcat和部署Web项目

发表回复