检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

平面图补图中的轮

平面图补图中的轮

作者：吕常委南京大学

学位级别：硕士

本文主要研究了几类平面图补图中含有轮的平面Ramsey数.平面Ramsey数的定义是经典Ramsey数定义在平面图上的限制,对给定的两个图F和H,平面Ramsey数PR(F,H)是确定如下条件的最小的正整数N,任一N阶平面图G,或者G包含子图F,或者G的补图包... 详细信息

本文主要研究了几类平面图补图中含有轮的平面Ramsey数.平面Ramsey数的定义是经典Ramsey数定义在平面图上的限制,对给定的两个图F和H,平面Ramsey数PR(F,H)是确定如下条件的最小的正整数N,任一N阶平面图G,或者G包含子图F,或者G的补图包含子图H.目前关于平面图补图含有轮的平面Ramsey数结果还很少,Zhou[20]等人证明了如下结果随后Zhou等人又确定了尸R(C4,Wn)的值.本文主要研究了完全图Km(m1≥5)和星Sk对轮Wn的半面Ramsey数.第一章主要介绍了平面Ramsey数的发展历程和最新进展,并介绍了图论的基本概念和本文用到的符号.第二章确定了完全图Km(m≥5)和星Sk这两类图对轮Wn的平面Ramsey数.

关键词：平面Ramsey数轮完全图星

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

含点不交偶圈的图的[r,s,t]-着色

天津师范大学学报（自然科学版） 2010年第2期30卷 18-22页

作者：俞竺君左连翠天津师范大学数学科学学院天津300387

通过用图G的导出星K1,Δ(G)的一个[r,s,t]-着色对图G进行从下往上着色,证明了含点不交偶圈的图的[r,s,t]-色数等于图中最大导出星的[r,s,t]-色数.

关键词： [r,s,t]-着色星偶圈

在线全文

学校读者我要写书评

暂无评论

关于一些图的Ramsey数

关于一些图的Ramsey数

作者：李群大连理工大学

学位级别：硕士

图论是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是计算机科学中有非常广泛的应用。本文主要研究某些图的Ramsey数问题。对任意两个图G和H,图的Ramsey数R(G,H)定义为最小的整数n,使得阶数为n的任意图F都包... 详细信息

图论是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是计算机科学中有非常广泛的应用。本文主要研究某些图的Ramsey数问题。对任意两个图G和H,图的Ramsey数R(G,H)定义为最小的整数n,使得阶数为n的任意图F都包含G作为子图或(?)包含H作为一个子图。本文研究了树对轮的Ramsey数。本文主要内容及结构如下: 在第一章中简要叙述了图Ramsey数的发展,介绍了图论的基本概念和术语。由于星图的特殊性,星图对其它图的Ramsey数得到了广泛的关注。在第二章中研究的是星对轮的Ramsey数。在本章中先给出并证明了关于图的Ramsey数的一些结果。然后利用文献[26]和[32]介绍并讨论了星对轮的一些结果。路径也是一类特殊的图。许多数学工作者都对关于路径或轮的Ramsey数进行了研究。在第三章我们研究的是路径对轮的Ramsey数。Faudree等人考虑了所有路径对圈的Ramsey数。Surahmat et al得到了路径对W或W的Ramsey数。陈耀军从更一般的情况考虑了路径对轮的Ramsey数并给出了下面的结果:R(P,W)=3n-2,对奇数m且n≥m-1≥2;R(P,W)=2n-1,对偶数m且n≥m-1≥3。因此在第二节中我们就给出了路径对轮在其他情况下的结果: (?)以及这样一个边界:若(n≥6,m为偶数且n+2≤m≤2n-4)或(n为偶数,n≥4,m=2n-2或m≥2n),则 m+[3n/2]-2≥R(P,W)≥max{[(m-1)/(n-1)](n-1)+n,m+[(m-1)/[(m-1)/(n-1)]]}。星和路径都是特殊的树,因此在第四章章中我们来研究树对轮的Ramsey数。***给出了树对W或W的Ramsey数:R(T,W)=2n-1,其中n≥4;R(T,W)=3n-2,其中n≥5。所以***猜想了下面的结果当n≥m≥7且m为奇数时,R(T,W)=3n-2。本章第二节中我们就证明了当m为奇数且m≥7时,R(T,W)=3n-2,其中n=m,m+1,m+2。

关键词： Ramsey数树星轮路径

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

几类森林的Tur(?)n数问题

几类森林的Tur(?)n数问题

作者：石恺上海交通大学

学位级别：硕士

极值图论是图论中的重要研究方向。它主要研究具有某些性质的图的极值问题。图H的Turan数ex(n,H)是指n个点的图G的最大边数,其中图G不包含H为子图。1941年,Turan确定了k-完全图的Turan数的值。1959年,Erdos及Gallai提出了路Pl的Turan数... 详细信息

极值图论是图论中的重要研究方向。它主要研究具有某些性质的图的极值问题。图H的Turan数ex(n,H)是指n个点的图G的最大边数,其中图G不包含H为子图。1941年,Turan确定了k-完全图的Turan数的值。1959年,Erdos及Gallai提出了路Pl的Turan数问题并给出了上界。2008年,Balister等人则证明了不含Pl的连通图的最大边数。2013年,Lidicky等人确定了由路构成的森林(?)Pli和由星构成的森林(?)Sdi的Turan数。Lidicky在文章最后提到了aPl ∪ bSt的问题,但未给出结论及证明。本文则将上述问题推广,研究了(?)Pli ∪(?)Sdi的极值问题,并证明了在一定条件下,该问题的Tur如数的值和极值图。结论:设a,b ≥:1,F=(?)Pli∪(?)Sdj,其中l1 1≥l2 ≥…≥la≥4,d1≥d2≥…≥:db,(?)[li/2]>d1/2。记k=(?)[li/2]+b-1,当n充分大时ex(n,F)=(2 k)+k(n-k)+cF其中当所有的li是奇数时,CF=1,否则为0。若存在一个li是偶数,那么极值图为Kk+Kn-k;若所有的li是奇数时,极值图是Kk+(K2 ∪(?)n-k2)。

关键词： Tur(?)n数极值图路星

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Cm·Sn的D(2)-点可区别边色数

数学的实践与认识 2008年第16期38卷 149-153页

作者：田京京邓方安张忠辅陕西理工学院数学系汉中723001 兰州交通大学应用数学研究所兰州730070

对阶数不小于3的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,…,α},若u,v∈V(G),1≤d(u,v)≤β,有C(u)≠C(v),则称f为G的一个α-D(β)-点可区别的边染色,简记为α-D(β)-VDPEC,对一个图进行α-D(β)-点可区别的边染色,所需的最少的... 详细信息

对阶数不小于3的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,…,α},若u,v∈V(G),1≤d(u,v)≤β,有C(u)≠C(v),则称f为G的一个α-D(β)-点可区别的边染色,简记为α-D(β)-VDPEC,对一个图进行α-D(β)-点可区别的边染色,所需的最少的颜色数称为图G的D(β)-点可区别的边色数,记为χ′β-vd(G),其中d(u,v)表示两个点u,v之间的最短距离.得到了***的D(2)-点可区别边色数.

关键词：圈星 D(β)-点可区别的边染色 D(β)-点可区别的边色数

在线全文

学校读者我要写书评

暂无评论

一些特殊种类图的[r，s，t]-着色

一些特殊种类图的[r，s，t]-着色

作者：俞竺君天津师范大学

学位级别：硕士

图G的[r,s,t]-着色是对图论经典着色的推广.令G=(V,E)是顶点集为V,边集为E的图,给定非负整数r,s和t,图G的[r,s,t]-着色是V(G)uE(G)到色集{0,1,…,k-1｝的一个函数c,满足：对于任意两个相邻的顶点vi,vj∈V,都有[c(vi)-c(uj)]≥r(称为r条... 详细信息

图G的[r,s,t]-着色是对图论经典着色的推广.令G=(V,E)是顶点集为V,边集为E的图,给定非负整数r,s和t,图G的[r,s,t]-着色是V(G)uE(G)到色集{0,1,…,k-1｝的一个函数c,满足：对于任意两个相邻的顶点vi,vj∈V,都有[c(vi)-c(uj)]≥r(称为r条件r-condition);对于任意两条相邻的边ei,ej∈E,都有[c(ei)-c(ej)]≥s(称为s-条件s-condition);对于任意一个顶点vi和与其关联的边ej,都有[c(vi)-c(ej)]≥t(称为t-条件,t-condition)图G的[r,s,t]-着色所用的最小色数k称为图G的[r,s,t]-色数,记作λr,s,t(G). 本文主要研究了树和含点不交偶圈的图的[r,s,t]-色数与它们最大导出星的[r,s,t]-色数的关系. 依据内容,本文分为五个部分：第一部分从历史的角度,主要介绍了图论的起源、发展及本文的选题背景. 第二部分主要介绍了图和点着色、边着色、全着色及其相关结论. 第三部分主要介绍了[r,s,t]-着色的基本知识、研究现状及相关引理. 第四部分研究的是树的[r,s,t]-色数.通过用树TT的导出星K1,△(T)的一个[r,s,t]-着色对树T进行点、边着色,证明了树的[r,s,t]-色数等于树中最大导出星的[r,s,t]-色数. 第五部分研究的是含点不交偶圈的图的[r,s,t]-色数.通过用图G的导出星K1,△(G)的一个[r,s,t]-着色对图G进行从下往上着色,证明了含点不交偶圈的图的[r,s,t]-小色数等于图中最大导出星的[r,s,t]-色数.

关键词： [r,s,t]-着色 [r,s,t]-色数星树点不交偶圈

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有关并图的标号结论

有关并图的标号结论

作者：高振滨哈尔滨工程大学

学位级别：硕士

自20世纪60年代Rosa引入图的标号概念以来，人们开始了对标号图的研究。随着标号图在编码理论、雷达、电路设计、通讯网络、数据基础管理等方面中的应用，人们定义了一些新的标号概念和新的图。在40年里，人们完成了千余篇关于标号图... 详细信息

自20世纪60年代Rosa引入图的标号概念以来，人们开始了对标号图的研究。随着标号图在编码理论、雷达、电路设计、通讯网络、数据基础管理等方面中的应用，人们定义了一些新的标号概念和新的图。在40年里，人们完成了千余篇关于标号图的文章;在这些文章中，有许多是关于并图的标号，在这些并图中，多是与路、圈、星等图有关。 Gnanajothi在1991年定义了图的奇优美标号。本论文的研究主要构造了一些并图的标号，对一些结论做了一定的搜集整理，在已完成的结果中，还没有关于路、星、圈并的奇优美性的结论，本文就研究了这几种图的并的奇优美标号，给出了它们存在奇优美标号的证明，研究的成果主要包括以下内容：路、星、圈的各自并的奇优美性：运用构造的方法给出了路的并图∪ P、星的并图∪ S、圈的并图C∪C的奇优美性标号，并图∪ C在m≡0(mod4)条件下的奇优美标号。路、星、圈之间并的奇优美性：通过构造方法，证明了路与星的并图(∪ S∪(∪ P)、圈与路的并图C∪P都具有奇优美标号。圈C有奇优美标号的必要条件：在本论文中，证明了圈C存在奇优美标号的必要条件。

关键词：路星圈优美图奇优美图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

排列图和数据中心网络图的结构容错性

排列图和数据中心网络图的结构容错性

作者：雷亚菲新疆大学

学位级别：硕士

点连通度是研究网络图容错性的重要参数之一.然而,图中所有故障点都是同一点的邻点的可能性很小.因此,人们提出了加上某些限制条件的连通度.设G是一个连通图,H是G的连通子图,F是G的子图的集合,其中F中的元素同构于H,称使得G-F不连通的F... 详细信息

点连通度是研究网络图容错性的重要参数之一.然而,图中所有故障点都是同一点的邻点的可能性很小.因此,人们提出了加上某些限制条件的连通度.设G是一个连通图,H是G的连通子图,F是G的子图的集合,其中F中的元素同构于H,称使得G-F不连通的F的最小基数为G的H-结构连通度,记作κ(G;H).设G是一个连通图,H是G的连通子图,F是G的子图的集合,其中F中的元素与H的连通子图同构,称使得G-F不连通的F的最小基数为G的H-子结构连通度,记作κs(G;H).结构连通度和子结构连通度是经典点连通度的推广.本文给出了(n,k)-排列图An,k的结构连通度κ(An,k;H)和子结构连通度κs(An,k;H),其中H∈{K,1m1,Pm2}(1≤m1≤n-k-1,4≤m2≤n-k);以及数据中心网络图Dk,n的结构连通度κ(Dk,n;H)和子结构连通度κs(Dk,n;H),其中H∈{K1,m,P4}(1≤m≤k).

关键词：结构连通度子结构连通度排列图数据中心网络图路星

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

S_n+W_n的邻点强可区别全色数

数学的实践与认识 2008年第18期38卷 229-232页

作者：王树勋陕西理工学院数学系陕西汉中723001

设G(V,E)是阶数不小于3的简单连通图,k是自然数,f是从V(G)∪E(G)到1,2,…,k的映射,满足:对任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);对任意的uv,uw∈E(G)(v≠w),f(uv)≠f(uw);对任意的uv∈E(G),C(u)≠C(v),其中C(u)={f(u)}∪{f(v)uv∈E(G)}∪{f(uv)uv∈E(G)},则称f是图G的一个邻点强可区别的全染色法,简记作k-AVSDTC,且称χast(G)=min{k G的所有k-AVSDTC}为G的邻点强可区别的全色数.得到了星与轮联图的邻点强可区别的全色数.

关键词：星轮联图邻点强可区别全色数