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

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

多重图的同构

证明了下列结论：２个多重图同构的充分必要条件是它们有相合的ＶＣ算法。     

一种求Ramsey数的命题演算法

首先在矩阵中用谓词描述“含Kn”和“含－↑Km”，然后通过命题演算法逐行求出不含Kn也不含－↑Km的矩阵（aij)j=i 1,…，l^i=1,2,…l-1，若对于l≤r－1有这样的矩阵，而对于l=r却没有，则r为Ramsey数。     

有向图的同构

证明“图Ｇ与图Ｆ同构当且仅当它们有机合的ＶＣ算法”的结论,对于简单有向图依然成立。     

判别哈密尔顿图的新方法

提出求一个图的顶点覆盖的VC算法，定义图的VC表示式及其全闭链的概念，证明一个连通无向图是哈密顿图当且仅当其VC表示式含有一条全闭链，并证明对构造全闭链有用的定理和推论。