共查询到18条相似文献,搜索用时 103 毫秒
1.
2.
讨论欧拉跳跃图,给出一个图是欧拉图,其跳跃图J(G)是欧拉图的充要条件及一个连通图G=(p,q)的跳跃图J(G)是欧拉图的充要条件,即定理1:设G=(p,q)是欧拉图,则J(G)是欧拉图当且仅当q≥5为奇数.定理2:设G=(p,q)是连通图,则J(G)是欧拉图的充要条件是⑴q≥5是奇数且q>ζ 1,每点的度有相同的奇偶性;⑵q≥6是偶数且q>ζ 1,任意一边的两端点的度有相异的奇偶性.其中ζ=max{d|u| d(v)|uv∈E(G)}. 相似文献
3.
4.
证明了非平面欧拉图在边连通度满足一定条件下可以表示成不超过|V|-2个边不重的圈的并,其中|V|是图的顶点数。 相似文献
5.
关于Hamilton图的充分必要条件 总被引:2,自引:0,他引:2
引入与图G具有相同连通性的图G的相关简单图GR的概念,并通过对GN的邻接矩阵的恒式的研究,给出了任意图G是Hamilton图的充分必要条件,得到了以下主要结论:定理:图G是Hamilton图的充分必要条件,是图G的相关简单图GR的邻接矩阵的恒式PerGR不为0。 相似文献
6.
7.
钮延英 《内蒙古大学学报(自然科学版)》1994,25(5):461-464
用g(G)表示图G的围长。S(k_1,k_2)表示两个非1度顶点分别为k_1,k_2的重星。在[2]中证明了:(2k+1)─正则图G是S(k+1,k+1)─可分解的充分必要条件是图G含有1─因子。本文证明的主要结果是:1)设图G是r(2k+1)─正则图(r≥2)且g(C)≥4,如果G含有r─因子,则图G是S(k+1,k+1)─可分解的。2)设q=|E(S(k,k))|,如果,n=1(mod2q),则完全图K_n是S(k,k)─可分解的。 相似文献
8.
该文证明了从任何一个n阶图中一个接一个地移去最大团,则移去团的顶点和达n^2/2后是空图,从而证明了Winkler猜想。 相似文献
9.
王斌 《西南师范大学学报(自然科学版)》2003,28(1):30-32
得到了超欧拉图的一个特征性质:G是简单图,则G是超欧拉图当且仅当G中有边不交路P1,…,Ps,使得E(Pi)连通.利用它可以证明:当m,n不其端点两两不同,并且满足O(G)={Pi的端点|=1,2,…,s},G-∪si=1同时为3时,m×n型矩形网格图是超欧拉图. 相似文献
10.
11.
孙君意 《北京联合大学学报(自然科学版)》2005,19(3):30-33
讨论了"单词接龙"的求解问题.运用图论中的欧拉定理建立了数学模型,并且设计了比较优化的算法,编制了程序.对任意一组单词,该程序可以判断出它们能否完成接龙.经测试,该算法较之传统的穷举法明显地降低了复杂度. 相似文献
12.
本文应用群论方法,证明了有限交换群的连通无向色图G(F,S)是Hamilton图。并由此得到:(i)Boosch—Tindell猜想的另一证明;(ii)有限交换群F具有对称色集S的连通色图D(F,S)是有向Hamilton图。 相似文献
13.
介绍了一类拟树所包含的Euler子图的个数,给出了简洁的计算公式,并进行了严格、详尽的证明.有关结果在理论物理的某些研究中具有重要的理论与应用价值。 相似文献
14.
刘春峰 《宁夏大学学报(自然科学版)》1991,12(3):22-28
设G是一个简单图,(?)e∈E(G),定义e=uv的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为u和v的度。本文的主要结果是:设G是n≥3阶几乎无桥的简单连通图,且G≠K_(1(?)n-1),G不含C_3和C_4,若对任何三个相互点不交的边e_0,e_1和e_2,d(e_0)+d(e_1)+d(e_2)≥n+7,则G有一个D-闭迹,从而G的线图L(G)是哈密顿图。 相似文献
15.
设图G为含有三角形或四边形的三次图,G_△为G的二角形收缩;G_□为G的四边形收缩。本文用计算机辅助证明了,若L(G)是2类的,则L(G_□)是2类的,若L~2(G)为2类的,则L~2(G_△)或L~2(G_□)为2类的。 相似文献
16.
17.
分析由延长而形成哈密顿回路、欧拉回路的特点,得出求图G(n,m)的最大回路算法:给定始结点xi和始边ei(xj).采用最长路回延长法,对点xi和边ei(xj)分别求最长路回HE序列,在对点xi求最长路回HE序列中,当出现长度为n的点回路的最长项,边ei(xj)出现长度为m的边回路的最长项,或延长后所得路径中没有元素,便结束延长;如对点xi有长度为n的最大点回路最长项,则G(n,m)为哈密顿图;如对边ei(xj)有长度为m的最大边回路最长项,则G(n,m)为欧拉图. 相似文献
18.