k-覆盖图的一个充分条件 被引量：5

1

作者 颜谨 傅少川 《山东工业大学学报》 1997年第4期360-364,共5页

论证了对整数ｎ（ｎ≥３）和ｋ（ｋ≥２），若ｋ为奇数，则令ｋ≥ｎ－１，Ｇ是一个不含Ｋ１，ｎ的２边连通图，ｋ｜Ｖ（Ｇ）｜≡ｏ（ｍｏｄ２），设Ｇ的顶点最小度α（Ｇ）至少为（ｎ２／４（ｎ－１））ｋ＋（３ｎ－６）／２＋（ｎ－... 论证了对整数ｎ（ｎ≥３）和ｋ（ｋ≥２），若ｋ为奇数，则令ｋ≥ｎ－１，Ｇ是一个不含Ｋ１，ｎ的２边连通图，ｋ｜Ｖ（Ｇ）｜≡ｏ（ｍｏｄ２），设Ｇ的顶点最小度α（Ｇ）至少为（ｎ２／４（ｎ－１））ｋ＋（３ｎ－６）／２＋（ｎ－１）／４ｋ，则Ｇ是ｋ覆盖图．并且说明了定理中条件“２边连通”不能减弱为“连通”． 展开更多

关键词 图 因子 K-覆盖图 充分条件

下载PDF 职称材料

关于图的线性点荫度 被引量：3

2

作者 陈东灵 《山东矿业学院学报》 CAS 1994年第1期92-95,共4页

Ｂｒｏｅｒｅ和Ｍｙｎｈａｒｄｔ等人猜想：任何平面图Ｇ的线性点荫度ｌａ（Ｇ）不超过３。本文证明了这个猜想，并证明了外平面图的线性点荫度ｌａ（Ｇ）不大于２。

关键词 图 平面图 线性点荫度

下载PDF 职称材料

平面图的完备染色 被引量：2

3

作者 吴建良 《山东矿业学院学报》 CAS 1994年第3期316-318,共3页

本文给出了两类可平面性的笛卡尔积图路与路、路与图的完备色数。

关键词 图 平面图 路 完备色数

下载PDF 职称材料

Ramsey数r(mC_4,nC_4) 被引量：2

4

作者 李大勇 王志坚 《上海铁道大学学报》 CAS 1999年第6期66-70,83,共6页

对于图Ｇ和图Ｈ，Ｒａｍｓｅｙ数ｒ（Ｇ，Ｈ）定义为最小正整数ｐ，使得经任意红兰２边着色的完全图Ｋｐ，或者其红色子图包含Ｇ，或者其兰色子图包含Ｈ。以ｍＣ４表示ｍ个互不相交的Ｃ４。得到以下结论：当ｎ≥ｍ≥１，（ｍ，ｎ）≠（... 对于图Ｇ和图Ｈ，Ｒａｍｓｅｙ数ｒ（Ｇ，Ｈ）定义为最小正整数ｐ，使得经任意红兰２边着色的完全图Ｋｐ，或者其红色子图包含Ｇ，或者其兰色子图包含Ｈ。以ｍＣ４表示ｍ个互不相交的Ｃ４。得到以下结论：当ｎ≥ｍ≥１，（ｍ，ｎ）≠（１，１）时，ｒ（ｍＣ４，ｎＣ４）＝２ｍ＋４ｎ－１。 展开更多

关键词 图 圈 RAMSEY数

下载PDF 职称材料

k-消去图的一个充分条件 被引量：3

5

作者 颜谨 《山东工业大学学报》 1999年第6期578-581,共4页

论证了 :对整数 n(n≥ 3 )和 k(k≥ 2 ) ,若 k为奇数则令 k≥n-1 ,G是一个不含k1,n的 2 -边连通图 ,k| V(G) |≡ 0 (mod2 ) ,设 G的顶点最小度 α(G)至少为 (n2 / 4 (n-1 ) ) k+(3 n-6) / 2 + (n-1 ) / 4 k,则 G是 k-消去图 .并且说明... 论证了 :对整数 n(n≥ 3 )和 k(k≥ 2 ) ,若 k为奇数则令 k≥n-1 ,G是一个不含k1,n的 2 -边连通图 ,k| V(G) |≡ 0 (mod2 ) ,设 G的顶点最小度 α(G)至少为 (n2 / 4 (n-1 ) ) k+(3 n-6) / 2 + (n-1 ) / 4 k,则 G是 k-消去图 .并且说明了定理中条件“2 -边连通”不能减弱为“连通” 展开更多

关键词 因子 消去法 K-消去图 充分条件

下载PDF 职称材料

无结图及其若干性质 被引量：2

6

作者 徐志才 《北京邮电大学学报》 EI CAS CSCD 1995年第1期79-83,共5页

给出了结、无结图、有结图等概念,然后提出了图G_0为无结图的充要条件,并论述了无结图的若干性质.

关键词 图(数学) 平面图 着色 结 无结图 有结图

下载PDF 职称材料

树图的 Hamilton 性质

7

作者 李乐学 《山东工业大学学报》 1997年第3期261-263,共3页

设Ｔ（Ｇ）为连通图Ｇ的树图，若Ｇ至少有三个支撑树，且ＧＳＦ１，则Ｔ（Ｇ）是Ｅ２－Ｈａｍｉｌｔｏｎ的．

关键词 图 圈 连通图 树图 哈密顿性质

下载PDF 职称材料

k─覆盖图的邻集和最小度 被引量：1

8

作者 滕聪 《山东工业大学学报》 1994年第1期21-28,共8页

研究了为保证一个图Ｇ是ｋ－覆盖图，Ｇ所具有的独立集邻集的基数和最小度。

关键词 因子 覆盖图 图论 邻集

下载PDF 职称材料

关于D－圈存在性的闭包定理

9

作者 孙惠泉 《北京邮电大学学报》 EI CAS CSCD 1994年第1期49-52,共4页

证明在ｖ≥３的连通图Ｇ中，如果ｕ与ｖ为二不相邻接顶点，且ｄ（ｕ）＋ｄ（ｖ）≥ｖ－１，则Ｇ中有Ｄ圈当且仅当Ｇ＋ｕｖ中有从Ｄ－圈．由此得到了Ｄ－圈存在性定理的一些推广．

关键词 连通图 D-圈 闭包 图论

下载PDF 职称材料

奇数度正则图的顶点数、边连通度和k-消去图

10

作者 颜瑾 《山东工业大学学报》 2000年第3期220-223,共4页

设 n为偶数 ,r和 k为奇数 ,n>r>k>0 ,λ≥ 2为整数 ,λ*=2 [λ/ 2 ] +1 ,r-λ*k>0 .G是有 n个顶点、边连通度为λ的 r-正则图 .若 n<( r+2 ) ( k+1 ) ,则 G是

关键词 图 因子 消去法 奇数度正则图 顶点数 边连通度 K-消去图

下载PDF 职称材料

独立数、连通度与r-覆盖

11

作者 杨大庆 滕聪 叶宏 《山东工业大学学报》 1998年第1期11-14,38,共5页

设Ｇ是一个图，如果对Ｇ的任一条边ｅ，Ｇ中存在包含ｅ的ｒ－因子，则称Ｇ是ｒ－覆盖图．文中证明了：如果ｒ≥１是一奇数，Ｇ是一图，｜Ｖ（Ｇ）｜为偶数．若Ｋ（Ｇ）≥（ｒ＋１）２／２，（ｒ＋１）２α（Ｇ）＜４ｒＫ（Ｇ），那么，... 设Ｇ是一个图，如果对Ｇ的任一条边ｅ，Ｇ中存在包含ｅ的ｒ－因子，则称Ｇ是ｒ－覆盖图．文中证明了：如果ｒ≥１是一奇数，Ｇ是一图，｜Ｖ（Ｇ）｜为偶数．若Ｋ（Ｇ）≥（ｒ＋１）２／２，（ｒ＋１）２α（Ｇ）＜４ｒＫ（Ｇ），那么，Ｇ是ｒ－覆盖的．如果ｒ≥２为偶数，图Ｇ满足：Ｋ（Ｇ）≥ｒ（ｒ＋２）／２，（ｒ＋２）α（Ｇ）＜４Ｋ（Ｇ），那么，Ｇ是ｒ－覆盖的． 展开更多

关键词 因子 覆盖 图独立数 连通度

下载PDF 职称材料

连通图的1-因子和(g,f)-覆盖图

12

作者 颜谨 《山东工业大学学报》 2000年第5期419-422,共4页

设 G是一个连通图且有一个 1 -因子 F,g和 f是定义在 V( G)上的整数值函数并且对每个 x∈V( G)都有 0≤g( x) <f( x)≤d G( x) .若对每个 xy∈F有 f( x) =f( y)且G-{ x,y}是 ( g,f) -覆盖图 ,则 G是 ( g,f) -覆盖的 .

关键词 因子 连通图 覆盖图 有限无向简单图

下载PDF 职称材料

r-正则图的顶点数、边连通度和k-覆盖图

13

作者 颜谨 《山东工业大学学报》 2001年第1期8-11,共4页

设 n为偶数 ,r和 k奇数 ,n>r>k>0 ,λ≥ 2为整数 ,λ* =2 [λ/2 ] +1 ,r-λ*k>0 .G是有 n个点、边连通度为 λ的 r-正则图 .若 n<( r+2 ) ( k+1 ) ,则 G是 k-覆盖的 .

关键词 因子 覆盖 r-正则图 顶点数 边连通度 K-覆盖图

下载PDF 职称材料

Job－shop问题的Branch－bound方法

14

作者 傅少川 曹建胜 张福祥 《山东工业大学学报》 1996年第A09期396-399,共4页

本文给出了Ｊｏｂ－ｓｈｏｐ问题的一种Ｂｒａｎｃｈ－ｂｏｕｎｄ方法。

关键词 分枝定界算法 关键路法 图 JOB-SHOP问题

下载PDF 职称材料

求图的［a，b］－因子的有效算法

15

作者 孙耀鲁 《山东工业大学学报》 CAS 1994年第2期159-164,共6页

求图的［ａ，ｂ］－因子的有效算法孙耀鲁（山东工业大学计算机工程系济南２５００１４）摘要＊给出了一个判断图中是否存在［ａ，ｂ］一因子的有效算法，其算法复杂性为０（｜Ｅ｜·｜Ｖ｜）．若图中存在［ａ，ｂ］－因子，该算法... 求图的［ａ，ｂ］－因子的有效算法孙耀鲁（山东工业大学计算机工程系济南２５００１４）摘要＊给出了一个判断图中是否存在［ａ，ｂ］一因子的有效算法，其算法复杂性为０（｜Ｅ｜·｜Ｖ｜）．若图中存在［ａ，ｂ］－因子，该算法求出一个［ａ，ｂ］－因子，否则给出一个... 展开更多

关键词 图 因子 图论 有效算法

下载PDF 职称材料

Ramsey数r(mC_5,nC_5)

16

作者 李大勇 王志坚 李鸿祥 《上海铁道大学学报》 CAS 1999年第12期59-63,共5页

对于图Ｇ和图Ｈ，Ｒａｍｓｅｙ 数ｒ（Ｇ，Ｈ） 定义最小正整数ｐ，使得经任意红、蓝２ 边着色的完全图Ｋｐ，或者其红色子图包含 Ｇ，或者其蓝色子图包含 Ｈ。以 ｍＣ５ 表示 ｍ 个互不相交的Ｃ５ 。可得：ｒ（ ｍＣ５ ，ｎＣ５） ＝... 对于图Ｇ和图Ｈ，Ｒａｍｓｅｙ 数ｒ（Ｇ，Ｈ） 定义最小正整数ｐ，使得经任意红、蓝２ 边着色的完全图Ｋｐ，或者其红色子图包含 Ｇ，或者其蓝色子图包含 Ｈ。以 ｍＣ５ 表示 ｍ 个互不相交的Ｃ５ 。可得：ｒ（ ｍＣ５ ，ｎＣ５） ＝５ｎ＋ ４，　　ｎ≥ｍ ＝ １３ ｍ ＋ ５ｎ －１ ，　　ｎ≥ｍ 展开更多

关键词 图 圈 RAMSEY数

下载PDF 职称材料

给定指数的对称本原矩阵的局部刻划

17

作者 李桂荣 何镇邦 +1 位作者 赵美英 谢文泉 《太原机械学院学报》 1993年第1期46-48,共3页

设S_n表示全体n阶对称本原非负矩阵的集合,S(n,d)={A∈S_n|G(A)中的最小奇圈之长为d}。文献[1]中证明了S(n,d)的指数集为{d-1,d,…,2n-d-1}\D,其中D为n-d+1到2n-d-2中的所有奇数与0之并集。本文证明若A∈S(n,d)且r(A)=m∈{d-1,d,…,2n-d... 设S_n表示全体n阶对称本原非负矩阵的集合,S(n,d)={A∈S_n|G(A)中的最小奇圈之长为d}。文献[1]中证明了S(n,d)的指数集为{d-1,d,…,2n-d-1}\D,其中D为n-d+1到2n-d-2中的所有奇数与0之并集。本文证明若A∈S(n,d)且r(A)=m∈{d-1,d,…,2n-d-1}\D,则A的伴随图G(A)必含子图P_l*C_d,其中l=(m-d+3)/2,P_l*C_d表示l长的路P_l的一个端点与d长的奇图C_d上一点重合所得到的连通图。 展开更多

关键词 本原矩阵 对称矩阵 伴随 图

下载PDF 职称材料

重图边着色的两个新结果

18

作者 刘焕平 杨义先 《北京邮电大学学报》 EI CAS CSCD 1996年第4期71-74,共4页

利用Ｈ．Ｐ．Ｙａｐ在文献［２］中给出的方法，给出了关于重图边着色的两个新结果。

关键词 图 边着色 边色数

下载PDF 职称材料

独立数、连通度及r－消去图

19

作者 吴强 《山东工业大学学报》 1995年第2期176-181,共6页

改进了关于ｒ－因子的结果，给出了一个图是ｒ－消去图的充分条件．并且用例子说明此结果是最好的可能．结果如下：定理Ⅰ设ｒ≥１是奇数，Ｇ是一简单图，且Ｖ（Ｇ）为偶数，如果ｋ（Ｇ）＞（ｒ＋１）２／２，且（ｒ＋１）２α（Ｇ）＜... 改进了关于ｒ－因子的结果，给出了一个图是ｒ－消去图的充分条件．并且用例子说明此结果是最好的可能．结果如下：定理Ⅰ设ｒ≥１是奇数，Ｇ是一简单图，且Ｖ（Ｇ）为偶数，如果ｋ（Ｇ）＞（ｒ＋１）２／２，且（ｒ＋１）２α（Ｇ）＜４ｒｘ（Ｇ），那么Ｇ为ｒ－消去图．定理Ⅱ设ｒ≥２为偶数，Ｇ是一简单图，如果ｋ（Ｇ）＞ｒ（＋２）／２，且（ｒ＋２）ａ（Ｇ）＜４ｋ（Ｇ），则Ｇ为ｒ－消去图． 展开更多

关键词 r消去图 图论 独立数 连通度

下载PDF 职称材料

区间图中连续1性质的试验

20

作者 钱建平 《南京理工大学学报》 EI CAS CSCD 2000年第5期433-436,共4页

在VLSI设计中 ,栅极矩阵法需用到区间图 ,区间图具有连续 1的性质。该文提出区间图中连续 1性质试验的一种算法 ,它从AAT 开始 ,建立在行向量的内积关系上 ,逐步确定行的次序 ,最终判断出连续 1的性质。它同Fulkerson算法相比 ,适用性... 在VLSI设计中 ,栅极矩阵法需用到区间图 ,区间图具有连续 1的性质。该文提出区间图中连续 1性质试验的一种算法 ,它从AAT 开始 ,建立在行向量的内积关系上 ,逐步确定行的次序 ,最终判断出连续 1的性质。它同Fulkerson算法相比 ,适用性和实用性更强 。 展开更多

关键词 超大规模集成电路 矩阵 区间图 栅极矩阵法 连续1性质

下载PDF 职称材料