重庆科技学院学报（自然科学版）
重慶科技學院學報（自然科學版）
중경과기학원학보（자연과학판）
JOURNAL OF CHONGQING UNIVERSITY OF SCIENCE AND TECHNOLOGY(NATURAL SCIENCE)
2009年
4期
171-173
,共3页
最小填充%标号%格子图%分解定理
最小填充%標號%格子圖%分解定理
최소전충%표호%격자도%분해정리
一个图的最小填充数就是确定顶点的一个标号顺序,按此顺序消去顶点时最少的添加边数.格子图是实际中遇到最多的一类稀疏图.利用图的分解定理和约化准则,讨论了平面格子图PmPn的最小填充,确定了m=4,5,6时的填充数表达式和它的一些界.
一箇圖的最小填充數就是確定頂點的一箇標號順序,按此順序消去頂點時最少的添加邊數.格子圖是實際中遇到最多的一類稀疏圖.利用圖的分解定理和約化準則,討論瞭平麵格子圖PmPn的最小填充,確定瞭m=4,5,6時的填充數錶達式和它的一些界.
일개도적최소전충수취시학정정점적일개표호순서,안차순서소거정점시최소적첨가변수.격자도시실제중우도최다적일류희소도.이용도적분해정리화약화준칙,토론료평면격자도PmPn적최소전충,학정료m=4,5,6시적전충수표체식화타적일사계.
