关联矩阵

关联矩阵（incidence matrix）以顶点和边分别作为两类索引，记录一条边与哪些顶点关联。它通常是长方形矩阵，区别于以顶点对为索引的邻接矩阵。带符号的关联矩阵还能记录边的方向，使流量守恒和顶点势差成为矩阵乘法。

下文取五个顶点 $a,b,c,d,e$ 和五条边 $ab,ac,bc,cd,de$。虽然本例的矩阵恰好是方阵，定义并不要求顶点数等于边数。先把每条边任选一个方向，依次记为 $e_1:a\to b$、$e_2:a\to c$、$e_3:b\to c$、$e_4:c\to d$、$e_5:d\to e$。

一列记录一条边

设不含自环的图有 $n$ 个顶点和 $m$ 条边。按“行对应顶点、列对应边”的约定，定向关联矩阵 $B\in {ℝ}^{n\times m}$ 定义为 $$B_{v,e}=\{\begin{array}{cc}-1,& v\text{是边}e\text{的起点},\\ 1,& v\text{是边}e\text{的终点},\\ 0,& v\text{不与边}e\text{关联}.\end{array}$$ 每列恰有一个 $-1$ 和一个 $1$，列和为零。文献也常用相反符号或将整个矩阵转置，引用恒等式时应同时核对维数与约定。

按上面的顶点、边次序，主例矩阵为 $$B=\left(\begin{array}{ccccc}-1& -1& 0& 0& 0\\ 1& 0& -1& 0& 0\\ 0& 1& 1& -1& 0\\ 0& 0& 0& 1& -1\\ 0& 0& 0& 0& 1\end{array}\right).$$ 例如第四列只有 $c$ 行为 $-1$、$d$ 行为 $1$，准确记录 $c\to d$。孤立顶点对应零行；若图有重边，每条边仍各占一列，所以可能出现相同的列。

箭头固定B的符号约定。b、c、d流入等于流出，a净流出三，e净流入三。

边流量与顶点净流入

令列向量 $f\in {ℝ}^m$ 的每个分量为沿所选方向的边流量。若边方向只是参考方向，可允许负数表示实际反向；若模型是禁止逆行的有向网络，则另需 $f_e\ge 0$ 以及容量条件。由矩阵条目的定义， $$(Bf{)}_v=\sum _{e\text{进入}v}{f}_e-\sum _{e\text{离开}v}{f}_e.$$ 因此 $Bf$ 是各顶点的净流入向量，要求内部顶点守恒就是要求对应分量为零。

图中取 $f=(2,1,2,3,3{)}^{𝖳}$。逐行计算为 $$Bf=\left(\begin{array}{c}-2-1\\ 2-2\\ 1+2-3\\ 3-3\\ 3\end{array}\right)=\left(\begin{array}{c}-3\\ 0\\ 0\\ 0\\ 3\end{array}\right).$$ 源点 $a$ 净流入为负三，汇点 $e$ 为正三，其余点流量守恒。每列和为零还说明 $1^{𝖳}Bf=0$：网络内部的边只能搬运流量，不能凭空增加全网流量。

变式。 令 $z=(1,-1,1,0,0{)}^{𝖳}$。可直接算得 $Bz=0$，因为它表示沿 $a\to b\to c\to a$ 绕一圈，其中最后一段逆着 $e_2$ 的参考方向。于是 $B(f+tz)=Bf$ 对任意实数 $t$ 成立：给流量加入一个环流不改变顶点净流入。若还要求所有边流非负，本例需 $2+t\ge 0$、$1-t\ge 0$、$2+t\ge 0$，即 $-2\le t\le 1$；有容量上界时还会进一步限制 $t$。

顶点势差与秩

若 $x\in {ℝ}^n$ 给每个顶点一个数值，则边 $u\to v$ 对应的分量为 $$(B^{𝖳}x{)}_e=x_v-x_u.$$ 因此 $B^{𝖳}x=0$ 当且仅当每条边两端数值相等；沿路径逐边使用相等关系，就得到每个连通分量上的数值都相同。这里的连通性指忽略所选参考方向后的无向连通性。

秩定理。 对含 $n$ 个顶点、$c$ 个连通分量且不含自环的无向图，任意定向关联矩阵在实数域上满足 $$\mathrm{rank}(B)=n-c.$$ 证明。 刚才已证明 $\ker (B^{𝖳})$ 恰由“在每个连通分量上取一个常数”的向量组成。每个分量可以独立选择常数，所以这个核的维数为 $c$。由秩—零化度定理，$\mathrm{rank}(B^{𝖳})=n-c$；转置不改变秩，结论成立。孤立顶点独占一个分量，其自由常数已计入 $c$，无需排除。

主例连通，故秩为 $5-1=4$。又因 $B$ 有五列，$\ker B$ 的维数为一，恰由上面算出的非零环流 $z$ 张成。这说明相同的顶点净流入一般不唯一确定每条边的流量；差异可以藏在环路中。

与图拉普拉斯矩阵的关系

设 $D$ 为度数对角矩阵、$A$ 为邻接矩阵。对于无向简单图， $$B{B}^{𝖳}=D-A.$$ 证明可检查每个条目。对角条目 $(B{B}^{𝖳}{)}_{vv}=\sum _e{B}_{v,e}^2$，每条关联边贡献一，故为度数。不同顶点 $u,v$ 的条目是 $\sum _e{B}_{u,e}{B}_{v,e}$：只有同时接着它们的边会贡献，存在这条边时一端为负一、另一端为正一，贡献负一；无边则贡献零。这就得到 $D-A$。

改变某条边的参考方向，会使对应列整体乘负一；该列与其转置的乘积不变，所以 $B{B}^{𝖳}$ 不依赖参考方向。对任意 $x$，还有 $$x^{𝖳}B{B}^{𝖳}x=\Vert B^{𝖳}x{\Vert }_2^2=\sum _{uv\in E}(x_v-x_u{)}^2\ge 0.$$ 这从边上的差平方解释了图拉普拉斯矩阵的半正定性，也将其零空间再次连接到连通分量上的常数。

无符号关联矩阵的区别

若仅记录“是否关联”，可定义零一矩阵 $C$，每条非自环边的两端都写一。此时同样逐项计数得到 $C{C}^{𝖳}=D+A$，而不是 $D-A$。其秩也不普遍等于 $n-c$：三角形的零一关联矩阵 $$C=\left(\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\end{array}\right)$$ 行列式为 $-2$，实数秩为三；同一三角形的带符号关联矩阵秩为二。因而“关联矩阵的秩”必须说明符号约定和所用数域。若允许自环，带符号列通常因同一顶点同时是首尾而取零，无符号版本可能把自环记作二或一；本文不含自环的条件避免这些额外约定。