检索结果-南通市图书馆

山东大学学报（理学版） 2019年第6期54卷 71-74页

作者：熊亚萍蔡建生山东师范大学数学与统计学院山东济南250358 潍坊学院数学与信息科学学院山东潍坊261061

随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,... 详细信息

随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,E),G 的 f-染色 c 是广义的边染色,使每个颜色类在任一顶点 v 上至多出现 f( v)次,其中 f(v)是分配给 v 的正整数。给出随机图 G (n,2/1)是 f-第一类的一个充分条件。

关键词：随机图 f-染色局部引理

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

限定条件下图的f-染色的分类

引用

山东大学学报（理学版） 2017年第2期52卷 37-38,43页

作者：杨春花蔡建生潍坊学院数学与信息科学学院山东潍坊261061

研究了一类特殊的f-染色,应用一阶矩定理给出了这类f-染色的简单图是f-第一类的一个充分条件。

关键词：染色 f-染色最大度一阶矩定理

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

随机图的f-染色的分类Ⅱ

引用

数学进展 2021年第5期50卷 787-792页

作者：蔡建生熊亚萍潍坊学院数学与信息科学学院潍坊山东261061 山东师范大学数学与统计学院济南山东250358

随机图G(n,p)是具有n个标号的顶点的图,并且图中的每一对顶点以概率p被随机且独立地选择为图G的边.对于有顶点集V和边集E的简单图G=(V,E),G的f-染色c是广义的边染色,使每个颜色类在任一顶点v上至多出现f(v)次,其中f(v)是分配给v的正整数... 详细信息

随机图G(n,p)是具有n个标号的顶点的图,并且图中的每一对顶点以概率p被随机且独立地选择为图G的边.对于有顶点集V和边集E的简单图G=(V,E),G的f-染色c是广义的边染色,使每个颜色类在任一顶点v上至多出现f(v)次,其中f(v)是分配给v的正整数.在这篇文章中,我们给出随机图G(n,p)是f-第一类的一个充分条件.

关键词：随机图 f-染色 Lovász局部引理

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

图的f-染色的若干结果

图的f-染色的若干结果

引用

作者：韩丽花曲阜师范大学

学位级别：硕士

网络的拓扑结构可以用图来表示，称为网络拓扑图。可以通过研究图的性质来研究网络的结构。研究图的性质的理论就是图论，图的染色是图论的一个重要内容。一般来说，图的染色分为顶点染色和边染色，而边染色又有严格边染色和f-染色等。... 详细信息

网络的拓扑结构可以用图来表示，称为网络拓扑图。可以通过研究图的性质来研究网络的结构。研究图的性质的理论就是图论，图的染色是图论的一个重要内容。一般来说，图的染色分为顶点染色和边染色，而边染色又有严格边染色和f-染色等。图的染色具有广泛的应用，如在全光网络的波长分配问题中的应用等。本文所考虑的图都是有限简单无向图，用G来表示一个图，V(G)表示它的顶点集，E(G)表示边集，顶点v在图G中的度记为d(v)，在不至引起混淆的情况下简记为d(v)。图G的最大度记为Δ(G)，即Δ(G)=(?){d(v)}。f为定义在顶点集V(G)上的正整数函数，它给V(G)中的每个顶点v分配一个正整数f(v)。图G的一个f-染色是一个边染色，满足每个顶点v处至多有f(u)条边染相同的颜色。我们称f-染色图G所需要的最少颜色数为G的f-色数，记为χ′(G)。如果对所有的v∈V(G)都有f(v)=1成立，则f-染色问题就归结为严格边染色问题。f-染色在网络设计、计算机网络中的文件传输，时间表等问题中有很强的应用背景。例如，在一个计算机网络中，令图G的一个顶点代表一台计算机，假定传输的文件都是同等长度的，每一条边表示两个顶点之间传输的一个文件，f(v)表示顶点v对应的计算机一次可同时传输的最大文件数。若求在最短的时间内完成传输任务，这就要求对图G进行f-染色，求其所用的最少的f-色数。在严格的边染色中，一个著名的结果是Vizing于1964年给出的：对任意简单图，有χ′(G)=Δ(G)或χ′(G)=△(G)+1，其中Δ(G)表示图G的最大度。同样，在f-染色中简单图的f-色数具有类似的性质，即对任意简单图，有χ′(G)=Δ(G)或χ′(G)=Δ(G)+1，其中Δ(G)=(?){(?)}。由此，χ′(G)=Δ(G)的图被称为C 1类的，χ′(G)=Δ(G)+1的图被称为C 2类的。本文研究了图的f-染色，并得到了一些结果。共分为五章。在本论文的第一章绪论中说明了文章研究的背景及问题的提出，论文的工作及文章的组织结构;第二章介绍了图的严格边染色和f-染色若干进展;第三章讨论了图的f-染色的分类问题，证明了扇图、轮图、系列平行图、一般Petersen图、定义在圈C上的Petersen图的f-染色分类定理;第四章研究了f-染色中f-临界图的性质;第五章给出总结并展望下一步要做的工作。

关键词：图严格边染色 f-染色图的分类 f-临界图

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

几乎正则图的f-色类与gc-色类的关系

几乎正则图的f-色类与gc-色类的关系

引用

作者：张蒙恩山东师范大学

学位级别：硕士

令C是一个颜色集.图G的边染色是颜色在图G的所有边上的一个分配.令G是一个图,一个图G的正常边染色是G的边染色使得G的每个点处不能有相同的颜色.一个图G的边覆盖染色是G的边染色使得每种颜色在每个点出至少出现一次.一个图G的f-染色和g... 详细信息

令C是一个颜色集.图G的边染色是颜色在图G的所有边上的一个分配.令G是一个图,一个图G的正常边染色是G的边染色使得G的每个点处不能有相同的颜色.一个图G的边覆盖染色是G的边染色使得每种颜色在每个点出至少出现一次.一个图G的f-染色和g-染色分别是正常边染色和边覆盖染色的推广.令f和g是两个函数,在每个点v ∈ V(G)处分别分配一个正整数f(v)和一个非负整数g(v). 一个图G的f-染色是G的边染色使得每个点v ∈ V(G)处最多有f(v)条边染相同的颜色.图G的g-染色是G的边染色使得每种颜色出现在每个点v ∈ V(G)处至少有g(v)次.清晰地,图G有g-边染色当且仅当对任意点v ∈V(G)有0 ≤ g(v)≤d(v).在这篇论文中,我们总是假设对任意点∈ V(G)有0≤g(v)≤d(v).将图G进行f-染色所需要的最小的颜色数目被称为图G的f-染色数,记作X’f(G).相对地,将图G进行g-染色所需要的最大的颜色数目被称为图G的g-染色数,记作X’g(G).当f= 1时,f-染色恰好是正常边染色;当g三1时,g-染色的确是边覆盖染色.因为正常边染色问题是NP-完备的(即使是对于立方图来说),所以f-染色问题和g-染色问题也是NP-完备的.1986年Hakimi和Kariv证明:任意简单图G有X’f(G)= △f(G)或△f(G) + 1,这里△f(G) = (?).如果X’f(G)= △f(G),称G为f-染色第一类图,否则称G为f-染色第二类图.这种确定简单图的f-染色数的问题称为f-染色的分类问题.宋慧敏和刘桂真在2005年给出的一个结果表明:任意简单图G有X’g(G)=δg(G)或δg(G) - 1,这里δg(G)=(?).如果X’g(G)=δg(G),称G为g-染色第一类图,否则称G为g-染色第二类图.这种确定简单图的g-染色数的问题称为g-染色的分类问题.本论文主要研究了几乎正则图的f-染色的分类问题以及f-色类与g-色类之间的关系,张霞2015年证明了对于任意的正则图G来说,当G的f-核与g-核是相同的,并且对于Jf-核或g-核里的每个点v都有f(v)=g (v),那么在f-色类与g-色类之间总是有一致性的结果.然而,对于其它的图(甚至是几乎正则图)来说,在f-色类与g-色类之间不是总是一致的.本论文对几乎正则图,当满足f-核与g-核是相同的,并且对任意f-核或g-核里的点v有f(v)=g(v)时,给出了f-色类与g-色类之间有一致性分类结果的一些充分条件.本文分为四章进行了讨论.在第一章中,介绍了研究背景以及研究意义,给出了本文中用到的基本概念与符号,给出了几类图的f-色类与g-色类的关系的研究现状和本文关于几乎正则图研究的主要结果;在第二章中,介绍了本文要用到的预备知识,包括主要的基本工具以及主要的引理;在第三章中,讨论了几乎正则图的f-色类与g-色类的关系,先给出了几乎正则图的f-染色分类的几个结论,然后给出f-核或g-核分别在r-度点集和r + 1-度点集内f-色类与g-色类关系的结论;在第四章中,给出了本论文可进一步研究的问题.

关键词：边染色边覆盖染色 f-染色 gc-染色图的分类几乎正则图

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的几类染色问题的研究

图的几类染色问题的研究

引用

作者：熊亚萍山东师范大学

学位级别：硕士

图论是数学领域一个重要分支,其中图的染色理论在图论研究中占有重要的地位.本文旨在讨论图的几类染色问题,包括随机图的f-染色,r-一致C-超图的染色和系列平行图的弱边面染色.设G=(V(G),E(G))是一个图,其中V(G)为G的顶点集,E(G)为G的边... 详细信息

图论是数学领域一个重要分支,其中图的染色理论在图论研究中占有重要的地位.本文旨在讨论图的几类染色问题,包括随机图的f-染色,r-一致C-超图的染色和系列平行图的弱边面染色.设G=(V(G),E(G))是一个图,其中V(G)为G的顶点集,E(G)为G的边集.在V(G)上定义一个整值函数f,使得对任意的顶点v∈V(G),有f(v)>0.图G的f-染色c是一个边染色,使得每一个颜色类在任意顶点v上至多出现f(v)次.图G的f-染色所需的最少颜色数称为图G的f-色数,记为χf'(G).Hakimi和Kariv证明:对于一个简单图G,△f(G)≤χf'(G)≤△f(G)+1成立.这表明:类似于图的正常边染色,图的f-染色也可以分为两类.如果χf'(G)=△f(G),我们称图G是f-第一类的,否则称图G是f-第二类的.首先,本论文在已有的f-染色的相关结论基础之上,讨论了随机图的f-染色的分类问题.我们关注是否存在一个关于△的函数g,使得若对任意的顶点v∈V(G),f(v)=g(△),则随机图G(n,1/2)几乎肯定是f-第一类的,随后我们将上述结果推广至随机图G(n,p).最后我们得到了关于随机图f-染色的分类问题的几个结果.其次,我们讨论了r-一致C-超图染色的极值问题.混合超图H=(X,C,D)是一个三元组,其中X为H的顶点集.C为X的子集族,记作C-边.D为X的子集族,记作D-边.C=(?)的混合超图称为D-超图,D=(?)的混合超图称为C-超图.设H=(X,C,D)是一混合超图,如果满足对任意的C-边和D-边,都有|C|=r,|D|=r,其中r ≥ 2且为正整数,则称混合超图H为r-一致混合超图.特别地,若又有D=(?),则称H为r-一致C-超图.2002年,Vitaly Voloshin提出一个公开问题:当χ(H)≥k时,r-一致C-超图H的最大边数是多少?在本文中,我们得到了当χ(H)=k时,r-一致C-超图H最大边数的上界.随后,我们讨论了系列平行图的弱边面染色问题.2016年,在边面染色定义的基础上,fabrici等人提出了平面图的弱边面染色概念.在提出概念的同时,fabrici等人证明了连通、无环且无割边的平面图是弱边面6-可染的,并提出如下猜想:每个连通、无环且无割边的平面图是弱边面5-可染的.目前仅有极大平面图、外平面图以及哈林图等一些特殊平面图得以验证满足猜想.在本文中,我们得到如下结果:系列平行图G是弱边面5-可染的.本论文共分五章进行讨论.第一章,我们首先介绍了图的f-染色的分类问题、C-超图的染色问题及弱边面染色问题的背景,给出了一些基本概念和符号,介绍了相关领域的研究现状,罗列了本文的主要结论.第二章,我们主要讨论随机图的f-染色的分类问题.第三章,我们研究了r-一致C-超图的染色问题,解决了由Voloshin提出的一个公开问题.第四章,我们研究了系列平行图的弱边面染色问题,证明了fabrici等人提出的猜想对于系列平行图也是成立的.第五章,我们指出了本论文可进一步研究的问题.

关键词：随机图 f-染色 r-一致C-超图 Lovasz局部引理弱边面染色

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：