应用破圈法求图的最优树的一种新算法

本文依据破圈法的原理提出了求图的最优树的一种新算法,并给出了具体的实现步骤。     

最小可行图问题的一个必要条件及总结

设有n个集合X1,X2,…，Xn,一个以X＝∪i=1nXi为顶点集的图G称为一个关于集合序列（X1，X2，…，Xn)的可行图，如果对每一个Xi(i=1,2,…，n)，导出图Gi=G[Xi]是连通的。那么集合序列（X1，X2，…，Xn)的含最少边数的可行图称为关于（X1，X2，…，Xn)的最小可行图。曾得出了n=3时集合序列（X1，X2，X3）的最小可行图的一个充分必要条件。下面得出了n=4时集合序列（X1，X2，X3，X4）的最小可行图的一个必要条件，并用一个例子说明了n=3时的判定最小可行图的充分必要条件，不能推广至n≥4的情况，对最小可行图问题做了总结。     

最小可行图的一个必要条件

本文研究了n=4时的集合序列X_1,X_2,X_3,X_4的可行图是最小可行图的一个必要条件。它部分地发展了文献[3]在1989年得到的结果。     

最小可行图问题的一个必要条件及总结

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni =1 Xi 为顶点集的图G称为一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。那么集合序列 (X1,X2 ,… ,Xn)的含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。曾得出了n =3时集合序列 (X1,X2 ,X3 )的最小可行图的一个充分必要条件。下面得出了n =4时集合序列 (X1,X2 ,X3 ,X4 )的最小可行图的一个必要条件 ,并用一个例子说明了n =3时的判定最小可行图的充分必要条件 ,不能推广至n≥ 4的情况 ,对最小可行图问题做了总结     

有关Woodall问题的一个充分条件

在一系列对Ｗｏｏｄａｌ问题的探索中，文献［２］得出了：如果ｂｉｎｄ（Ｇ）≥１＋５２，则图Ｇ包含三角形；文献［３］得出了：如果ｂｉｎｄ（Ｇ）≥１１６（１１＋１８５），则图Ｇ包含三角形。文中对此问题进行了研究，得出了一种新的思路与方法，用此种方法不仅可得出文献［２］、［３］的研究成果，也简化了有关Ｗｏｏｄａｌ问题现已得到的研究结果的推导步骤，同时对进一步研究Ｗｏｏｄａｌ问题奠定了较好的基础。     

一个定理的简单证明

图G的结合效定义为：文献[2]证明了定理：若，则图G含K3.用简捷的方法证明了此定理，简化了文献[2]中此定理的证明过程，从而为改进关于Woodall猜想的系列结果提供了新思路和方法．     

图的结合数与Woodall猜想B

文献［１］中Ｗｏｏｄａｌｌ猜想：若，则图Ｇ包含三角形．文献［２］中，这个猜想作为第２２个尚未解决的问题．本文证明：若，则图Ｇ包含三角形．     

关于可行图的几个新结论

设有n个集合X1,X2,…,Xn,一个以X＝∪i=1^nXi为顶点集的图G称为是一个关于集合序列（X1,X2,…,Xn）的可行图,如果对每一个Xi(i=1,2,…,n),导出子图Gi=G[Xi]是连通的。集合序列（X1,X2,…,Xn）含最少边数的可行图称为关于（X1,X2,…,Xn）的最小可行图。将n=3推广至任意的自然数n,得出了集合序列（X1,X2,…,Xn）的最小可行图G=∪i=1^nGi,当满足∩i=1^nXi≠φ时,G是关于集合序列（X1,X2,…Xn）的最小可行图的一个充分必要条件,同时得出了集合序列（X1,X2,…,Xn）的最小可行图在某种条件下的两个主要结果。     

关于某些新的非协调图

Graham和Slone引入了协调图的概念。一个具有q条边的图G是协调图 ,如果有一个从G的顶点集到模 q的整数群的一个单射 ,使得当每一条边xy被分配标号f(x) +f(y) (modq)时 ,所产生的边标号是不同的。利用数论的方法证明了一些新的非协调图     

关于可行图的几个新结论

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni=1Xi 为顶点集的图G称为是一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1 ,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。集合序列 (X1,X2 ,… ,Xn)含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。将n =3推广至任意的自然数n ,得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图G =∪ni=1Gi,当满足∩ni=1Xi≠Φ时 ,G是关于集合序列 (X1,X2 ,… ,Xn)的最小可行图的一个充分必要条件 ,同时得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图在某种条件下的两个主要结果。