【图论笔记】图论基础（7）：图与矩阵

---

目录

• 1. 邻接矩阵
• 2. 关联矩阵
• 3. 二部邻接矩阵
• 返回【图论笔记】

---

1. 邻接矩阵

• 设$G$是一个无向图，且$V(G)=\{v_1,v_2,\dots,v_n\}$．设$A_G=(a_{ij})_{n\times n}$是一个$n$阶方阵，其中$a_{ij}$取值为连接$v_i$和$v_j$的边数．那么我们就说$A_G$是$G$的邻接矩阵．

• 设$D$是一个有向图，且$V(D)=\{v_1,v_2,\dots,v_n\}$．设$A_D=(a_{ij})_{n\times n}$是一个$n$阶方阵，其中$a_{ij}$取值为从$v_i$到$v_j$的有向边的个数．那么我们就说$A_D$是$D$的邻接矩阵．

• 无向图的邻接矩阵的每一行的行和与每一列的列和都是对应顶点的度．
• 有向图的邻接矩阵中，每一行的行和是对应顶点的出度，每一列的列和是对应顶点的入度
• 无向图的邻接矩阵是对称的，有向图的邻接矩阵是非对称的．

---

2. 关联矩阵

• 设$G$是一个无向图，且$V(G)=\{v_1,v_2,\dots,v_n\}$，$E(G)=\{e_1,e_2,\dots,e_m\}$．设$M_G=(m_{ij})_{n\times m}$是一个$n\times m$阶矩阵，其中$m_{ij}$取值为$v_i$与$e_j$的关联次数（即0，1或2）．那么我们就说$M_G$是$G$的关联矩阵．

• 设$D$是一个有向图，且$V(D)=\{v_1,v_2,\dots,v_n\}$，$A(D)=\{a_1,a_2,\dots,a_m\}$．设$M_G=(m_{ij})_{n\times m}$是一个$n\times m$阶矩阵，其中$m_{ij}$取值为$0$，$1$或$-1$：如果$v_i$与$a_j$不关联，那么$m_{ij}=0$；如果$v_i$是$a_j$．那么我们就说$M_G$是$G$的关联矩阵．

---

3. 二部邻接矩阵

设$G[X,Y]$是一个二部图，其中$X=\{x_1,x_2,\dots,x_m\}$，$Y=\{y_1,y_2,\dots,y_n\}$．设$B_G=(b_{ij})_{m\times n}$是一个$m\times n$的矩阵，其中$b_{ij}$是连接$x_i$与$y_j$之间的边数．我们称矩阵$B_G$是$G$的二部邻接矩阵．

二部图的二部邻接矩阵其实是二部图的邻接矩阵的一个非零分块．

---

• 返回【图论笔记】