共查询到20条相似文献,搜索用时 15 毫秒
1.
1953年Landau引进了竞赛图中“王”的概念:如果竞赛图T的顶点v能通过长至多为2的有向路到达T的其他各个顶点,则称v 为王.他证明了,竞赛图中出度最大的顶点是王.1980年Maurer 证明了,对于整数n≥k≥1,不存在恰有k 个王和n 个顶点的竞赛图的充要条件是k=2或k=n=4.1982年Bridgland 和Reid 引进了下述概念:设T 是竞赛图,t、c 相似文献
2.
字典序地生成根树和树 总被引:1,自引:0,他引:1
文献[1]中给出了有序根树的一种序列表示方法,从而字典序地生成所有具有n个顶点的不同构的有序根树。现在我们在此基础上再进一步给出根树和树的序列表示方法,从而字典序地生成所有具有n个顶点的不同构的根树和树。 相似文献
3.
设F_2~n是二元域F_2上的n维向量空间,其中n≥1。以F_2~n的2~n个元作顶点,从每一个顶点a=(a_0,a_1,…,a_(n-1))出发,向顶点b=(a_1,a_2,…,a_(n-1),0)和b′=(a_1,…,a_(n-1),1)各做一条有向弧,得到一个有向图G_n,称为n级de Bruijn-Good图。从顶点a=(a_0,a_1,…,a_(n-1))到顶点b=(a_1,…,a_(n-1),a_n)的有向弧记作a→b或记作(a_0,a_1,…,a_(n-1),a_n)。因此G_n是以F_2~n为顶点集,F_2~(n 1)为弧集的有向图,即有G_n=(F_2~n,F_2~(n 1))。 相似文献
4.
Kelly提出:正则竞赛图T是否能分解为1/2(|T|-1)个弧不重的Hamilton回路(|T|表示T的顶点个数).此猜想是图论中至今未解决的难题之一.近年来,国外关于Kelly猜想的工作有:Alspach证明了9个顶点以下的 相似文献
5.
一、引言 1.令T=(V,A)为ρ个顶点的竞赛图,V为T的顶点集合,A为T的弧集合。 如果对T中每条弧e,都有一个长度为3的回路经过e,则称T为弧三回路的。如果对T中每条弧e,都有一个Hamilton回路经过e,则称T为弧Hamilton回路的。如果对T中每条 相似文献
6.
树的序列表示法及其在数树上的应用 总被引:1,自引:0,他引:1
谢力同等利用有序根树的每个顶点的次得到一个非负整数序列来表示一个有序根树。文献利用根树的每个分支的顶点数来排列各个分支的次序,从而得到一个方法:把所有的不同构的根树、树排列起来,并且能够依次数出来,而本文则利用树的每个顶点所确定的树枝的顶点数作出一个序列来表示一个树。这种表示法与过去的表示法不同,它不依赖于顶点 相似文献
7.
本文指出文献[1]定理2证明的错误之处,给出具有给定叶数的植树、自由树的计数公式。 以G_(n,m)、T_(n,m)、t_(n,m)分别表示n阶m叶植树、有向树、自由树的个数,其计数级数分别记为G(x,y)、T(x,y)、t(x,y)。 相似文献
8.
令m,n是正整数,F_2是由0和1两个元素组成的有限域,F_2上的2维(m,n)阶deBruijn-Good图是一有向图,它的顶点集合V由F_2上的m×n阵组成,即 它的弧集合由下面的2个集合E_1和E_2组成: 相似文献
9.
平面上一个三角格图是指边界为准矩形(上下为两条水平直线,左右两侧为折线)、网眼形状为三角形的一个网格图。将平面上的一个三角格图的左右两端在平面上分别按逆、顺时针方向运动,使两端折线重合,由此而生成的网格图,就是平面上的环形三角格图。例如,图1(a)和(b)是三角格图,(c)是相应的环形三角格图。在三角格图中,删去部分边或部分顶点而成的网格图,为方便起见,也称为三角格图。如果每个网眼是由水平直线族、斜率分别为+1和-1的直线族划分而成,且纵宽、横宽分别为m、n格,则称之为m×n三角格图,记为,其中i表示左端三角形列的形式。在中,i=(2)表示左端三角形列 相似文献
10.
11.
G.Chartrand在第四届国际图论会议(1980)上提出这样一个问题:若一连通图G分別有含m和n个端点的支撑树,m相似文献
12.
定义一个超图H的圈色数c(H),为将H的顶点染色使每个圈至少有两种颜色的顶点这样的染色法所需要的最少的颜色数。我们证明了若H有n个顶点,m条边,p个支及c(H)=c,则 相似文献
13.
14.
2-3树是一种很重要的平衡搜索树。文献[1]中叙述了2-3树(也叫3-2树)的定义(在每个内点上存放一个或两个关键字,且分别具有两个或三个儿子点;所有外点在同一层上)。显然,具有N个关键字的2-3树,其高度h在log_3(N 1)≤h≤log_2(N 1)之间。在这种树上的最坏搜索时间是O(h)。文献[1]中还给出了对它的O(h)时间的插入算法。通过该插入算法插入每个随机关键字而生成的2-3树叫动态自由2-3树。文献[2]研究了N→∞时这 相似文献
15.
圈长唯一的最大图的边数 总被引:4,自引:0,他引:4
Erds于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数。试确定f(n)。 含有f(n)条边、没有两个等长圈的n个顶点的图称为圈长唯一的最大图。 相似文献
16.
如果存在一个图G到图H的子图G′上的同构φ,我们就记作GH,说G嵌入到H内,而φ称为G到H内的一个嵌入。1982年,D.Bauer和R.Tindell对既不是道路,也不是K_(1,3)的图G定义了一个不变量∧(G),它是使GL~n(G)成立的最小的n,n≥1。他们研究了∧(G)=1的图,并提出研究∧(G)=2的图,以及对所有树T,确定∧(T)这两 相似文献
17.
在三角形T上定义并称之为T上的n次Bernstein多项式,其中(u,v,w)是点P关于三角形T的重心座标. 相似文献
18.
19.
所讨论的图均指无向、有限的简单图。图G的生成闭迹或S-闭迹(S-circuit)是指一个闭迹使得它含有图G的所有的顶点。如果G中存在一条闭迹T使得G的每条边至少有一个顶点在T上,则称T是D-闭迹(Dominating circuit)。连通图G称为几乎无桥的如果它们的每一个桥至少关联一个次数为1 相似文献