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

【邻接矩阵】

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

若干性质

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

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

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

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

⎡⎣⎢⎢⎢0111101011011010⎤⎦⎥⎥⎥ [ 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 ]

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

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

【关联矩阵】

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

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

M

(

D

)

=

(

m

i

j

)

n

×

ε

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

mij=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪1,−1,0,vi是有向边aj的始点vi是有向边aj的终点vi是有向边aj的不关联点 m i j = { 1 , v i 是 有 向 边 a j 的 始 点 − 1 , v i 是 有 向 边 a j 的 终 点 0 , 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⎤⎦⎥⎥⎥ [ 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 ]

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

关联矩阵:

⎡⎣⎢⎢⎢1−1000−110001−1−100110−10⎤⎦⎥⎥⎥ [ 1 0 0 − 1 1 − 1 − 1 0 0 0 0 1 1 0 − 1 0 0 − 1 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.cn/222914.html原文链接：https://javaforall.cn