检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

k边诱导子图问题的参数复杂性

k边诱导子图问题的参数复杂性

作者：林冰凯上海交通大学

学位级别：硕士

本文为k-边诱导子图问题提供了一个固定参数算法，从而解决了由蔡雷振提出的一个公开问题。更具体地说，我们证明，对于任意给定的k，我们能设计出一个算法，使得在线性时间内判断一个图G是否含有k边诱导子图。我们的算法基于一些二分... 详细信息

本文为k-边诱导子图问题提供了一个固定参数算法，从而解决了由蔡雷振提出的一个公开问题。更具体地说，我们证明，对于任意给定的k，我们能设计出一个算法，使得在线性时间内判断一个图G是否含有k边诱导子图。我们的算法基于一些二分图上的Ramesey类型的结果，高斯的Eureka定理[1]以及一个算法元定理。另一方面，我们还证明了k边诱导子图在简单图上是NP完全的，而且在包含多重边的图上是W[1]难的。

关键词：参数复杂性诱导子图算法拉姆塞定理

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

交换环Zn上的零除数图的Gutman指数

山西大学学报(自然科学版) 2024年第2期47卷 295-301页

作者：苗红丽梅银珍中北大学数学学院

交换环上的零除数图是一个无向的简单连通图，其顶点集为环上的零因子的集合。基于度与距离的Gutman指数，本文主要采用分类讨论的方法，首先对环上的零除数图进行顶点划分，其次对零除数图的诱导子图上的度与距离及相互之间的连接关系... 详细信息

交换环上的零除数图是一个无向的简单连通图，其顶点集为环上的零因子的集合。基于度与距离的Gutman指数，本文主要采用分类讨论的方法，首先对环上的零除数图进行顶点划分，其次对零除数图的诱导子图上的度与距离及相互之间的连接关系进行讨论，从而刻画出了某些情况下的零除数图的Gutman指数。

关键词： Gutman指数交换环零除数图诱导子图

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

均衡路径覆盖和连通子图划分问题

均衡路径覆盖和连通子图划分问题

作者：姚会影杭州电子科技大学

学位级别：硕士

本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容... 详细信息

本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容如下。第一章介绍了图论、计算复杂性和近似算法的一些基础知识,并阐述了{1,2}-边赋权完全图上最小最大k-路径（圈）覆盖问题和连通图上的均衡k-连通划分问题的研究现状。第二章研究了{1,2}-边赋权完全图上最小最大k-路径覆盖与k-圈覆盖问题。利用经典NP-哈密顿路问题和哈密顿圈问题进行多项式时间归约,证明了两个问题均是NP-难的。对最小最大2-路径覆盖问题,基于旅行售货商问题的一个近似算法,提出了一个近似比不超过11/7的算法,并给出了一个算例;然后将此算法推广到了一般最小最大k-路径覆盖问题,证明了算法的近似比不超过24/7-2/k。对于最小最大k-圈覆盖问题,基于上述最小最大k-路径覆盖问题算法,得到了一个近似比不超过19/7-1/k的算法。第三章研究了2-连通图上的均衡2-连通划分问题,基于局部搜索技术,提出了一个近似比不超过6/5的算法。第四章对全文的内容进行了总结,并对未来的研究方向给出了相关分析和展望。

关键词：路径覆盖圈覆盖图划分诱导子图 2-连通近似算法 NP-难

广义线图与{C41,K1,31,K1,4}-free图的符号差

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

高校应用数学学报（A辑） 2019年第4期34卷 492-500页

作者：赵志敏何常香徐光辉上海理工大学理学院上海200093 浙江农林大学理学院浙江杭州311300

图的邻接矩阵的正,负特征值个数分别被称为图的正,负惯性指数.图G的正惯性指数与负惯性指数之差被称为图G的符号差,记作s(G). 2013年马海成等人提出符号差猜想:对于任意简单图G,都有-c3(G)≤s(G)≤c5(G),其中ci(G)(i∈{3, 5})分别表示G... 详细信息

图的邻接矩阵的正,负特征值个数分别被称为图的正,负惯性指数.图G的正惯性指数与负惯性指数之差被称为图G的符号差,记作s(G). 2013年马海成等人提出符号差猜想:对于任意简单图G,都有-c3(G)≤s(G)≤c5(G),其中ci(G)(i∈{3, 5})分别表示G中长为模4余3和模4余1的圈的个数.此文证明了广义线图和不含C41, K1,31,K1,4之一作为诱导子图的图满足此猜想.

关键词：符号差广义线图诱导子图惯性指数

广义Brandt半群的另一类Cayley图

在线全文

学校读者我要写书评

暂无评论

福州大学学报（自然科学版） 2021年第4期49卷 441-446页

作者：李映辉王守峰昆明学院教师教育学院云南昆明650204 云南师范大学数学学院云南昆明650500

研究广义Brandt半群上的以Green等价类为连接集的Cayley图.通过扩大连接集和改变诱导子图得到不同类型的Cayley图,并刻画这些Cayley图的特征,讨论其同构的条件,揭示了广义Brandt半群的Cayley图本质特征.

关键词： Cayley图广义Brandt半群 Green等价类诱导子图

在线全文

学校读者我要写书评

暂无评论

关于圈对完全图的多色Ramsey数

郑州大学学报（理学版） 2014年第1期46卷 47-48页

作者：刘大瑾白路锋南京理工大学泰州科技学院江苏泰州225300

证明了关于k个偶圈对完全图的多色Ramsey数的上界。

关键词：完全图诱导子图 Ramsey数

在线全文

学校读者我要写书评

暂无评论

图的第二个最小特征值的界

华东师范大学学报（自然科学版） 1993年第4期 24-28页

作者：徐光辉华东师范大学数学系

设G是n个顶点的简单图,λ(n_1)(G)为G的第二个最小特征值。G的非孤立点形成的图记为G_1,V((G_1)=s,(э≤s≤n)。本文主要证明了:a.若G_1不是完全偶图,则λ_(n-1)(G)≤λ_(s-1)(K_(2,s-2—e)),等式成立G_1≌K_(2,s-2)—e。其中图K_(2,s... 详细信息

关键词：偶图特征值诱导子图图论

在线全文

学校读者我要写书评

暂无评论

图的距离拉普拉斯谱与距离无符号拉普拉斯谱

图的距离拉普拉斯谱与距离无符号拉普拉斯谱

作者：周成东南大学

学位级别：硕士

在研究图的性质时,人们引入各种与图结构相对应的矩阵,如关联矩阵、邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵、距离矩阵等.用线性代数及矩阵论的方法研究这些矩阵,所得结果能够帮助我们进一步了解图的结构和性质。2013年,Aouchiche... 详细信息

在研究图的性质时,人们引入各种与图结构相对应的矩阵,如关联矩阵、邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵、距离矩阵等.用线性代数及矩阵论的方法研究这些矩阵,所得结果能够帮助我们进一步了解图的结构和性质。2013年,Aouchiche和Hansen受拉普拉斯矩阵和无符号拉普拉斯矩阵的启发,提出了图的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵的概念,并在后续的研究中提出了一些具有挑战性的猜想.相较邻接矩阵而言,拉普拉斯矩阵和无符号拉普拉斯矩阵对角线元素直接反应了图各个顶点的度大小.同样地,对距离矩阵而言,距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵对角线元素还直接反应了图的各个顶点到其他所有顶点的距离和.本文针对图的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵,研究不同图类下的谱半径的性质.主要内容分为两大部分.第一部分研究图的距离拉普拉斯谱半径.首先,本文解决了Aouchiche和Hansen提出的一个关于图的距离拉普拉斯矩阵的最大特征值(等于谱半径)重数的猜想.其次,研究了一类具有诱导子图为树的图,得到了距离拉普拉斯谱半径在修改该诱导子图为若干悬挂点后必定不增的结论.然后,深入研究一类直径为偶数的树的距离拉普拉斯矩阵最大特征值及其对应的特征向量的性质.在顶点数一定情况下,给出了距离拉普拉斯谱半径最小的直径为偶数的树的刻画.最后,研究了一类单圈图不同围长下的距离拉普拉斯谱半径的大小关系.第二部分研究图的距离无符号拉普拉斯谱半径.先研究了一类具有诱导子图为树的图,得到了距离无符号拉普拉斯谱半径在修改该诱导子图为若干悬挂点后必定不增的结论.再深入讨论一类单圈图的距离拉普拉斯矩阵最大特征值及其对应的特征向量的性质.最后,在顶点数一定的情况下,给出了距离无符号拉普拉斯谱半径最小的直径为偶数的树的刻画.在论文的总结部分,提出了5个仍值得深入讨论的猜想.

关键词：图树直径单圈图诱导子图谱半径距离拉普拉斯距离无符号拉普拉斯

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

关于完全图的循环分解

南京大学学报(自然科学版) 1985年第3期 421-426页

作者：孙慧澄

本文给出关于将完全图分解成边相离的循环的和的几个结果。

关键词：循环置换图边正整数三元系奇素数南京大学学报诱导子图拉丁方构造图互异