检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的最大度、独立数与谱半径

图的最大度、独立数与谱半径

作者：杜雪北京交通大学

学位级别：硕士

图的谱半径是指图的邻接矩阵的最大特征值.研究图的谱半径与图的结构之间的关系是一个重要的研究方向.本文主要研究给定某些参数的图类中具有最小谱半径的图的结构.本文分三章.第一章介绍了相关的研究背景和基本概念,第二章刻画了阶数... 详细信息

图的谱半径是指图的邻接矩阵的最大特征值.研究图的谱半径与图的结构之间的关系是一个重要的研究方向.本文主要研究给定某些参数的图类中具有最小谱半径的图的结构.本文分三章.第一章介绍了相关的研究背景和基本概念,第二章刻画了阶数充分大、最大度等于3、最大度点的个数大于等于3的树中具有最小谱半径的图的结构和最大度大于等于4、最大度点的个数小于等于3的树中具有最小谱半径的图的结构.第三章刻画了独立数是3、阶数n=3k(k≥15)的连通图中具有最小谱半径的图和独立数是4、阶数n=4k(k≥26)的连通图中具有最小谱半径的图.

关键词：图最大度独立数谱半径

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

点传递图在张量积下的独立数

点传递图在张量积下的独立数

作者：毛惠群浙江师范大学

学位级别：硕士

组合数学是数学的一个重要分支,极值组合问题是组合学研究的一类非常重要的问题.1928年,Sperner提出的Sperner定理拉开了Sperner理论的序幕.由于Sperner理论应用广泛,因此吸引了许多学者对其进行研究,并得到迅速发展,最终发展成为一个... 详细信息

组合数学是数学的一个重要分支,极值组合问题是组合学研究的一类非常重要的问题.1928年,Sperner提出的Sperner定理拉开了Sperner理论的序幕.由于Sperner理论应用广泛,因此吸引了许多学者对其进行研究,并得到迅速发展,最终发展成为一个系统的理论.其中由Erd?os-Ko-Rado在1961年发表的著名定理EKR定理是Sperner定理的一个推广.EKR定理是极值组合理论中的一个核心定理,也是极值组合理论中一个经典结论.它主要研究的是集合交的性质,并且是有限交族的一个最早结果.随着学者几十年的研究,EKR定理已具有各种形式的推广.然而EKR性质在分拆格、线性格等方面交族的性质还有许多问题没有得到解决.因此,EKR性质还存在很大的研究空间.本文继续研究EKR性质的推广,主要研究EKR性质在张量积上的推广.本文第一章节,我们首先介绍了EKR定理的来源,并对其在各方面的推广作了一个简述.然后重点介绍了本文所要用到的符号、术语以及EKR定理在直积和张量积下的推广.最后给出本文的主要结果.在第二章节,我们主要介绍要用到的方法,重点给出对任意两个点传递图和一个圈图在张量积下的独立数的证明,并刻画了其最大独立结构.在第三章节,我们主要证明了任意两个点传递图和一个Kneser图在张量积下的独立数,并刻画了其最大独立结构.

关键词：直积张量积本原性独立数点传递图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

4正则无爪图的团横贯数和独立数

4正则无爪图的团横贯数和独立数

作者：许粉铃新疆大学

学位级别：硕士

设G=(V,E)是一个简单图,C是G的一个至少有两个顶点的子图,如果C是一个极大的完全子图,则称C是图G的一个团.设D是图G的一个顶点子集,如果对于G的任意一个团C,D∩C?=?,则称D是图G的一个团横贯集.基数最小的团横贯集称为最小团横贯集,最小... 详细信息

设G=(V,E)是一个简单图,C是G的一个至少有两个顶点的子图,如果C是一个极大的完全子图,则称C是图G的一个团.设D是图G的一个顶点子集,如果对于G的任意一个团C,D∩C?=?,则称D是图G的一个团横贯集.基数最小的团横贯集称为最小团横贯集,最小团横贯集的基数称为最小团横贯数,用τc(G)表示.设I是图G的一个顶点子集,如果对于任意的u,v∈I,uv/∈E,则称I是图G的一个独立集.基数最大的独立集称为最大独立集,最大独立集的基数称为独立数,用α(G)表示.顶点v∈V(G)的开邻集定义为v在G中所有邻点的集合,记为N(v).设H是一个简单图,如果图G中任意顶点的开邻集都同构于H,则称G是H邻域图.例如2K2邻域图每个顶点的开邻集导出的子图都同构于***等2014年已经证明了对于2连通且不含K4的4正则n阶无爪图τc(G)=?n/3?成立,并且猜想所有的不含K4的4正则n阶无爪图的团横贯数τc(G)≤(10n+3)/27.另外,Kang等2013年证明了2连通且不含K4的4正则n阶无爪图的独立数α(G)=?n/3?.进一步,他们也猜想所有的不含K4的4正则n阶无爪图的独立数α(G)≥(8n-3)/27.本文对上述Wang等和Kang等的定理分别给出了简洁的证明,并且解决了上述两个猜想.此外,我们对2K2邻域图G的团横贯数给了一个更好的上界(13n+3)/36,并对P4邻域图和C4邻域图分别给了一个刻画.

关键词：团团横贯数独立数无爪图 4正则图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

符号独立数与符号星独立数

符号独立数与符号星独立数

作者：张午骁安庆师范大学

学位级别：硕士

独立性是一个经典的概念,各种独立数是现在国内外图论研究的一个重点课题.在1998年,美国图论学者Haynes等出版了专著《Domination in Graphs》和《Fundamentals of Domination in Graphs》,较为系统的综述了一些主要研究成果[7,8].图的... 详细信息

独立性是一个经典的概念,各种独立数是现在国内外图论研究的一个重点课题.在1998年,美国图论学者Haynes等出版了专著《Domination in Graphs》和《Fundamentals of Domination in Graphs》,较为系统的综述了一些主要研究成果[7,8].图的独立数,是一重要理论问题,且有许多应用,因此研究它有其实际的和理论的意义.研究并确定各类图的独立(点,边,全)数是图论一个重要方向,然而值得注意的是,大多数概念都是先对图的点独立而言,对图的边独立问题还有许多要做的工作,所以边独立相关的研究就显得有价值.本文主要讨论符号独立数和符号星独立数两个部分.对于符号独立数简单的介绍了概念,并给出了一些特殊图和一般图的界.其后我们定义了一个新的参数符号星独立数,并给出了它的界.

关键词：独立数符号独立数符号星独立函数符号星独立数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

超线图的路，圈和独立数

超线图的路，圈和独立数

作者：李霞兰州大学

学位级别：硕士

对正整数r，图G的指标为r的超线图L(G)是这样定义的：L(G)的顶点集由E(G)的所有r元子集构成，E(G)的两个不同r元子集S和T在L(G)中邻接当且仅当G存在相邻接的边s∈S和t∈***，Beineke和Varma证明了如果连通图G至少有两条边，则L(G)是泛... 详细信息

对正整数r，图G的指标为r的超线图L(G)是这样定义的：L(G)的顶点集由E(G)的所有r元子集构成，E(G)的两个不同r元子集S和T在L(G)中邻接当且仅当G存在相邻接的边s∈S和t∈***，Beineke和Varma证明了如果连通图G至少有两条边，则L(G)是泛圈的。后来他们还进一步得到如果图G没有孤立边，L(G)是点泛圈的。一个有n个顶点的连通图被称为路稠的如果它的任意一对顶点都能被长度为2，3，…，n-1的路连接。在本文中，我们得到如果图G没有孤立边，则L(G)是路稠的。Bagga等提出：如果一个图G恰有一条孤立边，那么L(G)是否还具有点泛圈性。本文通过证明如果图G至多含有一条孤立边，那么L(G)是点泛圈的，肯定地回答了这个问题。最后，本文讨论了超线图的独立数。

关键词：超线图路稠点泛圈边泛圈独立数边独立数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的独立数与平均度的和

图的独立数与平均度的和

作者：杨旭暖新疆大学

学位级别：硕士

2008年,Aouchiche,Brinkmann和Hansen在文献中提出了一个关于”图的独立数与平均度之和的下界”的猜想.本文中,我们不仅证明了此猜想是正确的,并且论证了其对于任意的连通图都是成立的. 本文内容分为两章,第一章是引言部分.介绍了... 详细信息

2008年,Aouchiche,Brinkmann和Hansen在文献中提出了一个关于”图的独立数与平均度之和的下界”的猜想.本文中,我们不仅证明了此猜想是正确的,并且论证了其对于任意的连通图都是成立的. 本文内容分为两章,第一章是引言部分.介绍了文章的基本概念、背景和证明的主要结果. 第二章是定理的证明部分,分为两节.第一节介绍了本文用到的定理及推论;第二节是定理的详细证明过程.

关键词：独立数平均度连通图

图的独立数、连通度与Hamilton连通性

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的独立数、连通度与Hamilton连通性

作者：张秀玲华中师范大学

学位级别：硕士

Chvatal-Erdos定理证明了下述结论：设G为n阶图且n≥3。如果κ（G）≥α（G），则G是hamilton图;如果κ（G）>α（G），则G是Hamilton连通图。Jacobson等人通过改变Chvatal-Erdos定理的连通度和独立数，增加图的最小度条件得到了下面定... 详细信息

Chvatal-Erdos定理证明了下述结论：设G为n阶图且n≥3。如果κ（G）≥α（G），则G是hamilton图;如果κ（G）>α（G），则G是Hamilton连通图。Jacobson等人通过改变Chvatal-Erdos定理的连通度和独立数，增加图的最小度条件得到了下面定理：（i）设G为n阶图，n足够大，k≥3为正整数。如果κ（G）≥4k+1，δ（G）>（n+k-2k）/k，且δ（G）≥α（G）+k-2，则G是Hamilton连通图;（ii）设G为n阶图，n足够大，k=3或4。如果κ（G）≥k，δ（G）>（n+k-2k）/k，且有δ（G）≥α（G）+k-2，则G是Hamilton连通图。在本文中，我们将证明以下结论：设G为n阶图且n足够大，k=5，如果κ（G）≥k，δ（G）>（n+k-2k）/k，且有δ（G）≥α（G）+k-2，则G是Hamilton连通图。

关键词：独立数连通度 Hamilton连通图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

重要图类的独立数研究

重要图类的独立数研究

作者：张述平中国地质大学(北京)

学位级别：硕士

图论中,图的独立数为图论中重要的图参数。独立数研究在预测新化合物、合成新药品方面有很重要的应用。本文主要研究了两种特殊图类的独立数问题,分别为梯形图和凸多面体图。其中在梯形中我们主要研究了广义梯形图,Mobius梯形图和循环... 详细信息

图论中,图的独立数为图论中重要的图参数。独立数研究在预测新化合物、合成新药品方面有很重要的应用。本文主要研究了两种特殊图类的独立数问题,分别为梯形图和凸多面体图。其中在梯形中我们主要研究了广义梯形图,Mobius梯形图和循环梯形图。对于凸多面体图,我们主要研究了凸多面体图类An,Qn,Rn。在本文中,我们还给出了求解图类独立数问题的一般算法。对于梯形图,得到广义梯形图,Mobius梯形图和循环梯形图的独立数的精确值,并得到了三种图形独立集的总和NI的精确计算公式,并运用转换矩阵的思想设置程序验证结果。对于凸多面体图,我们主要研究了三种凸多面体图类,分别为An,Rn和Qn。我们求出来三种图类的独立数,并且求出凸多面体图类An的独立集总和NI的精确计算公式。因为凸多面体图类Rn和Qn结构较为复杂和一般化,我们很难求出NI的精确计算公式,所以我们给出它们的上界或者下界。对于任意图,我们给出了一般算法。可以计算任意图的NI问题。利用二部图和左部图对其进行验证。选出两个特殊图,如:K5,4,3,2和K5,4,3,2,4。得到NI(K5,4,3,2)=319,NI(K5,4,3,2,4)=757。与利用一般性公式算出的结果完全一致。但一般算法的应用仍然具有一定的局限性,如,将图转换为矩阵的形式。相信随着计算机网络的飞速发展,这一问题将不再是问题,极大推动重要图类独立数问题的研究。

关键词：独立数梯形图凸多面体图 NI值独立集

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

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

山东工业大学学报 1995年第2期25卷 176-181页

作者：吴强山东工业大学数理系

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

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

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