例:通过矩阵平移运算求下图G的极大独立集。 G
v1 v2 v4 v3 v6 v5 G 例：通过矩阵平移运算,求下图G的极大独立集
解:G的邻接矩阵A D1 U L1「011100 100100 100100 l1011 000101 把A的与v作平移变換A4;把A的1与v3作平移变換的A2
D6 D2 D D4 Ds D1 「000110 00101 U2000101 000110 300010 3000110 3100100 011100 2L011100 g[100100 4和A2都是标准形式,从而可知{23,3}与{2,U3,U3}都是 极大独立集,且它们也是G的最大独立集。因此,根据前面的 定理及其推论,可得{,4,U}与{3D4,L}都是G的最小点覆盖
定理:设G={E)是具有n个节点的无向简单图,A是G的邻接矩阵, {t32,…,}是独立集的充要条件是A中的第,…,相加所得到的向量中只 有第i个分量,第i个分量,…,第i个分量为0 证明:充分性:若{,t2,…,U}为图G的一个极大独立点集,则它们之间均 无边相连,故第行的第i,…个元素为0,同理,第i2,…行的第i,i,… 个元素亦均为0。所以可知第,2…行相加后的向量a的第i2,…,个元素为 0。又因为它们是一个极大独立点集,即不存在另一个点与,2,…,均不相邻, 故a的其它分量的值≥1 必要性:若a中仅,2,…,个分量为0,则易知2…,互不相邻且除这些 点外其它点至少与它们中某一点相邻,所以,n2…,为一个极大独立集
团 (图G的团设G=<V,E>是无向简单图,TV, T≠⑦。若T中任意两个顶点都相邻,则称T是 图G的团。若T是图G的团,但任意增加一个 新顶页点后,它就不是团,则称T是图G的极 大团
(图G的团)设G=<V,E>是无向简单图，TV， T。若T中任意两个顶点都相邻，则称T是 图G的团。若T是图G的团，但任意增加一个 新顶点后，它就不是团，则称T是图G的极 大团。 团