排序方式: 共有68条查询结果,搜索用时 24 毫秒
1.
2.
3.
混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上.混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色.所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数.上、下色数与边数有密切关系.作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数.该文证明当n=2k 1时,该下界是可以达到的. 相似文献
4.
设k是一个正整数,G是一个顶点数为|G|=4k的图. 假设σ\-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路,使得所有这些圈和路都是相互独立的. 设G=(V\-1,V \-2;E)是一个二分图使得|V\-1|=|V\-2|=2k. 如果对G中每一对满足x∈V\-1和y∈V\-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路,使得所有这些圈和路都是相互独立的,并且此度条件是最好的. 相似文献
5.
6.
(mg+k,mf—k)—图中正交于r个不相交子图的边不变的(g,f)—因子 总被引:3,自引:0,他引:3
设m,k和r为正整数,且使l≤k<m.设G是一个具有顶点集合V(G)和边集合E(G)的图,并设g和f是定义在V(G)上的使对每个x∈V(G)有r≤g(x)≤f(x)的整数值函数.设H1,H2,…,Hr是G的r个顶点不相交的子图且|E(Hi)|=k,1≤i≤r.本文证明了每个(mg+k,mf-k)-图有k个边不相交的(g,f)-因子正交于Hi,1≤i≤r. 相似文献
7.
1.引言 Edmonds给出了求一个图的最大权对集的算法它是从一个满足原始对偶可行的解出发使其逐步满足互补松驰条件。[1]描述了一个求最大权完美对集原始算法。它是从一个满足互补松驰条件的原始可行解出发,使其逐步满足对偶可行条件。我们给出一个求图的最大权完美对集的对偶算法,它是从一个满足互补松驰条件的对偶可行解出发使其逐步满足可行条件。本算法开始不要求给出图的一个完全对集,其对偶变量的改变法则也较[1]中的法则简单得多。其基本方法仍是用Edmonds的花的算法[2]。我们将说明本文的算法可用来解其他的最优对集问题。本文中采用的术语参看[2]。 相似文献
8.
9.
树的概念分别由Ljamin 及 Bolloba’s等人在超图中做了不同的推广,他们研究了超树的顶点数与边数的关系及复盖数等。本文中的γ-超树是 Ljamin超树的特例.文中给出了一个γ-超树有1-因子的充分必要条件,推广了Chungphaisam关于树的因子定理. 本文中未加说明的记号和述语皆见[4].超图H=(X,E)的秩γ(H)=max|Ei|.超图H=(X,E)的圈是一个顶点和边的交错序列{x_1,E_1,x_2,E_2,…,x_q,E_q,x_(q 1)}使x_i∈X,E_i∈E,x_i,x_(i 1)∈E_i, i=1,…,q,其中x_(q 1)=x_1;i≠j时E_i≠E_j,x_i≠x_j,且q>1. 由此定义易见一个超图不合圈,则任意的E_i,E_j∈E,E_i≠E_j必有|E_i∩E_j|≤1. 相似文献
10.
本文证明了一个无圈超图 H=(X,E)有1-因子当且仅当(?)S(?)X,sum from i=1 to r-1(r-i)q_i≤|S|,其中 q_i 表示 H 的子超图 H-S 的顶点数模 r 等于 i 的连通分支数,r 是超图 H 的秩. 相似文献