共查询到20条相似文献,搜索用时 0 毫秒
1.
主要证明了以下结果;1.如果G是一个连通的无爪的非哈密顿图,则G至少有一条长为2δ+的路。2.如果G是一个2连通的无爪图,且δ(p-2)/3,则G是可迹的。3.G是一个2连通的无爪图,且不含生成子图B工G1,如果G的每个朵匀于Z2的生成子图都满足ψ(α1,b1)ˇψ(α1,b2),则是G是泛圈图。 相似文献
2.
1974年,Erdos和Saucer提出如下问题:设f(p)是p个顶点的不含3正则子图的图的最大可能边数,确定f(p)。本文给出:(1)f(p)≥3p-9,p≥4;(2)f(p)≥3p-5,p≥34。 相似文献
3.
4.
5.
证明了如下结果:(1)若G是2-连通的(K1,3,P5,B)-自由图,或2-连通的(K1,3,Z2,P5)-自由图,则G是哈密顿图,(2)若G是3-连通的(K1,3,Z1)-自由图,或3-连通的(K1,3,Z2,P5)自由图,或3-连通的(K1,3,P5,B)-自由图,则G是哈密顿连通的。 相似文献
6.
7.
8.
孙志人 《南京师大学报(自然科学版)》1995,18(1):35-40
设G是k-连通无爪图,S是G的子图,G中过S所有顶点的路称为S-路,证明了:若a3(S)≤k+1,则G含S-路,这里a3(S)为S的在G中两两离至少为3的顶点的最大数目,推广了如下结论:若a(G^2)≥k+1,则G是可迹的,这里G^2为G的平方图。 相似文献
9.
10.
11.
图的同构判定算法:关联度序列法及其应用 总被引:10,自引:1,他引:9
提出了图的同构判定新算法,即关联度序列法和黄金分割关联度序列法,后者的计算时间复杂性远远低于2N(N为图的顶点数),已接近于多项式时间复杂性,该算法可应用于很多能用图来描述的式识别等实际问题。 相似文献
12.
哈密尔顿图与泛圈图的几个性质的探讨 总被引:1,自引:0,他引:1
让NC=min{U(x)∪N(y)||x,y∈V(G),xy不属于E(G|},R.J.Faudree等曾得到NC≥n-δ,则G是哈密尔顿图。本文进一步研究NC≥n-δ-1的哈密顿性,推广了文前人的结果。 相似文献
13.
从生活中的一个问题出发,运用图论知识进行了分析,得到了结论,并且对结论进行了推广 得到了在一般情况下简单图含有完全子图的充分条件 并且,在度数要求方面,这个结果是最佳可能的 相似文献
14.
邓依群 《郑州大学学报(理学版)》2003,35(3):20-22
对两个给定的图G和H,以G H表示G和H的联,以G[H]表示G对图H的结合图,证明了如下结果:(1)G H是Menger图当且仅当G和H均为Menger图;(2)若G和H均为Menger图,且G的任一导出子图也是Menger图,则G[H]必为Menger图。 相似文献
15.
令G(V,E)是简单图,Ore研究了不相邻两点情况的哈密尔顿连通图。本中,我们进一步研究较好条件的长为2点的哈密尔顿连通图情况。结果不仅比Ore的好而且证明方法更加简单。 相似文献
16.
在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高. 相似文献
17.
罗小伟 《吉首大学学报(自然科学版)》1994,15(5):22-23
独立集与临界图是图论中的重要概念,它们在数学的其它分支和实际问题中有广泛应用,在文中均有介绍,本文将证明一些临界图的性质。性质1设T1、T2…Tx是G的最大独立集,而X为任何独立集,设…Tk。则证明;首先考虑k=1的情形,显然此处,显然是独立的,因而,至多有a(G)个点,这样,即性质2设G1、G2是连通的a临界图且不同于K2。分裂一点为x1、x2,移动G2的一边(y1,y2),使xi与Yi此一致,这样得出的图是a临界的。证明:设T为G的独立集,如T至多包含X1,X2之一,则和(G2)分别为G1和G2中的独立集,由此,若x1,x2,则T和分别是… 相似文献
18.
19.
图的第二个最小特征值的界 总被引:2,自引:0,他引:2
徐光辉 《华东师范大学学报(自然科学版)》1993,(4):24-28
设G是n个顶点的简单图,λn-1(G)为G的第二个最小特征值。G的非孤立点形成的图记为G1,V(G1)=s,(3≤s≤n)。本文主要证明了:a.若G1不是完全偶图,则λn-1(G)≤λs-1(K2,s-2^-e),等式成立=G1≌K2,s-2^-^e。其中图K2,s-2^-^e为完全偶图K2,s-2去掉一边e而得到的图b.若G1既不是完全偶图,又不是K2,s-2^-e,则λn-1(G)<-√2/2 相似文献
20.