# 关联矩阵 Incidence matrix

## 无向图和有向图 Undirected and directed graphs

e1 e2 e3 e4
1 1 1 1 0
2 1 0 0 0
3 0 1 0 1
4 0 0 1 1
=

$\displaystyle{ \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix}. }$

G 的无向关联矩阵与其线图 Line Graph L(G)的邻接矩阵有以下定理关系:

$\displaystyle{ A(L(G)) = B(G)^\textsf{T}B(G) - 2I_m. }$

$\displaystyle{ B(G) B(G)^\textsf{T}. }$

## 参考文献

1. Coxeter, H.S.M. (1973) [1963], Regular Polytopes (3rd ed.), Dover, pp. 166-167, ISBN 0-486-61480-8
2. Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, The Mathematical Association of America, p. 99

## 其他阅读

• Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, 173 (3rd ed.), Springer-Verlag, ISBN 3-540-26183-4
• Jonathan L Gross, Jay Yellen, Graph Theory and its applications, second edition, 2006 (p 97, Incidence Matrices for undirected graphs; p 98, incidence matrices for digraphs)