点覆盖集 定义3. 设G=<V,E>,VsV,若对于ve∈E,3v∈V,使得v与e相关 联,则称v覆盖e,并称V为G的点覆盖集或简称点覆盖; 若点覆盖V的任何真子集都不是点覆盖,则称V是极小点覆盖; 顶点个数最少的点覆盖称为最小的点覆盖;最小点覆盖的顶点 数称为点覆盖数,记作α0(G,简记为ao
6 点覆盖集 定义3. 设G = <V, E>, V*⊆V, 若对于∀e ∈ E, ∃v ∈ V*, 使得 v与e相关 联, 则称v覆盖e, 并称V*为G的点覆盖集或简称点覆盖; 若点覆盖V*的任何真子集都不是点覆盖, 则称V*是极小点覆盖; 顶点个数最少的点覆盖称为最小的点覆盖; 最小点覆盖的顶点 数称为点覆盖数, 记作α0(G), 简记为α0
点覆盖集与点独立集的关系 定理2.设G=<V,E>中无孤立点,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, E>中无孤立点, 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=<VE>,E*E,若v∈V,彐e∈E*,使得v与e相关联,则 称e覆盖v,并称E*为边覆盖集,或简称边覆盖 若边覆盖E*的任何真子集都不是边覆盖,则称巳是极小边覆盖 边数最少的边覆盖集称为最小的边覆盖;最小的边覆盖所含的 边数称为边覆盖数,记作α1(G或简记为α1
8 边覆盖集 定义4. 设图G = <V, E>, E*⊆E, 若∀v∈V, ∃e∈E*, 使得 v与e相关联, 则 称e覆盖v, 并称E*为边覆盖集, 或简称边覆盖; 若边覆盖E*的任何真子集都不是边覆盖, 则称E*是极小边覆盖; 边数最少的边覆盖集称为最小的边覆盖; 最小的边覆盖所含的 边数称为边覆盖数, 记作α1(G)或简记为α1
边独立集(匹配) 定义5. 设G=<V,E>,若E*(E*E)中任何两条边均不相邻,则称E为G 中边独立集,也称E*为G中的匹配; 若在E*中加入任意一条边所得集合都不是匹配,则称E为极大 匹配; 边数最多的匹配称为最大匹配;最大匹配的边数称为边独立数 或匹配数,记作β1(G,简记为
9 边独立集(匹配) 定义5. 设G = <V, E>, 若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中交替取边的圈为交错圈