检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

字典积图的任意可分性

新疆大学学报（自然科学版中英文） 2024年第2期41卷 181-187页

作者：西日尼阿依·努尔麦麦提刘凤霞蔡华喀什大学数学与统计学院新疆喀什844000 新疆大学数学与系统科学学院新疆乌鲁木齐830017 昌吉学院数学与数据科学学院新疆昌吉831100

给定n个顶点的图G,对于满足∑_(i=1)^(k)n_(i)=n的任意一个正整数序列(n_(1),n_(2),…,n_(k)),如果都存在顶点集V(G)的划分(V_(1),V_(2),…,V_(k)),满足Vi导出的子图G[V_(i)]是连通的,并且|V_(i)|=n_(i),其中1≤i≤k,则称图G是任意可分图(简称为AP).两个图G和H的字典积图记为G?H,其顶点集为V(G)×V(H),(g,h)(g,h)是G?H的一条边当且仅当gg∈E(G)或者g=g且hh∈E(H).讨论了可迹图和任意可分图的字典积图的任意可分性,证明了对于最大度至多为n+1的树T,如果T有一条路P满足全部度数为(T)的顶点属于顶点集V(P),则字典积图T○Pn是任意可分图;如果G是一个可迹图且H是任意可分图,则图G○H是任意可分图;如果G=S(2,a,b)是一个满足2≤a≤b的任意可分星型树,则图G○G是任意可分图;如果G是哈密顿图且H是一个图,则G○H是任意可分图.

关键词：图的任意可分性字典积图星型树可迹图

在线全文

学校读者我要写书评

暂无评论

可迹图和哈密顿图的谱充分条件研究

可迹图和哈密顿图的谱充分条件研究

作者：杜雪郑州大学

学位级别：硕士

图谱理论是图论与组合矩阵论中的一个重要课题.判断一个给定图是否是可迹的或哈密顿的是NP-完全问题,给出简洁可用的谱充分条件是非常有意义的.下面我们将给出可迹图和哈密顿图的谱充分条件.·首先介绍了图谱理论的一些历史与背景以及... 详细信息

图谱理论是图论与组合矩阵论中的一个重要课题.判断一个给定图是否是可迹的或哈密顿的是NP-完全问题,给出简洁可用的谱充分条件是非常有意义的.下面我们将给出可迹图和哈密顿图的谱充分条件.·首先介绍了图谱理论的一些历史与背景以及本论文所研究问题的现状和意义.其次介绍了本论文用到的一些重要的概念和符号.最后简要介绍了本论文所做的主要工作.·对于一个连通图是否是可迹的或哈密顿的,本论文基于此图和相应补图的Wiener指数进行讨论给出了充分条件,改正和扩展了 Yang[45]的结果.进一步地,对于连通二部图也给出Wiener指数充分条件.最后,对于连通图和连通二部图给出了距离谱半径充分条件.·对于一个连通图是否是可迹的或哈密顿的,本论文基于此图和相应补图的Harary指数给出了充分条件,改正和扩展了 Hua和Wang[18]的结果.进一步地,对于连通二部图也给出了 Harary指数充分条件.最后,对于连通图和连通二部图给出了 Harary谱半径充分条件.

关键词：可迹图哈密顿图 Wiener指数 Harary指数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

哈密顿连通图和可迹图的新充分谱条件

数学的实践与认识 2017年第11期47卷 272-276页

作者：贾会才王辉中国人民大学信息学院数学系北京100872 河南工程学院理学院河南郑州451191

令G是一个简单连通图,ρ(G)和q^D(G)分别为图G的邻接谱半径和距离无符号拉普拉斯谱半径.提供了图G是哈密顿连通的两个新的谱充分条件,这两个充分条件分别是以ρ(G)和q^D(G)表示的,其中G是G的补图.进一步地,还给出了以q^D(G)表示的图G是... 详细信息

令G是一个简单连通图,ρ(G)和q^D(G)分别为图G的邻接谱半径和距离无符号拉普拉斯谱半径.提供了图G是哈密顿连通的两个新的谱充分条件,这两个充分条件分别是以ρ(G)和q^D(G)表示的,其中G是G的补图.进一步地,还给出了以q^D(G)表示的图G是从任意一点出发都是可迹的新的谱充分条件,从而扩展和改进了文献中的结果.

关键词：哈密顿连通图可迹图邻接谱半径距离无符号拉普拉斯谱半径

在线全文

学校读者我要写书评

暂无评论

可迹图的谱半径条件

安庆师范大学学报（自然科学版） 2018年第1期24卷 6-7,16页

作者：方怡刘琦阮佂周甫安庆师范大学数学与计算科学学院安徽安庆246133

本文研究的是简单图,它的邻接矩阵是表示顶点之间相邻关系的矩阵,它的最大特征值被定义为图的谱半径。如果图中有一条包含图中所有顶点的路,则称这条路为哈密尔顿路;如果一个图含有哈密顿路,则称该图是可迹图。设图具有最小度条件,本文... 详细信息

本文研究的是简单图,它的邻接矩阵是表示顶点之间相邻关系的矩阵,它的最大特征值被定义为图的谱半径。如果图中有一条包含图中所有顶点的路,则称这条路为哈密尔顿路;如果一个图含有哈密顿路,则称该图是可迹图。设图具有最小度条件,本文主要利用图的补图的谱半径给出图是可迹图的充分条件。

关键词：图补图可迹图谱半径最小度

在线全文

学校读者我要写书评

暂无评论

图的可迹性与哈米尔顿—连通性的谱刻画

图的可迹性与哈米尔顿—连通性的谱刻画

作者：刘琦安庆师范大学

学位级别：硕士

谱图理论是代数图论的一个重要研究方向,也是国内外组合矩阵理论与代数组合研究的一个重要课题,它在其他非数学学科,如:化学、统计力学、通信网络、计算机及信息科学等领域均有着广泛的应用.谱图理论是利用矩阵理论,将图的基本结构方面... 详细信息

谱图理论是代数图论的一个重要研究方向,也是国内外组合矩阵理论与代数组合研究的一个重要课题,它在其他非数学学科,如:化学、统计力学、通信网络、计算机及信息科学等领域均有着广泛的应用.谱图理论是利用矩阵理论,将图的基本结构方面的性质与图的相关矩阵的参数关联起来,并找出它们之间的内在联系.为了研究图的性质是怎样通过与这些图相关矩阵的代数性质所反映出来,人们引入了各种不同的矩阵,如:图G的邻接矩阵A(G)、关联矩阵M(G)、距离矩阵D(G)、拉普拉斯矩阵L(G)以及无符号拉普拉斯矩阵Q(G)等.著名的哈密尔顿问题旨在确定一个给定的简单图是否含有哈密尔顿圈,是图论研究的经典问题.迄今为止,虽然有许多相关的研究成果不断涌现,但最理想的解决方案仍尚未找到。近年来,人们试图将谱图理论应用到这个问题的研究中.自Fiedler和Nikiforov于2010年用邻接谱半径刻画图的哈密尔顿性以来,许多图论工作者都致力于图的哈密尔顿谱刻画的研究,并得到很多很好的结论.本文主要内容安排如下:第一章,首先介绍谱图理论的研究背景与意义以及本文涉及到的学术术语和基本概念,接下来阐述研究的问题与相关的进展,并对本文主要结论进行展示;第二章,可迹图的谱半径条件;第三章,哈密尔顿-连通图与可迹图的拉普拉斯谱充分条件.

关键词：图补图可迹图谱半径哈密尔顿-连通图拉普拉斯特征值

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

具有邻域并型的 X-可迹图

昆明理工大学学报（理工版） 1997年第2期22卷 141-148页

作者：梁立云南师范大学计算中心

设Ｇ是连通图，ＸＶ（Ｇ），若Ｇ存在路Ｐ使得ＸＶ（Ｐ），则称Ｇ是Ｘ－可迹图；记ＮＣ２（Ｘ）＝ｍｉｎ｛｜Ｎ（ｕ）∪Ｎ（ｖ）｜：ｕ，ｖ∈Ｘ且ｕｖＥ（Ｇ）｝，我们得到如下结果：如果Ｇ是ｎ阶２－连通图，ＸＶ（Ｇ）并且Ｎ... 详细信息

设Ｇ是连通图，ＸＶ（Ｇ），若Ｇ存在路Ｐ使得ＸＶ（Ｐ），则称Ｇ是Ｘ－可迹图；记ＮＣ２（Ｘ）＝ｍｉｎ｛｜Ｎ（ｕ）∪Ｎ（ｖ）｜：ｕ，ｖ∈Ｘ且ｕｖＥ（Ｇ）｝，我们得到如下结果：如果Ｇ是ｎ阶２－连通图，ＸＶ（Ｇ）并且ＮＣ２（Ｘ）≥ｎ－１２，则Ｇ是Ｘ－可迹图，该结果在可迹图方面推广了Ｂ．Ｊ．

关键词：邻域并独立集连通图 X-可迹图可迹图

在线全文

学校读者我要写书评

暂无评论

关于线图完美匹配数的若干结果

关于线图完美匹配数的若干结果

作者：叶银珠集美大学

学位级别：硕士

图的匹配及其计数不仅在图论和计算科学中起着重要的作用,而且在统计物理和量子化学中占有重要的地位.完美匹配和最大匹配的计数是一个NP-hard问题,本文主要研究一些特殊图类线图的完美匹配和最大匹配的计数问题.设G是n个顶点m条边的连... 详细信息

图的匹配及其计数不仅在图论和计算科学中起着重要的作用,而且在统计物理和量子化学中占有重要的地位.完美匹配和最大匹配的计数是一个NP-hard问题,本文主要研究一些特殊图类线图的完美匹配和最大匹配的计数问题.设G是n个顶点m条边的连通图,L（G）表示它的线图,M（G）和Max（G）分别表示G的完美匹配数和最大匹配数,本文主要研究内容和结论如下:1.研究偶数条边的可迹图线图的完美匹配数.对这类图G,我们首先把M(L（G）)表示为2棵毛毛虫树T的线图完美匹配数M(L（T）)之和,然后通过确定M(L（T）)的最小值和最大值得到M(L（G）)的上界和下界.2.研究偶数条边且最大度等于n-1的图线图的完美匹配数.对这类图G,我们首先把M(L（G）)表示为2棵繁星树S的线图完美匹配数M(L（S）)之和,然后通过确定M(L（S）)的最小值和最大值得到M(L（G）)的上界和下界.3.研究奇数条边的图线图的最大匹配数.首先我们确定了其线图L（G）的最大匹配所含的边数,以及最大匹配数Max(L（G）)的一个一般表达式.然后对树和单圈图线图的最大匹配数进行了讨论,确定了Max(L（G）)的一些最值,并得到了一些特殊图类线图最大匹配数的具体表达式.

关键词：完美匹配最大匹配线图可迹图单圈图树毛毛虫树繁星树

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

似星树与路的乘积图的任意可分性

吉林大学学报（理学版） 2021年第3期59卷 525-530页

作者：张盼盼刘凤霞孟吉翔新疆大学数学与系统科学学院乌鲁木齐830046

设似星树S=S(a 1,a 2,…,a t,b 1,b 2,…,b s),其中a i(1≤i≤t)是奇数,bj(1≤j≤s)是偶数.首先,讨论似星树S与路Pl的乘积图S■P l在t和s不同取值下是否为任意可分图,并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件;... 详细信息

设似星树S=S(a 1,a 2,…,a t,b 1,b 2,…,b s),其中a i(1≤i≤t)是奇数,bj(1≤j≤s)是偶数.首先,讨论似星树S与路Pl的乘积图S■P l在t和s不同取值下是否为任意可分图,并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件;其次,分析图S■P l的Hamilton性,并用似星树的任意可分性给出图为任意可分图的充分条件.结果表明,当t=1且s≤2时,图S■P l是任意可分图;当t≥2或t=0,或者t=1,s≥3,b 1=b 2=…=b s,t+s≥l+2时,图S■P l均不是任意可分图.

关键词：任意可分图乘积图似星树可迹图

在线全文

学校读者我要写书评

暂无评论

似星树和乘积图的任意可分性

似星树和乘积图的任意可分性

作者：张盼盼新疆大学

学位级别：硕士

一个阶为n的图G称为任意可分图(简记为AP),是指对每个满足∑ λ=n的正整数序列=(λ,λ,···,λ),都存在顶点集V的一个划分(V,V,···,V)满足V|=,且V导出的子图连通,其中i=1,2,···,p.似星树S(a,b,c)是同态于K的图.在这篇文章中,我... 详细信息

一个阶为n的图G称为任意可分图(简记为AP),是指对每个满足∑ λ=n的正整数序列=(λ,λ,···,λ),都存在顶点集V的一个划分(V,V,···,V)满足V|=,且V导出的子图连通,其中i=1,2,···,p.似星树S(a,b,c)是同态于K的图.在这篇文章中,我们讨论了两类图的任意可分性,即S(a,b,c)的线图L(S(a,b,c))的任意可分性和乘积图S(?)P的任意可分性.首先,考虑最大度为三的似星树S(a,b,c)的线图的任意可分性,证明图G=L(S(2,b,c))和图G=L(S(3,b,c))是任意可分图的充分必要条件,图G=L(S(a,b,c))不是任意可分图的三个充分条件.其次,设似星树S=S(a,a,···,a,b,b,···,b),其中a是奇数(1≤i≤t),b是偶数(1≤j≤s).对最大度至少为二的似星树S,讨论S(?)P在t和s不同取值下是否为任意可分图.并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件;分析图的哈密顿性,并用似星树的任意可分性给出图为任意可分图的充分条件.结果表明,当t=1且s≤2时,图S(?)P是任意可分图;当t≥2或t=0,或者t=1,s≥3,b=b=···=b,t+s≥l+2时均不是任意可分图.

关键词：任意可分图似星树线图乘积图可迹图