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

超图

超图

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

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

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

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

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

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

通路 ■设H=是一个超图,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=是一个超图，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的通路

连通 ■在超图H中,如果两个结点(或边)之间 存在一条通路,则称它们是连通的 ■如果一个边的集合中每一对边都是连通 的,则称该边集是连通的

连通  在超图H中，如果两个结点（或边）之间 存在一条通路，则称它们是连通的。  如果一个边的集合中每一对边都是连通 的，则称该边集是连通的

连通支 个超图H中的任一极大连通边集以及它 们的关联结点一起称作H的一个连通支

连通支  一个超图H中的任一极大连通边集以及它 们的关联结点一起称作H的一个连通支

子图 ■设H=,H=都是超图,如 果V,EcE,则称H是H的一个子图

子图  设H=，H’=都是超图，如 果V’V，E’E，则称H’是H的一个子图

化简超图 ■设H=是一个超图,如果边集E中 不存在任何一条边是另一条边的真子集, 则称H是一个化简超图。 ■对于任意一个超图H,通过从图中删去那 些为别的边所真包含的超边而得到一个 化简超图,称这个化简超图为H的化简图, 记为RED(H)

化简超图  设H=是一个超图，如果边集E中 不存在任何一条边是另一条边的真子集， 则称H是一个化简超图。  对于任意一个超图H，通过从图中删去那 些为别的边所真包含的超边而得到一个 化简超图，称这个化简超图为H的化简图， 记为RED(H)

投影图 ■设H=是一个超图,结点集ⅤV, 则我们称超图RED(V,巨>)为H到V的 投影,记作H,其中E={enE:e∈E} {},E中的每一条边通常也称作H的 条子边

投影图  设H=是一个超图，结点集V’V， 则我们称超图RED()为H到V’的 投影, 记作HV’，其中EV’={eEV’: eE}- {}，EV中的每一条边通常也称作H的一 条子边