补充资料：超图

超图
hypergraph

超图【鲡哟p户;r“ue拼pa中」 图的概念的一种推广.一个超图由一个集合V，它的元素称为顶点，和V的子集族犷定义，子集称为举(曰罗)或移枣(h”簿放辱).一个超图记为(V，约·超图的概念是熟知的复形(田几甲】ex)、区组设计(场因k翻咖)与网络(理加幻水)等概念的变体.超图的两顶点称为担邻的(edj~)，如果有一条边包含这两顶点.超图的一顶点v与一边E称为关联的(企‘允七nt)，如果u 6E.具有n顶点和m边的超图H可以用一个关联矩阵(泊d击泊沈几必trix)定义，即摊x爪矩阵!}风，}}，其中列对应于超图的边，而行对应于顶点，且 fl，若veE， a‘，一飞。，若v‘，乓，‘一‘，”’，”，j一‘，一m·可以给每个(O，l)矩阵M指定一个超图，使M就是该超图的关联矩阵.超图H’称为超图H的对偶(du-al)，如果H‘的关联矩阵是H的关联矩阵的转置.超图H的与一给定顶点关联的边的个数称为该顶点的摩(d奥护况ofthe~).一条边的摩(d哪，笼ofan伐堪e)是与该边关联的顶点个数.一个超图(V’，“)称为超图(V，‘)的一个子薄甲(subh班祀电珍ph)，如果V‘互V，g’生g，并且V‘的一顶点v与g‘的一边E在超图(V‘，彩‘)中关联，当且仅当它们在超图(V，扩)中关联. 一个超图可以在平面上表示，超图的顶点表为平面上的点，超图的边表为包含与该边关联的所有点的连通域.例如，顶点集是V={v，，…，魄}，边族是 ‘二{E，二{v，}，EZ二{v、，v3}，E3={vl，”:，v小 E4=ES={vZ，v4}，E。={。3，v4，垅)，E，=必}的超图可以在平面上表示如下图: 多 E，。。。O￡， 超图H亦可以用一二部图(见二部圈(g肚ph，肠partj忱))K(H)表示，其中一部Ul的顶点表示超图的点，而另一部矶的顶点表示H的边.这时以的顶点u’与矶的顶点u’’连接成图K(H)的一边，如果H中对应于“‘的顶点与对应于““的边关联.一个超图是图，如果它的每条边的度都是2.超图概念的一重要的特殊情形就是拟阵(几以。。id).图论的许多概念，如连通度、可平面性、色数、和外与内稳定数，都可以转移到超图，图论的许多结论也可转移于超图.

说明：补充资料仅用于学习参考，请勿用于其它任何用途。