关联矩阵 Incidence matrix
在数学中，关联矩阵 incidence matrix是表示两类对象之间关系的矩阵。如果自变量是 x，因变量是 y，那么这个矩阵对于 x 的每个元素存在一行，对于 y 的每个元素存在一列。如果 x 和 y 是相关的 ，则行 x 和列 y 中的条目为1，如果它们不是相关的，则结果为0。但也有一些例外，请看下文。
图论
关联矩阵是图论 Graph theory中经常使用的一种表示方法。
无向图和有向图 Undirected and directed graphs
在图论中，无向图 Undirected Graph有两种关联矩阵：无向关联矩阵和有向关联矩阵。
无向图的无向关联矩阵 unoriented incidence matrix（也称为简单关联矩阵 incidence matrix）B，其中 n 和 m 分别是顶点和边的数目，如果顶点 vi 和边 ej是关联的，则结果为1，否则为0。
如图右所示的无向图，它的关联矩阵是一个4行（分别对应4个顶点，1-4）4列（各自对应4条边，e1-e4）组成的矩阵：
|
= |
[math]\displaystyle{ \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix}. }[/math] |
观察关联矩阵，我们就会发现，因为每条边都有一个顶点连接到每个端点，所以每一列的和总是等于2。
有向图的关联矩阵是一个矩阵B，其中 n 和 m 分别是顶点和边的数目，这样当边 ej 离开顶点 vi，时为1，当它进入顶点 vi ，时为0(许多作者使用相反的符号约定)。The incidence matrix of a directed graph is a matrix B where n and m are the number of vertices and edges respectively, such that if the edge ej leaves vertex vi, 1 if it enters vertex vi and 0 otherwise (many authors use the opposite sign convention).
无向图的有向关联矩阵在有向图的意义上是关于图的任任意方向的关联矩阵。也就是说，在边e的列中，e对应的一个顶点的行中有一个1，而另一个顶点的行中有一个−1，所有其他行都有0。定向关联矩阵是唯一的，因为对于任何列取反，列中的条目求逆向对应于反转边的方向。
图 G 的无向关联矩阵与其线图 Line Graph L(G)的邻接矩阵有以下定理关系:
- [math]\displaystyle{ A(L(G)) = B(G)^\textsf{T}B(G) - 2I_m. }[/math]
其中 A(L(G)) 是 G 的线图的邻接矩阵 Adjacency Matrix，B(G)是关联矩阵，Im 是维数为m的单位矩阵 Identity Matrix。
离散的拉普拉斯矩阵 Kirchhoff matrix（或基尔霍夫矩阵 Kirchhoff Matrix）是由定向的关联矩阵B(G)通过公式得到的
- [math]\displaystyle{ B(G) B(G)^\textsf{T}. }[/math]
图的圈空间 Cycle Space等价于其有向关联矩阵的零空间，可以看作是整数或实数或复数上的矩阵。二元循环空间是有向或无向关联矩阵的零空间，也可以看作是二元域上的矩阵。
有符号双向图 Signed and bidirected graphs
有符号图 Signed Graph的关联矩阵是有向关联矩阵的推广。它是任意双向图的关联矩阵，并为给定的有符号图定向。正边的列在对应一个端点的行有1，在对应于另一个端点的行中有 -1，就像普通无符号图 Unsigned Graph中的边一样。负边的列在两行中都有1或 -1。线图和 Kirchhoff 矩阵性质都能推广到符号图中。
多重图 Multigraphs
多重关联图 Multigraphs的定义：多重关联图与循环相对应的定向关联矩阵的列均为零，除了图有符号且循环为负的情况外，该列除其入射顶点行中的±2外均为零。
超图 Hypergraphs
因为一般图的边只能有两个顶点（每端一个），所以图的关联矩阵列只能有两个非零项。相比之下，超图却可以有多个顶点指定给一条边。因此，一般的非负整数矩阵才能用来描述超图。
关联结构 Incidence structures
关联结构 C 的关联矩阵是一个矩阵B （或其转置） ，其中 p 和 q 分别是点和线的数目，如果点 pi和线Lj 是关联的，就为1，否则为0。在这种情况下，关联矩阵也是Levi图 Levi Graph 的双邻接矩阵的结构。每个Levi图都有一个超图，反之亦然，因此关联结构的关联矩阵就可以描述一个超图。
有限几何 Finite geometries
举一个有限几何的重要例子。例如，在有限平面中,X 是点的集合,Y 是线的集合。在高维有限几何中，X 仍可以是点的集合，Y 可以是低于整个空间维数的一维子空间（超平面）的集合；或者，更一般地，X 可以是一维子空间 d 的所有子空间的集合，Y 可以是另一维子空间 e 的所有子空间的集合，关联度定义也包含在内。
多面体 Polytopes
以类似的方式，在多面体中尺寸相差一个的细胞之间的关系可以由关联矩阵表示。[1]
区组设计/块设计 Block designs
另一个例子是区块设计。这里 X 是一个有限的“点”集合，而 Y 是 X 的一类子集，称为“块” ，它受设计类型规则的制约。关联矩阵是块设计理论中的一个重要工具。例如，它可以用来证明Fisher不等式 Fisher's inequality，一个平衡不完全2- 设计（BIBDs）的基本定理，块的数目至少是点的数目。[2]将块看作一个集合系统，关联矩阵的常数是不同代表系统的个数（SDRs）。
参考文献
- ↑ Coxeter, H.S.M. (1973) [1963], Regular Polytopes (3rd ed.), Dover, pp. 166-167, ISBN 0-486-61480-8
- ↑ 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, vol. 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)
编者推荐
书籍领读：图论
本课程中，将讲解巴拉巴西网络科学书籍第一章图论。
漫谈图论的起源、发展与应用
本课程中，介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。
本中文词条由信白翻译，CecileLi审校，薄荷，欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。