| 关于图同构复杂性的一点补充 |
| |
| 引用本文： | 罗示丰.关于图同构复杂性的一点补充[J].广西科学院学报,2004,20(3):133-136. |
| |
| 作者姓名： | 罗示丰 |
| |
| 作者单位： | 广西大学计算机与信息工程学院,广西,南宁,530004 |
| |
| 摘 要： | 在图G=(V，E)中，删除其度数最大的顶点及其关联的边，在余下的子图中，如法炮制，直至余下的子图为零图．设所删除的这些顶点x1，x2，…，xi的度数依次为P1，P2，…，Pl，称序列P1，P2，…，Pl为图G的度序列；xi(1≤i≤l)关联的边的另一端点在G中的度数的集合称为顶点五关联的度集合．通过计算、比较两图的度序列、被删除的顶点的度数以及它们关联的度集合，证明两图同构问题的复杂度是多项式的．
|
| 关 键 词： | 图 同构复杂性 多项式 度序列 度集合 |
| 收稿时间： | 2004/2/15 0:00:00 |
| 修稿时间： | 2004年2月15日 |
A Supplement of the Complexity of Graph Isomorphism Test |
| |
| Luo Shifeng.A Supplement of the Complexity of Graph Isomorphism Test[J].Journal of Guangxi Academy of Sciences,2004,20(3):133-136. |
| |
| Authors: | Luo Shifeng |
| |
| Institution: | Coll. of Comp. & Info. Engi., Guangxi Univ., Nanning, Guangxi, 530004, China |
| |
| Abstract: | |
| |
| Keywords: | graph isomorphism complexity polynomial degree series degree set |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《广西科学院学报》浏览原始摘要信息 |
| 点击此处可从《广西科学院学报》下载免费的PDF全文 |
