关于f—复盖图

如果图G的每一条边都属于一个f一因子,则称图G是f-复盖的。本文给出了一个图是f-复盖的充分必要条件,并且证明了若图G是m-复盖的及n-复盖的,m,n,k有同样的奇偶性且m相似文献   

关于图的路色数的一些结果

本文研究图的路色数，首无得到图的路色数的一些基本性质，其次给出了G满足X（G；P2）小于等于2的一个充分必要条件，该条件可以有效地应用于极大平面图和2－连通极大外平面图，最后证明了图的K－路色数问题NP-完全性（K≥3）。     

伪对集复盖图

若过图G的每条边都有一个亏数为d的伪对集,则称图G为亏数d-复盖图。本文给出了一个图是亏数d-复盖图的充分必要条件及该条件的一些应用,从而推广了Little 的结果.     

关于图的叉数的一个注记

本文改进了完全二分图的叉数的已知下界,并证明了,在已知的完全图的叉数上界μ(K_p)≤1/4[p/2][(p-1)/2][(p-2)/2][(p-3)/2]中,如果对奇数p等号成立,邸么对下一个偶数p+1也有等号成立。     

分组遗传算法用图的着色

图的着色算法是一种典型的ＮＰ－完全问题。在系统地讨论了图的正常顶点着色,边着色以及全着色的有关理论的基础上,提出了基于分组遗传算法和启发式搜索的图的正常ｋ－点着色,正常ｋ－边着色以及正常ｋ－全着色的新型混合算法,提出了评价算法性能的标准。实验仿真结果表明,新型混合算法可以获得问题高质量的解,即对图进行着色所使用的颜色数接近图的色数。     

求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G))|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G)|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

关于二分图的2-因子

证明：若Ｇ＝（Ｖｉ;Ｖ２;Ｅ）是一个二分简单图,│Ｖ１│＝│Ｖ２│＝ｎ≥２ｋ＋１且δ（Ｇ）≥〔ｎ／２〕＋１,那么Ｇ含一个２－因子,它恰有ｋ个分支。     

图顶点m着色的改进算法

对于解决图顶点着色问题，目前较常使用ＤＦＳ算法，而由于该算法存在效率不高问题，故提出ＤＦＳ改进算法，极大提高了该算法的效率，对于较难的图顶点着色问题，利用该改进算法更为有利。     

关于2—连通图哈密顿路的Lindquester猜测

本文证明了Lindquester猜测:设G是顶点数为n的2-连通图,如果对于G中任一对顶点u,v,距离d(u,v)=2|N(u)U N(v)|≥(n-1)/2,则G有哈密顿路。     

邻域并和[a,b]——消去图

本文给出了一个图是「ａ，ｂ」－消去图关于邻域并的充分条件。     

关于F-复盖的注记(英文)

本文主要给出F-复盖的直积还是一个F-复盖的充分条件和充要条件.假设右R-模类F在直积,直和项下封闭,{M_i}i∈I是一簇右R-模.如果每个φ_i:F_i→M_i都是M_i的具有唯一映射性质的F-复盖,且multiply from i∈I M_i有F-复盖,则可以得到是multiply from i∈I M_i的F-复盖.另外我们证明如果φ_i:F_i→M_i是M_i的F-复盖,且multiply from i∈I M_i有F-复盖,则是multiply from i∈I M_iF-复盖当且仅当multiply from i∈I Kerφ~i不包含multiply from i∈I F_i中的非零直和项.从而改进、推广了文[6]中的相应结果.     

K1,r—Free图的生成树及其算法

证明了任一连通的Ｋ１，ｒ－Ｆｒｅｅ图都有最大度小于等于ｒ的生成树，并建立了算法。