所以 P=U1VU2AU3AU4 VIU1AU2A 6 5 ∧ UAAUVIL1∧D1∧ U2AU3AU4 AU6VU2AU3AU4AUSV U,AUAUAUA 故得所有极大独立集: {2,3,U3,{2,U3,6},{,U3},{v2,b6},{4}。 因此,由所有的极大独立集我们可以得到最大独立集分别是 {U2,U3,U3},{b2,U3,U6}。独立数是a(G)=3
点覆盖 设G=<VE>,∈V 然是点覆盖点覆盖集)—VeE,Bv∈Ⅳ,使e 与联 2)是极小点覆盖—的任何真子集都不是点覆 盖集; (3)最小点覆盖顶点数最少的点覆盖集 (4)点覆盖数—β(最小点覆盖的元素个数。 图中,点覆盖数依次为3,4,7
点覆盖 设G=<V,E>, V*V, (1) V*是点覆盖(点覆盖集）——eE，vV*，使e 与v关联； (2) V*是极小点覆盖——V*的任何真子集都不是点覆 盖集； (3) 最小点覆盖——顶点数最少的点覆盖集； (4) 点覆盖数——(G)——最小点覆盖的元素个数。 图中，点覆盖数依次为3，4，7
定理:设G=<V,E>是无向简单图,ScV,S≠,S 是G的独立集分→VS是G的点覆盖。 证S是G的独立集分G中每条边的两端点都不同 时属于S◇G中每条边至少有一端点在VS中 V-S是G的点覆盖。 推论:S是G的极大独立集分VS是G的极小点覆盖
定理：设G=<V,E>是无向简单图,SV,S，S 是G的独立集V-S是G的点覆盖。 推论：S是G的极大独立集V-S是G的极小点覆盖。 证:S是G的独立集G中每条边的两端点都不同 时属于S G中每条边至少有一端点在V-S中 V-S是G的点覆盖
推论:a(G)+B(C)=|v(G) 证明:设S是G的最大独立集,S2是G的最小点覆 盖由前面的定理知V(G)-S1是点覆盖,V(G)-S2是 独立集。因而 (G)|-a(G)=|v(G)-S1|≥B(G) v(G)|-B(G)=|v(G)-S2|≤a(G) 所以a(G+B(G)=|V(G)l
推论：(G)+(G)=V(G)。 证明: 设S1是G的最大独立集, S2是G的最小点覆 盖,由前面的定理知V(G)-S1是点覆盖,V(G)-S2是 独立集。因而 V(G)- (G)= V(G) -S1 (G) V(G)- (G)= V(G) –S2 (G) 所以 (G)+(G)=V(G)
边覆盖 设G三<V,E>是无向简单图,LcV,L≠O。若G 中每个顶点都与中某条边关联,则称L为G的边 覆盖。 如果G中的任何异于L的边覆盖U均有||≥ L|,则称s为G的最小边覆盖。 最小边覆盖L的基数L称为G的边覆盖数, 记作(G)
设G=<V,E>是无向简单图，LV，L。若G 中每个顶点都与L中某条边关联，则称L为G的边 覆盖。 如果G中的任何异于L的边覆盖L’,均有L’ L ,则称S为G的最小边覆盖。 最小边覆盖L的基数 L 称为G的边覆盖数, 记作Θ(G)。 边覆盖