n≤12阶(k,l)-正则极大平面图 被引量：1

1

作者 韩忠海 杨爱民 《数学的实践与认识》 CSCD 北大核心 2007年第21期100-106,共7页

我们知道当图的顶点数n>12时不存在正则极大平面图.相关文献提出了(k,l)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性.在相关文献中,作者分别讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法.本文讨论了... 我们知道当图的顶点数n>12时不存在正则极大平面图.相关文献提出了(k,l)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性.在相关文献中,作者分别讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法.本文讨论了阶n(≤12)的(k,l)-正则极大平面图的存在性,除两种情况外,本文给出了阶n(≤12)的(k,l)-正则极大平面图的存在条件及其一种构造的例子. 展开更多

关键词 极大平面图 正则 三角剖分图 (k l)-正则

原文传递

关于三角剖分图的2个结果

2

作者 李丽萍 谢秀峰 张海霞 《纺织高校基础科学学报》 CAS 2011年第4期554-556,共3页

研究了含有1个或2个分离三角形的三角剖分图.得到了仅含有1个分离三角形且至多有7个边界点的三角剖分图,有一条Hamilton路.还得到了含有2个分离三角形的极大平图,当2个分离三角形有公共边时,此极大平图是Hamilton图.

关键词 三角剖分图 分离三角形 HAMILTON图

下载PDF 职称材料

关于Pseudo-split图的一点推广

3

作者 薛清波 孙大宁 唐旭辉 《北方工业大学学报》 2000年第1期41-44,共4页

继 Ham m er和 Fo··ldes提出 split图的概念 ,并证明 split图即是 ( C4,C5 ,2 K2 ) -free图之后 ,1994年 ,Frederic Maffray和 Myriam Preissmann给出了 ( C4,2 K2 ) -free图 ( pseu-do-split graphs)的结构特点 .我们将 2 K2... 继 Ham m er和 Fo··ldes提出 split图的概念 ,并证明 split图即是 ( C4,C5 ,2 K2 ) -free图之后 ,1994年 ,Frederic Maffray和 Myriam Preissmann给出了 ( C4,2 K2 ) -free图 ( pseu-do-split graphs)的结构特点 .我们将 2 K2 -free这个条件减弱为 ( F1 ,F2 ) -free后 ,得出结论 :一个连通图是 ( C4,F1 ,F2 ) -free的 ,其最大的一个团中点的个数至少为 3 ,且不是一个三角剖分图 ( triangulated graph)的充分必要条件为 :其点集可被划分为 A,B,C3个部分 ,其中 A导出一个团 ,B导出一个独立集 ,C导出一个 Cn( n>4) ,而 A与 C之间有所有可能的线 ,B与 展开更多

关键词 完美园 连通图 Pseudo-split图 三角剖分图

下载PDF 职称材料

12阶的(4,8)-正则极大平面图的不存在性

4

作者 韩忠海 《山西农业大学学报（自然科学版）》 CAS 2008年第1期106-108,共3页

当图的顶点数n>12时,不存在正则极大平面图。S.Karimi et.al.提出了(r,k)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性。作者曾讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法,研究并讨论了阶n(n>12... 当图的顶点数n>12时,不存在正则极大平面图。S.Karimi et.al.提出了(r,k)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性。作者曾讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法,研究并讨论了阶n(n>12)的(k,l)-正则极大平面图的存在性及其构造,对于剩余的两种情况,同时提出了两个猜想。本文在此基础上又证明了其中一个猜想的正确性——不存在12阶的(4,8)-正则极大平面图。 展开更多

关键词 极大平面图 正则 三角剖分图 构造

下载PDF 职称材料

某些平面近似三角剖分图的带宽问题

5

作者 廖章钜 《北京联合大学学报》 CAS 1997年第1期40-45,共6页

Ｒ．Ｈｏｃｈｂｅｒｇ等给出了一种技巧去求任意平面图带宽的一个下界，并使用这种技巧证明了具有边长ｌ的三角剖分三角形Ｔｌ有带宽ｌ＋１，在此基础上做了以下工作：１）外界面为正六边形，其边长为ｌ的平面近似三角剖分图（记为ｌ）... Ｒ．Ｈｏｃｈｂｅｒｇ等给出了一种技巧去求任意平面图带宽的一个下界，并使用这种技巧证明了具有边长ｌ的三角剖分三角形Ｔｌ有带宽ｌ＋１，在此基础上做了以下工作：１）外界面为正六边形，其边长为ｌ的平面近似三角剖分图（记为ｌ）的带宽为２ｌ＋１；２）Ｔｌ的符合某种条件的子图（记为Ｔ（ｓ）ｌ）的带宽界为ｍ＋１≤Ｂ（Ｔ（ｓ）ｌ）≤ｍ＋２（其中ｍ为子图的最大层宽）；３）外界面为正方形，其边长为ｌ的平面近似三角剖分图（记为□ｌ）的带宽为ｌ＋１；４）满足某种条件，外界面为五边形的平面近似三角剖分图（记为ｌ，ｌ１———其中ｌ为最大层宽，ｌ－ｌ１为底宽，ｌ１≤ｌ）的带宽为ｌ＋１。 展开更多

关键词 带宽 三角剖分图 平面图 图论

下载PDF 职称材料

三角剖分图的色多项式

6

作者 鲍学文 《青海师范大学学报（自然科学版）》 1992年第1期7-11,共5页

本文给出多项式f(λ)=(λ-i)(λ-j)[λ(λ-1)…(λq)],1≤i≤j≤是 q T-多项式的一个充分必要条件,并给出f(λ)=λ(λ-1)^(n_1)(λ-2)^(n_2)…(λ-q)^(n_q)是 T-多项式的一个必要条件,其中 q≥4.n_1,n_2,…,n_q 是正整数.

关键词 三角剖分图 色多项式 色根

下载PDF 职称材料

阶n>12(k,l)-正则极大平面图

7

作者 韩忠海 《山西农业大学学报（自然科学版）》 CAS 2007年第2期209-213,共5页

在S.Karimis和Dragan Stevanovic研究的基础上,研究并得出了(k,l)-正则极大平面图存在的必要条件。并对存在的(k,l)-正则极大平面图进行了构造。不仅彻底解决了S.Karimis提出的问题,而且就是否存在对应阶n>12的(k,l)-正则极大平面图... 在S.Karimis和Dragan Stevanovic研究的基础上,研究并得出了(k,l)-正则极大平面图存在的必要条件。并对存在的(k,l)-正则极大平面图进行了构造。不仅彻底解决了S.Karimis提出的问题,而且就是否存在对应阶n>12的(k,l)-正则极大平面图研究和证明,并得出当阶n>13时仅存在(3,6)、(4,6)、(5,6)-正则极大平面图,同时给出了对应的(k,l)-正则极大平面图的一种构造方法。 展开更多

关键词 极大平面图 正则 三角剖分图 构造

下载PDF 职称材料

在闭曲面上生成最小度为4的三角剖分图

8

作者 艾山江.吾素音 阿力木江.艾则孜 《新疆师范大学学报（自然科学版）》 2010年第2期56-58,共3页

证明在面(除了球面)上的最小度至少为4的任意三角剖分图是对不可约的三角剖分图做两种局部的形变(4-分割和八面体加法)而得到的,球面上的任意三角剖分图对八面体做上述两种形变得到的。

关键词 三角剖分图 4-分割序列 八面体加法

下载PDF 职称材料

三角剖分图的点面全色数

9

作者 王维凡 《辽宁大学学报（自然科学版）》 CAS 1993年第2期1-6,共6页

平面图G(V,E,F)的点面全色数X_e(G)是使得集合V(G)∪F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文证明了:若G是三角剖分图,则4≤X_e(G)≤6。

关键词 三角剖分图 染色 点面全色数

下载PDF 职称材料

无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法 被引量：9

10

作者 薛亮 陈晰 +2 位作者 赵继军 黎作鹏 关新平 《自动化学报》 EI CSCD 北大核心 2016年第10期1570-1584,共15页

为同时满足覆盖与节能应用需求,本文提出了无线传感器网络中一种最小刚性拓扑控制算法MRTc(Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation).该算法基于Voronoi覆盖机制,准确控制节... 为同时满足覆盖与节能应用需求,本文提出了无线传感器网络中一种最小刚性拓扑控制算法MRTc(Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation).该算法基于Voronoi覆盖机制,准确控制节点工作状态,实现活动节点对目标区域的完全覆盖.在此基础上,MRTc利用Delaunay三角剖分图的特点,构建出适用于无线传感器网络的最小刚性拓扑结构.该结构有效约束了网络平均节点度,且同时具有容错性、覆盖性和稀疏性.此外,MRTc引入节点功率控制策略,在维持网络完全覆盖的基础上最小化节点能耗.仿真结果进一步验证了本文提出的MRTc算法的有效性. 展开更多

关键词 无线传感器网络 拓扑控制 最小刚性 Voronoi覆盖 Delaunay三角剖分图

下载PDF 职称材料

近三角剖分图的最大亏格与1-因子 被引量：3

11

作者 吕长青 任韩 《华东师范大学学报（自然科学版）》 CAS CSCD 北大核心 2006年第5期66-71,共6页

考察了平面近三角剖分图的最大亏格与独立边集之间的关系．设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2φ]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-11,这里φ和β(G)分别表示图G在平面上嵌入的面数与G的Be... 考察了平面近三角剖分图的最大亏格与独立边集之间的关系．设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2φ]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-11,这里φ和β(G)分别表示图G在平面上嵌入的面数与G的Betti数．特别地,如果φ=0 mod 2,即G有1-因子,则G是上可嵌入的．作为应用．证明了几个已知的结果． 展开更多

关键词 最大亏格 上可嵌入 1-因子 BETTI数 近三角剖分图

下载PDF 职称材料

非极大部分对偶平面图的刻画与平面三角剖分图的部分对偶最大亏格

12

作者 秦楚 陈仪朝 《数学学报（中文版）》 CSCD 北大核心 2024年第3期531-538,共8页

图嵌入G的部分对偶G^(A)是选择G的部分边集A做对偶,它是经典的庞加莱对偶G^(*)的推广.与经典的庞加莱对偶不同的是,部分对偶G^(A)的亏格往往不等于G的亏格.类似于黄-刘图的非上可嵌入性刻画定理,对平面图我们先证明了非极大部分对偶平... 图嵌入G的部分对偶G^(A)是选择G的部分边集A做对偶,它是经典的庞加莱对偶G^(*)的推广.与经典的庞加莱对偶不同的是,部分对偶G^(A)的亏格往往不等于G的亏格.类似于黄-刘图的非上可嵌入性刻画定理,对平面图我们先证明了非极大部分对偶平面图结构定理,并由此确定了平面三角剖分图G的部分对偶最大亏格,即当G为3-圈时,G的部分对偶最大亏格为1;否则G的部分对偶最大亏格为其顶点数减1. 展开更多

关键词 部分对偶 极大部分对偶平面图 平面三角剖分图 部分对偶最大亏格

原文传递

关于两类平面图及相关图的L(2,1)-标号问题 被引量：2

13

作者 邵振东 刘家壮 《山东大学学报（理学版）》 CAS CSCD 北大核心 2003年第1期37-40,共4页

图G的L( 2 ,1) 标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1,则 |f(x) -f(y) | 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) | 1 图G的L( 2 ,1)标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L( 2 ,1)标号中的最小数k Gri... 图G的L( 2 ,1) 标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1,则 |f(x) -f(y) | 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) | 1 图G的L( 2 ,1)标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L( 2 ,1)标号中的最小数k Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) Δ2 证明了对平面三角剖分图、立体四面体剖分图、平面近四边形剖分图 。 展开更多

关键词 L(2 1)标号 T-染色 平面三角剖分图 立体四面体剖分图 平面近四边形剖分图

下载PDF 职称材料

关于图的L(d,1)-标号问题

14

作者 邵振东 刘家壮 《高校应用数学学报（A辑）》 CSCD 北大核心 2004年第B12期561-566,共6页

图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则f(x)-f(y)≥2;若d(x,y)=2,则f(x)-f(y)≥1.图G的L(2,1)-标号数λ(G)是使得G有maxf(v)v∈V(G)=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为Δ的... 图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则f(x)-f(y)≥2;若d(x,y)=2,则f(x)-f(y)≥1.图G的L(2,1)-标号数λ(G)是使得G有maxf(v)v∈V(G)=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为Δ的一般图G,有λ(G)≤Δ2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立. 展开更多

关键词 L(2 1)-标号 T-染色 平面三角剖分图 立体四面体剖分图 平面近四边形剖分图

下载PDF 职称材料

至多n- 2圈二重覆盖的近三角剖分图(英文) 被引量：1

15

作者 刘同印 刘彦佩 《北方交通大学学报》 EI CSCD 北大核心 2000年第2期65-67,72,共4页

令G =(V ,E)为一具有n个节点的 2 -连通近三角剖分图 ,C为G的一个小圈二重覆盖 .本文讨论 |C|≤n -

关键词 圈二重覆盖 小圈二重覆盖 近三角剖分图 连通图

下载PDF 职称材料

少圈二重覆盖平面近三角剖分图的生成元(英文) 被引量：1

16

作者 刘同印 刘彦佩 《运筹学学报》 CSCD 1999年第4期11-16,共6页

令Ｇ为一具有ｎ个节点的平面近三角剖分图，Ｃ为Ｇ的一个少圈二重覆盖（ＳＣＤＣ）．本文首先给出了Ｇ的一些生成元，由此可以得到Ｇ的一个ＳＣＤＣ．若Ｇ为一外平面近三角剖分图，得到 ｜Ｃ｜≤ｎ－２的一充分必要条件；若 Ｇ至少有一... 令Ｇ为一具有ｎ个节点的平面近三角剖分图，Ｃ为Ｇ的一个少圈二重覆盖（ＳＣＤＣ）．本文首先给出了Ｇ的一些生成元，由此可以得到Ｇ的一个ＳＣＤＣ．若Ｇ为一外平面近三角剖分图，得到 ｜Ｃ｜≤ｎ－２的一充分必要条件；若 Ｇ至少有一个内点，得到｜Ｃ｜≤ｎ－２的一充分条件． 展开更多

关键词 次形 少圈二重覆盖 近三角剖分图 生成元 平面图

下载PDF 职称材料

几乎三角剖分图中的2-连通支撑子图

17

作者 欧阳克毅 《海南大学学报（自然科学版）》 CAS 1998年第1期8-14,共7页

证明了每一个无可分离三角形的几乎三角剖分图均存在一个２－连通支撑子图，其最大度至多３．并且，这一结果是最佳可能的。

关键词 支撑子图 可分离三角形 连通图 几乎三角剖分图

下载PDF 职称材料

三正则平面图与平面三角剖分图

18

作者 陈婵 《杭州师范大学学报（自然科学版）》 CAS 2001年第1期4-5,共2页

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图

关键词 平面三角剖分图 对偶图 HAM ilton圈

下载PDF 职称材料

简单平面三角剖分图中各生成两部子图的最大次

19

作者 陈燕 《南京师大学报（自然科学版）》 CAS CSCD 2000年第2期21-24,共4页

讨论了简单平面三角剖分图中各生成两部子图的最大次的取值范围 ,否定了郁星星提出的生成两部子图最大次的上界为常数的猜想 ,并且得到下面的主要结果 .(1)设 G是简单平面三角剖分图 .当 n=3时 ,α0 (G) =1;当 n=4时 ,α0 (G) =α1(G) =... 讨论了简单平面三角剖分图中各生成两部子图的最大次的取值范围 ,否定了郁星星提出的生成两部子图最大次的上界为常数的猜想 ,并且得到下面的主要结果 .(1)设 G是简单平面三角剖分图 .当 n=3时 ,α0 (G) =1;当 n=4时 ,α0 (G) =α1(G) =α2 (G) =1;当 n≥ 5时 ,有 2≤ α0 (G)≤ α1(G)≤ α2 (G)≤ [Δ(G) /2 ],且下界 α0 (G) =2能达到 .(2 )若 l是不小于 3的整数 .则 (a)存在简单平面三角剖分图 G0 ,使得 α0 (G0 ) =l;(b)存在简单平面三角剖分图 G1,使得 α1(G1) =l. 展开更多

关键词 简单平面三角剖分图 两部图 生成子图 最大次

下载PDF 职称材料

关于一个猜想的简单证明

20

作者 苗莲英 陈东灵 逄世友 《山东矿业学院学报》 CAS 1998年第1期89-91,共3页

图Ｇ的一个（正常）路着色是一映射φ：Ｖ（Ｇ）→Ｃ，使得Ｃ中任一元素的原象的导出子图是路的不交并，使Ｇ有正常路着色所需要的Ｃ的最小基数｜Ｃ｜，称为Ｇ的路色数，用ｘ（Ｇ；Ｐ∞）表示。Ｊ．Ａｋｉｙａｍａ和Ｅｒａ［３］提出如... 图Ｇ的一个（正常）路着色是一映射φ：Ｖ（Ｇ）→Ｃ，使得Ｃ中任一元素的原象的导出子图是路的不交并，使Ｇ有正常路着色所需要的Ｃ的最小基数｜Ｃ｜，称为Ｇ的路色数，用ｘ（Ｇ；Ｐ∞）表示。Ｊ．Ａｋｉｙａｍａ和Ｅｒａ［３］提出如下问题：是否存在平面图Ｇ使得ｘ（Ｇ；Ｐ∞）＝４？关于这一问题，已有人证明［３，５］；对于任意平面图Ｇ，都有ｘ（Ｇ；Ｐ∞）≤３。 展开更多

关键词 平面图 路色数 平面三角剖分图 猜想 证明

下载PDF 职称材料