例:求下图的极大独立集 ○5
例：求下图的极大独立集 4 5 2 3 6 1 8 7 G G 1 2 3 4 5 6 8 7
解:图G的补图G中全部极大完全图的顶点 集合依次为{5},{34},{2,38}、{12,3},{3.6,7,8 因此,这些集合也恰是G的全部极大独立集
支配集 设G=<V,E>是无向简单图,ScV,S≠C 若对于x∈VS,x与S里至少一个顶点相 邻,则称S是图G的支配集 >S是图G的支配集,若S的任何真子集都不 是支配集,则称S为图G的极小支配集。 >S是图G的支配集,若不存在任何其他支 配集S’,使得|S?|<S,则称S是图G的最 下支配集s|为图G的支配数记作y(G)
支配集 ➢设G=<V,E>是无向简单图，SV，S， 若对于xV-S，x与S里至少一个顶点相 邻,则称S是图G的支配集。 ➢S是图G的支配集，若S的任何真子集都不 是支配集，则称S为图G的极小支配集。 ➢ S是图G的支配集，若不存在任何其他支 配集S’,使得S’ <S,则称S是图G的最 下支配集, S为图G的支配数,记作(G)
例:在下图中,S。={v},S={n,v,},S2=v1,3,v3,v7} 都是G的支配集,且都是极小支配集,S是最小支配集,因此y(G)=1
又例:在下图示中,S={369,10}和S2={2,11是图G的两个支配集 用黑实点表示,且都是极小支配集,而S2是最小支配集,所以y(G)=3 9 10 3456