关于图同构复杂性的一点补充

• 作者: 罗示丰
• 来源期刊: 广西科学院学报
• 学科: 数学
• 关键词: 图同构 复杂性 多项式 度序列 度集合
• 年，卷（期）: 2004,（3）
• 页码范围: 133-136
• 页数: 4页
• 分类号: O157.5
• 字数: 3014字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-7378.2004.03.003

摘要

在图G=(V,E)中,删除其度数最大的顶点及其关联的边,在余下的子图中,如法炮制,直至余下的子图为零图.设所删除的这些顶点x1,x2,…,xi的度数依次为P1,P2,…,Pl,称序列P1,P2,…,Pl为图G的度序列;xi(1≤i≤l)关联的边的另一端点在G中的度数的集合称为顶点xi关联的度集合.通过计算、比较两图的度序列、被删除的顶点的度数以及它们关联的度集合,证明两图同构问题的复杂度是多项式的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	罗示丰	广西大学计算机与信息工程学院	4	8	2.0	2.0