设G是一个简单连通图,若{G_1,G_2,…,G_R}是图G的一组支撑子图,且满足:(1)G_i是连通图,i=1,2,…,R;(2) 对任何1≤i≠j≤R,有E(G_i)∩E(G_j)=φ;(3)∪E(G_i) from i=1 to R=E(G);(4) R是满足上述条件的最大正整数,则称{G_1,G_2,…,G_R}为...设G是一个简单连通图,若{G_1,G_2,…,G_R}是图G的一组支撑子图,且满足:(1)G_i是连通图,i=1,2,…,R;(2) 对任何1≤i≠j≤R,有E(G_i)∩E(G_j)=φ;(3)∪E(G_i) from i=1 to R=E(G);(4) R是满足上述条件的最大正整数,则称{G_1,G_2,…,G_R}为图G的一个连通支撑分解,并记R(G)=R,称它为图G的分解度。本文证明:R(K_n)=[n/2]和R(K_(m,n))=[nm/(n+m-1)],并且给出求子图的算法。展开更多
如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P...如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。展开更多
文摘设G是一个简单连通图,若{G_1,G_2,…,G_R}是图G的一组支撑子图,且满足:(1)G_i是连通图,i=1,2,…,R;(2) 对任何1≤i≠j≤R,有E(G_i)∩E(G_j)=φ;(3)∪E(G_i) from i=1 to R=E(G);(4) R是满足上述条件的最大正整数,则称{G_1,G_2,…,G_R}为图G的一个连通支撑分解,并记R(G)=R,称它为图G的分解度。本文证明:R(K_n)=[n/2]和R(K_(m,n))=[nm/(n+m-1)],并且给出求子图的算法。
文摘如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。
