复旦大学：《离散数学》课程教学讲义（图论）超图

超图

超图

线图的缺陷 ■线图中限定每条边的关联结点为两个, 限制了线图的表达能力。现实世界中, 广泛地存在着各种各样的多元联系,难 以用线图直观地表达

线图的缺陷  线图中限定每条边的关联结点为两个， 限制了线图的表达能力。现实世界中， 广泛地存在着各种各样的多元联系，难 以用线图直观地表达

超图 个超图H是一个有序二元组H=<V,E>, 其中V是一个有限集,V中的元素称为H 的结点,E是一个超边的集合。E中每 条超边都是V的一个非空子集,并使得∨ 中每个结点至少属于E中的一条超边

超图  一个超图H是一个有序二元组H=<V, E>， 其中V是一个有限集，V中的元素称为H 的结点，E是一个超边的集合。E中每一 条超边都是V的一个非空子集，并使得V 中每个结点至少属于E中的一条超边

超图表示 ■结点用标号表示 ■超边用环绕它的全部关联结点的封闭曲 线表示 例

超图表示  结点用标号表示  超边用环绕它的全部关联结点的封闭曲 线表示  例

通路 ■设H=<V,E>是一个超图,A、B是∨中的 结点,则H中从A到B的一条通路是一个 边的序列E1,E2,…,E(k≥1),该序列满 足下列条件: (1)A∈E1,B∈Ek; (2)对于所有1≤k,E∩E1。 ■边序列E1,E2,…,为从E到E的通路

通路  设H=<V, E>是一个超图，A、B是V中的 结点，则H中从A到B的一条通路是一个 边的序列E1, E2, …, Ek (k1)，该序列满 足下列条件： （1）AE1, BEk； （2）对于所有1ik，EiEi+1。  边序列E1, E2, …, Ek为从E1到Ek的通路