超图

File:Hypergraph-wikipedia.svg

一个超图的例子，图示中包含了 <math>X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math> 和 <math>E = \{e_1,e_2,e_3,e_4\} = </math> <math>\{\{v_1, v_2, v_3\},</math> <math>\{v_2,v_3\},</math> <math>\{v_3,v_5,v_6\},</math> <math>\{v_4\}\}</math>.

在数学中，超图（Hypergraph）是一种广义上的图，它的一条边可以连接任意数量的顶点。形式上，超图<math>H</math>是一个集合组<math>H = (X,E)</math>，其中<math>X</math>是一个有限集合，该集合的元素被称为节点或顶点，<math>E</math>是<math>X</math>的非空子集的集合，被称为超边或连接。因此，<math>E</math>是<math>\mathcal{P}(X) \setminus\{\emptyset\}</math>的一个子集，其中<math>\mathcal{P}(X)</math>是<math>X</math>的幂集。

尽管图的边各有一对节点，而超边是节点的任意集合，因而能包含任意数量的节点。然而，通常的研究更倾向于每个超边连接的节点数相同的超图：k-均匀超图（每个超边都连接了k个节点）。因此，2-均匀超图就是图，3-均匀超图就是三元组的集合，依此类推。

参考

• Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 Springer-Verlag
• 本条目含有来自PlanetMath《Hypergraph》的内容，版权遵守知识共享协议：署名-相同方式共享协议。
• Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.