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

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