对于超图的一些理解

2020-05-25 本文已影响0人云之彼端

我们知道普通的graph中，一条边只能连接两个点，而边实际上是用来表示两点间有邻接关系的一种符号。而超图（hyper graph）中的边可能会关联（或者说包含）两个以上的点，即在同一边中的点均邻接。

如下图（图片来自网络，下图中e指边，v指点）：

hypergraph is a generalization of a graph in which an edge can join any number of vertices

在数学上，超图泛指边可以关联任意数量点的图。确切地说，超图是一种点-边对（pair），表示为H=(X,E),其中X是点的集合，E是边（下称超边）的集合。超图中的边不像普通graph的边一样有实体，而只是它所包含的点的集合。所以E实际上是X的非空子集。另外，一个点也可能在多条超边中。

超图是一种高维的对于数据的图形展示，弥补了普通graph方式信息丢失的缺陷，专用于描述具有成对的组合关系（点与超边）的体系。

如果点v在超边e中，则称超边e与点v关联（hyper edge e is incident with node v）。

如果 v∈ e ,w∈ e，则称v与w邻接（ neighborhood relationships）。

以下定义暂不考虑权重：

上图中，第一行是对关联矩阵 H ∈R |V|×|E|的定义,类比普通graph中的关联矩阵，还是比较容易理解的。

类似于普通graph中对于点的度的定义，我们可以得到超图中超边与点的度的定义：

第二行是关于超边e的度 δ(e)，|e|即e中的点个数。如果δ(e)=r(r>0)对于所有的超边都成立，则称该超图为r-uniform超图（额，不会翻译）。这样一来，普通的graph实际上就是2-uniform的超图。

第三行是关于点v的度d(v)，其中E(v)指与v关联的边的个数。

于是我们得到了对角边度矩阵（the diagonal hyperedge degree matrix），De ∈R|E|×|E|；

以及对角点度矩阵（the diagonal vertex degree matrix ），Dv ∈R|V|×|V| 。