图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
支配集、覆盖集、独立集、匹配与着色 支配集、点覆盖集与点独立集 边覆盖集与匹配 二部图中的匹配 点着色 地图着色与平面图的点着色 边着色
2 支配集、覆盖集、独立集、匹配与着色 • 支配集、点覆盖集与点独立集 • 边覆盖集与匹配 • 二部图中的匹配 • 点着色 • 地图着色与平面图的点着色 • 边着色
支配集的定义 定义1 设图G=,V≌M,若对于Wv∈vV,丑∈V,使得(v veE,则称y支配v,并称y"为G的一个支配集; 若支配集V的任何真子集都不是支配集,则称W是极小支配集; 顶点数最少的支配集称为最小支配集;最小支配集中的顶点数 称为支配数,记作?G或简记为yo
3 支配集的定义 定义1. 设图G = , V*⊆V, 若对于∀vi∈V - V*, ∃vj∈V*, 使得 (vi, vj)∈E, 则称vj支配vi, 并称V*为G的一个支配集; 若支配集V*的任何真子集都不是支配集, 则称V*是极小支配集; 顶点数最少的支配集称为最小支配集;最小支配集中的顶点数 称为支配数, 记作γ0(G)或简记为γ0
点独立集 定义2 设图G=,VcV,若V中任何两个顶点均不相邻,则称 V为G的点独立集,或称独立集; 若在V中加入任何顶点都不再是独立集,则称V为极大点独立 集 顶点数最多的点独立集称为最大点独立集;最大点独立集的顶 点数称为点独立数,记作P(G),简记为β0
4 点独立集 定义2. 设图G = , V* ⊆ V, 若V*中任何两个顶点均不相邻, 则称 V*为G的点独立集, 或称独立集; 若在V*中加入任何顶点都不再是独立集, 则称V*为极大点独立 集; 顶点数最多的点独立集称为最大点独立集; 最大点独立集的顶 点数称为点独立数, 记作β0(G), 简记为β0
点独立集与支配集的关系 定理1.设G=中无孤立点,则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 = 中无孤立点, 则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*是极小支配集。 证明:
点覆盖集 定义3. 设G=,VsV,若对于ve∈E,3v∈V,使得v与e相关 联,则称v覆盖e,并称V为G的点覆盖集或简称点覆盖; 若点覆盖V的任何真子集都不是点覆盖,则称V是极小点覆盖; 顶点个数最少的点覆盖称为最小的点覆盖;最小点覆盖的顶点 数称为点覆盖数,记作α0(G,简记为ao
6 点覆盖集 定义3. 设G = , V*⊆V, 若对于∀e ∈ E, ∃v ∈ V*, 使得 v与e相关 联, 则称v覆盖e, 并称V*为G的点覆盖集或简称点覆盖; 若点覆盖V*的任何真子集都不是点覆盖, 则称V*是极小点覆盖; 顶点个数最少的点覆盖称为最小的点覆盖; 最小点覆盖的顶点 数称为点覆盖数, 记作α0(G), 简记为α0
点覆盖集与点独立集的关系 定理2.设G=中无孤立点,V(VcV为G的点覆盖,当且仅 当VV*为G的点独立集 证明 (必要性) 假设存在 Vi, ViEV-Vi,且vy∈E.由于顶点v和v都不在V 中,这显然与“V是点覆盖”相矛盾.所以,V-V为点独立集 (充分性 由于V-V是点独立集,因此,任意一条边的两个端点至少有 个在V中.根据定义可知,V是G的点覆盖 推论设G是n阶无孤立点的图,则V是G的极小最小)点覆盖,当且仅当 VV是G的极大(最大)点独立集,从而有α+βB0=n
7 点覆盖集与点独立集的关系 定理2. 设G = 中无孤立点, V*(V*⊂V)为G的点覆盖, 当且仅 当V-V*为G的点独立集。 证明: (必要性) 假设存在vi, vj∈V - V*, 且(vi, vj) ∈ E. 由于顶点vi和vj都不在V* 中, 这显然与“V*是点覆盖”相矛盾. 所以, V - V*为点独立集。 (充分性) 由于V - V*是点独立集, 因此, 任意一条边的两个端点至少有一 个在V*中. 根据定义可知, V*是G的点覆盖。 推论 设G是n阶无孤立点的图, 则V*是G的极小(最小)点覆盖, 当且仅当 V-V*是G的极大(最大)点独立集, 从而有α0 + β0 = n
边覆盖集 定义4. 设图G=,E*E,若v∈V,彐e∈E*,使得v与e相关联,则 称e覆盖v,并称E*为边覆盖集,或简称边覆盖 若边覆盖E*的任何真子集都不是边覆盖,则称巳是极小边覆盖 边数最少的边覆盖集称为最小的边覆盖;最小的边覆盖所含的 边数称为边覆盖数,记作α1(G或简记为α1
8 边覆盖集 定义4. 设图G = , E*⊆E, 若∀v∈V, ∃e∈E*, 使得 v与e相关联, 则 称e覆盖v, 并称E*为边覆盖集, 或简称边覆盖; 若边覆盖E*的任何真子集都不是边覆盖, 则称E*是极小边覆盖; 边数最少的边覆盖集称为最小的边覆盖; 最小的边覆盖所含的 边数称为边覆盖数, 记作α1(G)或简记为α1
边独立集(匹配) 定义5. 设G=,若E*(E*E)中任何两条边均不相邻,则称E为G 中边独立集,也称E*为G中的匹配; 若在E*中加入任意一条边所得集合都不是匹配,则称E为极大 匹配; 边数最多的匹配称为最大匹配;最大匹配的边数称为边独立数 或匹配数,记作β1(G,简记为
9 边独立集(匹配) 定义5. 设G = , 若E*(E*⊆E)中任何两条边均不相邻, 则称E*为G 中边独立集, 也称E*为G中的匹配; 若在E*中加入任意一条边所得集合都不是匹配, 则称E*为极大 匹配; 边数最多的匹配称为最大匹配;最大匹配的边数称为边独立数 或匹配数, 记作 β1(G), 简记为β1
与匹配相关的概念 定义6.假设M为图G中一个匹配, 若(vvy)eM,则称v与v被M所匹配即v)为匹配边;否 则为非匹配边 对Wv∈v(G),若存在边e∈M,使e与v关联,则称v为M-饱和 点;否则,称v为M非饱和点; 若G中每个顶点都是M饱和点,则称M为G中的完美匹配; 称在M和E(G)M中交替取边的路径为M的交错路径,起点 和终点都是M-非饱和点的交错路径称为可增广的交错路径 称在M和E(G-M中交替取边的圈为交错圈 10
10 与匹配相关的概念 定义6. 假设M为图G中一个匹配, ¾ 若(vi, vj)∈M, 则称vi与vj被M所匹配,即(vi, vj)为匹配边;否 则为非匹配边; ¾ 对∀v∈V(G), 若存在边e∈M, 使e与v关联, 则称v为M-饱和 点; 否则, 称v为M-非饱和点; ¾ 若G中每个顶点都是M-饱和点, 则称M为G中的完美匹配; ¾ 称在M和E(G)-M中交替取边的路径为M的交错路径, 起点 和终点都是M-非饱和点的交错路径称为可增广的交错路径; ¾ 称在M和E(G)-M中交替取边的圈为交错圈