排序方式: 共有39条查询结果,搜索用时 15 毫秒
1.
针对Vizirtg猜想△为9的情况,运用Discharging差值转移方法研究了9-临界图的边数下界,得到了新结论:m≥10^-36n,改进了已有结果。 相似文献
2.
利用扇,断片及简约图的概念,得到不为轮的极小3连通图的非基本边数与其简约图的非基本边数相等,从而将求极小3连通图的非基本边数问题转化为求其简约图的非基本边数问题后,给出简约极小3连通图非基本边数的一个下界,刻画了达到下界的图类. 相似文献
3.
设 f(n)是有 n 个顶点的任何两个圈的长均不相等的图的最大可能边数。P.Erdos在1975年提出了确定 f(n)的问题(见[1]问题11)。Y.Shi[2]证明了:对于每个 n≥3,f(n)≥n [((8n-23)~(1/2) 1)/2];作者在[3][4][5]证明了:对于每个 n>((2m 3)/4)e~(2m),f(n)相似文献
5.
6.
李登信 《重庆工商大学学报(自然科学版)》2008,25(3):223-225
若C有一个生成子图是欧拉图,则称G是超欧拉图(supereulerian graph).用SL表示全体超欧拉图的集合.1995年,赖虹建(LAI Hong-jian)、陈志宏(CHEN Zhi-hong)提出一个关于欧拉生成子图边数的公开问题;决定:L=min max G∈SL-{K1}{|E(H)|/|E(G)|} : H是G的欧拉生成子图}定义了一些含两棵边不相交生成树的图Fi(i=1,2,3),证明了如果G∈F3,那么L≥2/3. 相似文献
7.
利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 . 相似文献
8.
李登信 《重庆工商大学学报(自然科学版)》2007,24(3):215-217
设G是超欧拉图,X是G的子图.在G中,把X的点收缩为一个点vX,去掉X的边,得到G关于子图X的收缩,记为G/X.引入a—子图的概念,得到了若干a—子图,并表明如何利用a—子图来寻找欧拉生成子图的最大边数. 相似文献
9.
李霄民 《重庆工商大学学报(自然科学版)》2007,24(3):218-220
对极大欧拉生成子图为Hamilton圈的图作了初步研究,得到了该类图的极大欧拉生成子图的边数问题,在一定条件下满足3/5—猜想,并给出了一个公开问题;同时也得到了该类图的最小度及最大度的上界. 相似文献
10.
一类双约束最短路问题的近似算法 总被引:1,自引:0,他引:1
带时间和边数约束的双约束最短路问题是NP-完备的。它的一种拟多项式精确算法可以利用动态规划方法给出,在此基础上采用rounding和scaling的处理技术得到了一种全多项式时间近似方案(FPAS)。 相似文献