图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
支配集、覆盖集、独立集、匹配与着色 支配集、点覆盖集与点独立集 边覆盖集与匹配 二部图中的匹配 点着色 地图着色与平面图的点着色 边着色
2 支配集、覆盖集、独立集、匹配与着色 • 支配集、点覆盖集与点独立集 • 边覆盖集与匹配 • 二部图中的匹配 • 点着色 • 地图着色与平面图的点着色 • 边着色
支配集的定义 定义1 设图G=<V,E>,V≌M,若对于Wv∈vV,丑∈V,使得(v veE,则称y支配v,并称y"为G的一个支配集; 若支配集V的任何真子集都不是支配集,则称W是极小支配集; 顶点数最少的支配集称为最小支配集;最小支配集中的顶点数 称为支配数,记作?G或简记为yo
3 支配集的定义 定义1. 设图G = <V, E>, V*⊆V, 若对于∀vi∈V - V*, ∃vj∈V*, 使得 (vi, vj)∈E, 则称vj支配vi, 并称V*为G的一个支配集; 若支配集V*的任何真子集都不是支配集, 则称V*是极小支配集; 顶点数最少的支配集称为最小支配集;最小支配集中的顶点数 称为支配数, 记作γ0(G)或简记为γ0
点独立集 定义2 设图G=<V,E>,VcV,若V中任何两个顶点均不相邻,则称 V为G的点独立集,或称独立集; 若在V中加入任何顶点都不再是独立集,则称V为极大点独立 集 顶点数最多的点独立集称为最大点独立集;最大点独立集的顶 点数称为点独立数,记作P(G),简记为β0
4 点独立集 定义2. 设图G = <V, E>, V* ⊆ V, 若V*中任何两个顶点均不相邻, 则称 V*为G的点独立集, 或称独立集; 若在V*中加入任何顶点都不再是独立集, 则称V*为极大点独立 集; 顶点数最多的点独立集称为最大点独立集; 最大点独立集的顶 点数称为点独立数, 记作β0(G), 简记为β0
点独立集与支配集的关系 定理1.设G=<V,E>中无孤立点,则G的极大点独立集都是G的极 小支配集。 证明 设V是G中的任意一个极大独立集.VVeV-V,一定丑v∈ V,使得(v,v)∈E.否则彐u∈VV不与V中任何顶点相邻,则 U{u}就是一个更大的独立集,这与V是极大独立集相矛盾.所 以,V是G的支配集。 由“V是点独立集”可知,V1*cV,V-V*中的顶点都不受 V1*中的顶点支配,即V*不是支配集.所以,V是极小支配集 5
5 点独立集与支配集的关系 定理1. 设G = <V, E>中无孤立点, 则G的极大点独立集都是G的极 小支配集。 设 V*是G中的任意一个极大独立集. ∀v∈V - V*, 一定 ∃v’ ∈ V*, 使得 (v, v’) ∈ E. 否则∃u∈V-V*不与V*中任何顶点相邻, 则 V*∪{ u }就是一个更大的独立集, 这与V*是极大独立集相矛盾. 所 以, V*是G的支配集。 由“V*是点独立集”可知, ∀V1* ⊂ V*, V* - V1*中的顶点都不受 V1*中的顶点支配, 即V1*不是支配集. 所以, V*是极小支配集。 证明: