超图(Hypergraph)概念理解
这几天在看关于复杂网络的paper,其中有一个概念叫做HyperGraph,中文名译为“超图”。这个概念paper上面讲的不是很清楚,于是我去查了一下维基:
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. Formally, a hypergraph is a pair where is a set of elements called nodes or vertices, and is a set of non-empty subsets of called hyperedges or edges.
结合图,可以理解到超图就是每一个边可以包含两个以上的点所构成的图,继续看下去:
While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting k nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on.
虽然明白了一些,但感觉不是很直观。每个边所包含的顶点个数都是相同且为k个的,就可以被称为k阶超图。2阶超图就是我们平时所见到的图,因为我们平时的图由线条(edge,边)和点(vertice,顶点)构成,每条线都只包含两个点,所以这是符合2阶超图的定义的。那么我这个理解是否是正确的呢?我去找一些可以表示三阶超图的概念图,最终在南加州大学Joshua Cooper的讲稿上找到一张图:
这张图一条直线或者曲线代表的是一个超边(Hyperedge),这张图就比较清晰的证实了我的理解,确实是每一个边都只包含3个顶点。理解到这一点,把握了超图的基本概念后,就可以继续看paper了。
参考连接:
https://en.wikipedia.org/wiki/Hypergraph
http://slideplayer.com/slide/4792016/