独立集的应用举例 例:(收款食的说置题某大型商场为加强经营 管理,对商品的零售收入实行统 网棱破么遥度驶橙 问题分析:建立简单无向图G=<VE>该商场两排货架 之间的通道为G的边通道交叉处为G的顶点为使顾客 在任何一个货架前都能看到收款台。从尽可能减少收 款台的数目来说。收款台应设在通道的交叉处。故收 款台的设置问题转化为在G中找出一个最小点覆盖或 G的一个最大独立集
独立集的应用举例 例：(收款台的设置问题)某大型商场为加强经营 管理，对商品的零售收入实行统一收款制度。 为了使顾客在任何一个货架前都能看到收款台， 问收款台应设置在什么地方且至少要设置多少 个收款台? 问题分析:建立简单无向图G=<V,E>,该商场两排货架 之间的通道为G的边,通道交叉处为G的顶点.为使顾客 在任何一个货架前都能看到收款台。从尽可能减少收 款台的数目来说。收款台应设在通道的交叉处。故收 款台的设置问题转化为在G中找出一个最小点覆盖或 G的一个最大独立集
矩阵变换求独立集 设G一=<V,E>是简单无向图,同时将G的邻 接矩阵第与第行,第冽与第例列互换, 称为一次平移变换。 说明:平移变换不改变邻接矩阵所表示图G 的各顶点之间的关系,紧紧仅仅改变了i j的编号。也就是说:邻接矩阵的平移变 换对应于图中结点的一个重新编号。反 之,结点的重新编号对应于邻接矩阵的 系列平移变换
矩阵变换求独立集 设G=<V,E>是简单无向图，同时将G的邻 接矩阵第i行与第j行, 第i列与第j列互换, 称为一次平移变换。 说明:平移变换不改变邻接矩阵所表示图G 的各顶点之间的关系，紧紧仅仅改变了i， j的编号。也就是说，邻接矩阵的平移变 换对应于图中结点的一个重新编号。反 之，结点的重新编号对应于邻接矩阵的 一系列平移变换
定理:设G=(V,E)是具有n个节点的无向简单图, A是G的邻接矩阵,且A具有如下分块矩阵形式: 其中A2∈R(n-)(m), 1+1,1 1+1.1 i+21 2,2 1+2,1 n.2 令b=∑(=计+1,…,m,若b>0(=i+1,…,m),(3) 则其已确定一极大独立集S={2} 其中,V(1≤1≤为A下三角阵的第行
证明: 由矩阵A可知a(1S1)即结点v,V2,…v1 互不相邻。在A21中,因b(计+l≤j≤n),则 j194j25 a中必有一元素为1,不妨设a=(1 ≤i,即v与v相邻。由j={计+1,+2,,n}的任意性 得{v1,V计…,wn}中所有元素都与S={v1,V2,y} 相邻接,而S={1,V2…,wv中任何两点不邻接。 由极大独立集的定义可知S={v1,V2,,}即为G 的一个极大独立集
证明: 由矩阵A可知,akj(1 ji),即结点v1 , v2 , …, vi 互不相邻。在A21中,因bj (i+1 jn)，则 aj1,aj2,…,aji中必有一元素为1，不妨设ajk=1(1 ji),即vj与vk相邻。由j={i+1,i+2,…,n}的任意性 得{vi+1, vi+,…, vn }中所有元素都与S={v1 , v2 ,…, vi } 相邻接，而S={v1 , v2 ,…, vi }中任何两点不邻接。 由极大独立集的定义可知S={v1 , v2 ,…, vi }即为G 的一个极大独立集
定理:设A是简单无向图G=(V,E的邻接矩阵,则总可以经过 若干次平移变换把A化为标准型,从而得到图G的一个极大独立集 证明:设一邻接矩阵A,通过一系列平移变换,可将A化为形如式 (1)的形式,如果A是标准型,即可找出极大独立集{12,…}。若 A不是标准型,则41中必有一行元素全为0,不妨设第k(k>)行元 素=0(1≤j≤)。将第i+1项与第项进行平移变换,得到一新的 矩阵!',再判断'是否为标准型。我们知道,这种平移变换仅对应 于图中节点的一个重新编号,不影响该矩阵所表示图G各点之间的 邻接关系