检索结果-南通市图书馆

运筹学学报（中英文） 2024年第2期28卷 143-150页

作者：邢抱花孙旻昊余桂东安庆师范大学数理学院安徽安庆246133 合肥幼儿师范高等专科学校公共教学部安徽合肥230013

设G是一个简单的无向连通图,T_(n,α)是顶点数为n独立数为α的所有树的集合。本文主要讨论了在集合T_(n,α)中的最大倒数度距离,并刻画了唯一对应的极图。

关键词：倒数度距离独立数树

在线全文

学校读者我要写书评

暂无评论

随机图的独立数和分数匹配数的一个注记

数学进展 2022年第2期51卷 283-288页

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

设I为图G顶点集的子集.如果I中的任意两个点均不相邻,则称I为G的独立集.G的最大独立集的阶数称为独立数,记为α(G).图G的分数匹配是边集上的函数f∈[0,1],使得对每个顶点v都有∑f(e)≤1,这里是对所有与顶点v相关联边的函数值求和.分数... 详细信息

设I为图G顶点集的子集.如果I中的任意两个点均不相邻,则称I为G的独立集.G的最大独立集的阶数称为独立数,记为α(G).图G的分数匹配是边集上的函数f∈[0,1],使得对每个顶点v都有∑f(e)≤1,这里是对所有与顶点v相关联边的函数值求和.分数匹配数β(G)是所有的分数匹配f中∑_(e∈E(G))f(e)的最大值.本文给出了随机图上关于独立数α(G)与分数匹配数β(G)的一些结果.

关键词：独立数分数匹配数随机图

在线全文

学校读者我要写书评

暂无评论

图的独立数、割边数以及A_σ谱半径

图的独立数、割边数以及A_σ谱半径

作者：周梓涵华中师范大学

学位级别：硕士

图论主要研究图所蕴藏的内部结构,独立数和割边数以及谱半径作为图的重要结构参数和代数参数,能够很好地刻画图的结构性质和代数性质.给定一个图G,我们分别用A(G)和D(G)来表示G的邻接矩阵和度对角矩阵.2017 年,Nikiforov 首次提出Aσ矩... 详细信息

图论主要研究图所蕴藏的内部结构,独立数和割边数以及谱半径作为图的重要结构参数和代数参数,能够很好地刻画图的结构性质和代数性质.给定一个图G,我们分别用A(G)和D(G)来表示G的邻接矩阵和度对角矩阵.2017 年,Nikiforov 首次提出Aσ矩阵:Aσ(G)=σD(G)+(1-σ)A(G),其中σ∈[0,1].这种新型矩阵的最大特征值被称为G的Aσ谱半径.显然,A(G)=A0(G),D(G)=A1(G)且Q(G)=2A1/2(G),其中Q(G)表示图G的无符号拉普拉斯矩阵,简称Q-矩阵.设Bnα表示独立数为α的所有n阶块图构成的集合,G(n,k)表示割边数为k的所有n阶图构成的集合.在本文中,我们分别刻画了在Bnα和G(n,k)中,Aσ谱半径达到最大时对应的唯一极图.令人惊讶的是,在这两种情况下对应的极图吻合,都是菠萝图.我们使用不同的方法建立了极图Aσ谱半径的上界,并在σ=1/2时对所得到的两个界进行了比较.本文主要内容分为七章,具体如下:·第一章主要介绍了论文的研究背景.通过对研究背景的系统分析,给出了我们研究工作的动机和出发点,进而展现了我们研究工作的必要性和创新点.·第二章给出了一些基本概念、符号以及一些需要用到的相关已知结论.·第三章对所有的正整数n和满足1≤α≤n-1的正整数α以及σ∈[0,1),刻画了在Bnα中Aσ谱半径达到最大时对应的唯一极图.·第四章对所有满足n≥5的正整数n和满足2≤α≤n-2的正整数α以及σ∈[0,1/2],用n,α,σ建立第三章中所得极图的Aσ谱半径一个紧的上界.·在第五章,对所有的正整数n和满足0≤k≤n-1的整数k以及σ∈[0,1),我们一方面刻画了G(n,k)中Aσ谱半径达到最大时的唯一极图;另一方面,当n≥5.1≤k≤n-3以及σ∈[0,1/2]时,用n,k,σ来建立了该极图Aσ谱半径一个紧的上界.·在第六章,通过分析我们发现Bnα中极图的独立数α和G(n,k)中极图的割边数k具有如下关系:α=k+1.进而通过在第四章和第五章所得到的结果,我们便可导出Q-谱半径的两个上界,并进行了比较,得到一个较好的上界.这些拓展了前人的一些结果.·第七章总结全文并作出展望.

关键词： A_σ谱半径 Q-谱半径块图独立数割边

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

固定独立数的图的Aα-谱半径研究

固定独立数的图的Aα-谱半径研究

作者：陈元梅青海师范大学

学位级别：硕士

令G是一个连通图,A（G）和D（G）分别是图G的邻接矩阵和度对角矩阵.2017年Nikiforov首次定义了这两个矩阵的凸线性组合,即对于任意的α ∈[0,1],Aα（G）=αD（G）+（1-α）A（G）.事实上,该凸线性组合作为邻接矩阵A（G）和无符号拉普... 详细信息

令G是一个连通图,A（G）和D（G）分别是图G的邻接矩阵和度对角矩阵.2017年Nikiforov首次定义了这两个矩阵的凸线性组合,即对于任意的α ∈[0,1],Aα（G）=αD（G）+（1-α）A（G）.事实上,该凸线性组合作为邻接矩阵A（G）和无符号拉普拉斯矩阵Q（G）的共同推广,显然有A（G）=A0（G）,Q（G）=2A1/2（G）.此外,有一个关键特征是 Aα（G）-Aβ（G）=（α-β）L（G）,α,β ∈[0,1],其中 L（G）是图G的拉普拉斯矩阵,定义为L（G）=D（G）—A（G）.Aα（G）矩阵的最大特征值称为图G的Aα-谱半径,关于Aα-谱极值问题的研究具有重要理论价值.目前的研究热点是关于固定图参数的Aα-谱极值问题.寻求Aα-谱半径的上界,并且刻画达到上界的极图,这是Brualdi和Solheid的问题在矩阵上的推广.本文主要研究固定独立数的图的Aα-谱极值问题.分别研究了固定独立数的最大Aα-谱极值问题,固定独立数的图的最小Aα-谱极值问题,以及固定独立数的块图类中最大Aα-谱极值问题.确定了顶点数为n、独立数为γ（1/2≤γ≤n-1）的树集中唯一取得最大Aα-谱半径的图;确定了顶点数为n、独立数为γ（1/2≤γ≤n-1）的连通图中唯一取得最大Aα-谱半径的图是团星,唯一取得最小Aα-谱半径的图是团路;确定了顶点数为n、独立数为γ（1/2≤γ≤n-1）的块图类中,唯一取得最大Aα-谱半径的图是菠萝图.

关键词： Aα-谱半径独立数极值图树块图

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

不含三角形的图的独立数和匹配数关系

同济大学学报（自然科学版） 2017年第1期45卷 124-126页

作者：陈明李雨生同济大学数学科学学院上海200092 嘉兴学院数理与信息工程学院浙江嘉兴314000

设α(G),β(G)和n(G)分别表示图G的独立数、匹配数和阶数.图的独立数和匹配数是图的两个较重要的参数.证明了对于不含三角形且最大度不超过5的图,独立数、匹配数和阶数之间存在两个最优的数量关系.

关键词：独立数匹配数三角形最大度

路径幂图、Flower Snark图及多锥图独立数

在线全文

学校读者我要写书评

暂无评论

大连理工大学学报 2010年第2期50卷 309-312页

作者：徐连诚杨元生夏尊铨大连理工大学数学科学学院辽宁大连116024 山东师范大学信息科学与工程学院山东济南250014 大连理工大学计算机科学与技术学院辽宁大连116024

图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多... 详细信息

图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多锥图的独立数问题,首先构造出了它们的独立集,得到其独立数的下界,然后证明了该值也是其独立数的上界,并给出了它们独立数的准确值.

关键词：独立集独立数路径幂图 Flower Snark 多锥图

在线全文

学校读者我要写书评

暂无评论

图的完全积的独立数和独立多项式

大理大学学报 2023年第6期8卷 1-8页

作者：杨利民大理大学数学与计算机学院云南大理671003

在图论中,独立数和独立多项式是NP难问题。它们是非常困难的问题,然而,通过变换问题,可以找到一种求解独立数和独立多项式的有效方法。通过将基数k的稳定集合问题转化为k阶完全子图问题,得到独立多项式的计算方法。类比,将最大稳定集合... 详细信息

在图论中,独立数和独立多项式是NP难问题。它们是非常困难的问题,然而,通过变换问题,可以找到一种求解独立数和独立多项式的有效方法。通过将基数k的稳定集合问题转化为k阶完全子图问题,得到独立多项式的计算方法。类比,将最大稳定集合的大小转化为最大完全图的大小,得到独立数的计算方法。利用组合计算给出许多图的完全积的独立数和独立多项式的显式公式。进一步利用发生函数导出图的Merrifield-Simmons指数。证明了一些独立多项式的系数序列是单峰的,有一些不是单峰的,并否定了树的独立多项式的系数序列是单峰的猜想,这对组合数学和图论有重要的价值和意义。

关键词：稳定集合独立数完全积独立多项式单峰性

维普期刊数据库博看期刊

给定连通度和独立数图的最大A_(α)谱半径

在线全文

学校读者我要写书评

暂无评论

青海师范大学学报（自然科学版） 2023年第1期39卷 48-51页

作者：张磊韩淑蓉余欢周曾鹏青海师范大学数学与统计学院青海西宁810016 青海师范大学省部共建藏文智能信息处理及应用国家重点实验室青海西宁810016

令A(G)、D(G)分别是图G的邻接矩阵和度矩阵,对于任意实数α∈[0,1],图G的A_(α)矩阵记作:A_(α)(G)=αD(G)+(1-α)A(G).对于图G,如果图G至少有k+2个顶点,且删除任意k-1个顶点后图依然是连通图,那么图G是k-连通的,连通度记作k.独立集是图... 详细信息

令A(G)、D(G)分别是图G的邻接矩阵和度矩阵,对于任意实数α∈[0,1],图G的A_(α)矩阵记作:A_(α)(G)=αD(G)+(1-α)A(G).对于图G,如果图G至少有k+2个顶点,且删除任意k-1个顶点后图依然是连通图,那么图G是k-连通的,连通度记作k.独立集是图G中任意互不相邻的顶点的集合,最大的独立集是给定图G中一个顶点数最多的独立集,而这个最大独立集的顶点个数就是图G的独立数,记作r.在本文中我们主要研究n阶、连通性为k、独立数为r的图类,我们确定了这类图具有最大A_(α)谱半径的极图结构.

关键词：图 A_(α)谱半径独立数连通度

在线全文

学校读者我要写书评

暂无评论

独立数的一个下界

中国科学（A辑） 2001年第10期31卷 865-870页

作者：李雨生 C.C.Rousseau 臧文安河海大学数学物理系南京210098 Department of Mathe matical Sciences The University of Memphis 香港大学数学系

设G是一个图 ,其度序列为 (dv) .若由G的任意邻域导出子图的最大度至多为m ,则G的独立数至少是 ∑vfm +1(dv) ,这里当x >0 ,函数fm +1(x)大于log(x/(m + 1 ) ) - 1x .对于加权图G =(V ,E ,w) ,证明了它的加权独立数至少是∑vwv1 +dv,这... 详细信息

设G是一个图 ,其度序列为 (dv) .若由G的任意邻域导出子图的最大度至多为m ,则G的独立数至少是 ∑vfm +1(dv) ,这里当x >0 ,函数fm +1(x)大于log(x/(m + 1 ) ) - 1x .对于加权图G =(V ,E ,w) ,证明了它的加权独立数至少是∑vwv1 +dv,这里wv 是顶点v的权重 .

关键词：独立数离散形式加权图图论导出子图局部稀疏图 Turan定理

在线全文

学校读者我要写书评

暂无评论

独立数的另一类关系

数学杂志 1991年第2期11卷 129-132页

作者：王建方张忠辅中国科学院应用数学研究所兰州铁道学院

本文研究了图的独立数与边独立数、独立数与全独立数、边独立数与全独立数、图的独立数与其补图边独立数、图的独立数与其补图的全独立数、图的边独立数与其补图全独立数之间的关系。

关键词：图补图独立数边独立数全独立数