搜索结果: 151-165 共查到“知识库 图论”相关记录301条 . 查询时间(1.312 秒)
关于连通图幂中边不交1-因子
1-因子 边不交 连通图幂
2009/9/18
本文讨论连通图幂 G~n 存在 n 个边不交1-因子的条件.本文中所指图均为简单图.除特别强调外,所用术语、记号均与[1]中一致。定义.设 G 为简单连通图,n 为自然数,则 G~n 为 V(G~n)=V(G),E(G~n)={uv:d_G(u,v)≤n,u,v,∈V(G)}.对 G~n 的因子已有不少结果.主要有以下几个...
关于图 G_Δ的圈秩较小时的边色数分类
边色数分类 圈秩 图 G_Δ
2009/9/18
设 G 是简单连通图,由 Vizing 定理知,△(G)≤x′(G)≤△(G)+1,其中△(G)表示图 G 的最大顶点次,x′(G)是 G 的边色数.若 x′(G)=△(G),则称 G 为第一类图,记为 G∈C~1;否则称 G 为第二类图,记为 G∈C~2.其它图论术语及记号均与[1]一致.令 F={u|d(u)=△(G),u∈y(G)},记 GΔ=G[F].一条边 e(或顶点 v)称...
1987年,文献[1]中给出了图的升分解概念.已知图 G 和自然数 n,G 的边数 q 满足\[\left(\begin{array} .
关于图的团符号控制数
团符号控制函数 团符号控制数 平面图 轮 完全$m$-部图.}
2009/9/18
引入了图的团符号控制的概念, 给出了$n$阶图$G$的团符号控制数$\gamma_{ks}(G)$的若干下限, 确定了几类特殊图的团符号控制数, 并提出了若干未解决的问题和猜想.
关于(f,g)-因子定理的注记
学图 因子定理 f,g
2009/9/18
关于（ｆ，ｇ）－因子定理的注记蔡茂诚（中国科学院系统科学研究所，北京１０００８０）国家自然科学基金资助项目．１９９３年２月５日收到．我们只考虑有限的一般图，允许多重边和自环．一般图记作Ｇ＝（Ｖ，Ｅ），其中Ｖ（Ｇ）是点集合，而Ｅ（Ｇ）是边集合．对于任意点，用记点。的度，即Ｇ中关联于ｖ的边数，自环要计算两次．对于任意点子集表示从Ｃ中去掉Ｘ的所有点及其关联边所得到的学图，记若Ｘ和是Ｖ（Ｇ）的不相交.....
局部连通度至多是1的有向图的最大弧数
最大弧数 有向图 局部连通度
2009/9/18
设 D=(V,A)是局部连通度至多是1的严格有向图,令 n 和 e(D)分别表示 D 的点数和弧数.本文证明:若 n≤7,则 e(D)≤2(n-1);若 n≥7,则 e(D)≤[(n~2)/4];并且给出极图的完全刻画.
具有 Hamilton 性的次序列
次序列 Hamilton 性
2009/9/18
朱永津、刘振宏在[1]中给出了两类次序列,它们不满足 Chvátal 条件,其中一类甚至不满足 Bondy 和 Chvátal 的 n-闭包是完全图的条件,但它们却都保证了图的Hamilton 圈的存在.本文推广了[1]的结果,得到了更为广泛的两大类具有前述性质的次序列.
具有给定性质的(g,f)因子
因子 g,f 给定性质
2009/9/18
本文考虑的图 G 均为无环边的有限图.文中未定义的符号及术语均引自[1].对S,T\subseteq V(G),使得 S∩T=\varphi,我们用 E_G(S,T)表示 G 的端点分别包含在 S 及 T 中的边的集合.记 e_G(S,T)=|E_G(S,T)|.
文中未加说明的述语均同于[1]。给定图 G,以 c(G)记其联通分支数,定义h(G)=min{|s|-c(G\S):S(?)V(G),c(G\S)>1},f(G)=min{d(u)+d(v):u、v∈v(G),u=v,uv\not\in E}。1978年 H.A.Jung 在[2]中证明了,当 f(G)≥n(G)-4,n(G)≥11,h(G)≥0时,G 含哈密顿圈。本文研究了上述参数与图中最长链所...
两类 Hamilton 次序列
无向图 Hamilton 次序列
2009/9/18
无向图中 Hamilton 圈存在的充分条件,虽有一些,但几乎都包含在 Chvátal 的次序列条件和 Bondy 与 Chvátal 的 n-稳定闭包是完全图的条件里.本文提出两类次序列,虽然它们都不满足 Chvátal 条件,并且也有一个不满足闭包是完全图的条件,但是却都保证了图的 Hamilton 圈的存在性.从而为进一步从次序列方面研究图的 Hamilton 性,提供了新的依据.
偶图中彼此不交的对集
对集 偶图
2009/9/18
本短文考虑偶图中k个彼此不交的对集存在的充要条件. 先引进几个术语和记号. 给定集合S及其子集族={A_1,A_2,…,A_n}.对于S的子集R如果存在一一对应:R→{1,2,…,n),使得对于每个r∈R,r∈A_((r)),则称R为的不同代表系.类似地,定义的部分不同代表系R’,如果R’是部分子集族的不同代表系.
一个图 G 的平方图(记作 G~2),是在 G 中把所有距离为2的点对用边相邻接而形成的图.本文主要结果是:定理.如果 G 是连通,无 S(K_(1,3))导出子图的图,则 G~2是顶点泛圈图.这样,Gould 和 Jacobson 提出的两个猜想得到证明.结合这一方向上已有的工作,平方图的汉米尔顿问题基本上得到满意的解决.
图 K_n—E(kP_s∪rP_t)的色唯一性
色唯一性 K_n—E(kP_s∪rP_t) 图
2009/9/18
本文仅考虑有限、无向、无环的简单图.P(G,λ)表示图 G 的色多项式.如果从P(H,λ)=P(G,λ)可以推出图 H 和 G 同构,则称 G 是色唯一的.设 G 是一个顶点数不超过 n 的图,用 K_n—E(G)表示从完全图 K_n 中删去一个和G 同构的子图的所有边而得到的图.关于 K_n—E(G)型图中的色唯一图的研究已有不少结果,参见[1—5].
围长对是(4,5)的最小正则图
最小正则图 4,5 围长对
2009/9/18
我们把围长对是(g,h)的 k-正则图称为(k;g,h)-图;(k;g,h)-图的顶点的最少数目用 f(k;g,h)表示.本文证明了(?)我们还构造了最小(2s+1;4,5)-图,s≥1的无限族.这样,我们就完全解决了 Harary和 Kovács 提出的问题1.
乡村投递员问题的多面体
边集合连通无向图
2009/9/18
设 G=(V,E)是以 V 为顶点集,E 为边集合的连通无向图.对任意的 E′\subseteq E,以G[E′]记 G 的由 E′中的边所组成的子图,称之为边集 E′导出的子图.称边序列 w=〈(i_0,i_1,),(i_1,i_2),…,(i_(k-1),i_k)〉为连接 i_0和 i_k 的路,其中 i_j∈V,(i_j,i_(j+1)∈E,0≤j≤k-1.如果 i_0=i_k,则称 w ...