| 摘要: |
| 在图G=(V,E)中,删除其度数最大的顶点及其关联的边,在余下的子图中,如法炮制,直至余下的子图为零图.设所删除的这些顶点x1,x2,…,xi的度数依次为P1,P2,…,Pl,称序列P1,P2,…,Pl为图G的度序列;xi(1≤i≤l)关联的边的另一端点在G中的度数的集合称为顶点xi关联的度集合.通过计算、比较两图的度序列、被删除的顶点的度数以及它们关联的度集合,证明两图同构问题的复杂度是多项式的 |
| 关键词: 图同构 复杂性 多项式 度序列 度集合 |
| DOI： |
| 投稿时间：2004-02-15修订日期：2004-05-02 |
| 基金项目: |
|
| A Supplement of the Complexity of Graph Isomorphism Test |
|
Luo Shifeng
|
| (Coll. of Comp. & Info. Engi., Guangxi Univ., Nanning, Guangxi, 530004, China) |
| Abstract: |
| The vertex with maximum degree and its incidence edges in the graph G are deleted. The remaning subgraphs follow in the same way until the last subgraph empty. If degrees of the deleted vertexes x1,x2,…,xl are P1,P2,…,Pl in order. The series P1,P2,…,Pl is called the degree-series of the graph G. The set consists of the degrees of other ends of the incidance edges of xi(1 ≤ i ≤ l) in graph G,is called the incidence degree-set of xi. The complexity of graph isomorphism test is proved to be polynomial by calculating and comparing the degree-series,the degrees of the deleted vertexes and their incidence degree-set. |
| Key words: graph isomorphism complexity polynomial degree-series degree-set |
