检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图能量与边控制数关系的研究

图能量与边控制数关系的研究

作者：王玲中国矿业大学

学位级别：硕士

对于一个无环无重边的简单图G,分别用V(G)和E(G)来表示图G的点集和边集.如果E(G)的子集F满足不在集合F中的任意一条边都至少与F中的一条边相邻接,则F称为G的边控制集.G的最小边控制集中所包含的边的条数称为图G的边控制数,记作θ(G).图... 详细信息

对于一个无环无重边的简单图G,分别用V(G)和E(G)来表示图G的点集和边集.如果E(G)的子集F满足不在集合F中的任意一条边都至少与F中的一条边相邻接,则F称为G的边控制集.G的最小边控制集中所包含的边的条数称为图G的边控制数,记作θ(G).图G的能量ε(G)是G的所有特征值的绝对值之和.我们知道图的一个代数不变量——图的能量在图理论中占据重要地位,它在物理、化学等领域也有着广泛应用.Gutman将能量的概念推广到所有简单图,他定义简单图G的能量为ε(G)=(?),其中λ1,...,λn是G特征值.显然,如果我们能计算出一个图的特征值,我们就能立刻知道它的能量.但计算大规模矩阵的特征值是非常困难的,即使对于像邻接矩阵A(G)这样的(0,1)-对称矩阵也是十分困难的.于是,许多研究者便对某些图类建立了很多能量的上、下界来估计这一不变量.本文主要研究图G的能量与边控制数之间的关系.主要内容如下:第一章介绍与图的能量有关的研究背景和现状.第二章介绍了与本文有关的概念和已知的结论.第三章我们研究一种特殊情况——图的控制集为一条边时图的能量.第四章用先用图的边控制数证明了图能量的下界.如果G边控制数为θ的连通图,则ε(G)≥ 2θ,等号成立当且仅当G是完全二部图Kθ.θ.接着用图的边控制数证明了图能量的上界.ε(G)≤2θ(?)+(θ2-θ)((?)+ 1)Δ上界可达当且仅当G是由一条边连接两个K1,Δ-1的中心点得到的图形,其中Δ是G的顶点的最大度.

关键词：图能量特征值最大度点覆盖数边控制数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图能量在肿瘤特征基因提取问题中的应用

图能量在肿瘤特征基因提取问题中的应用

作者：于璐婧山东大学

学位级别：硕士

基因芯片可以快速检测成千上万条基因,从而对生物细胞基因水平做出一个全面的认识。近年来,越来越多学者将基因芯片技术应用到肿瘤与癌症的研究中。针对维数高、样本数量少的微阵列数据,如何从海量数据中提取出数量很少的与疾病和肿瘤... 详细信息

基因芯片可以快速检测成千上万条基因,从而对生物细胞基因水平做出一个全面的认识。近年来,越来越多学者将基因芯片技术应用到肿瘤与癌症的研究中。针对维数高、样本数量少的微阵列数据,如何从海量数据中提取出数量很少的与疾病和肿瘤分类相关的特征基因,对于推进肿瘤的基础研究和发现肿瘤致病机理,科学的认识肿瘤疾病本质具有重要意义。本文致力于通过选取数量较少的特征基因获得正确率较高的分类效果,主要研究工作如下：一个共轭烃分子的能量(π-电子在分子中运动产生的能量)与分子的几何结构图的特征值有很重要的关系。由此而构造的图能量(Graph Energy)是一个描述分子性质的重要变量。文章提出了基于图能量的基因选取方法,将图能量引入到基因芯片分析中,将图能量与信噪比函数(SNR)结合起来,构造一个新的挑选基因的函数SNRGE。提取特征基因时,本文首先使用k-均值聚类对所有基因进行聚类,通过将特征相似的基因聚为一类从而删除冗余基因。然后采用SNRGE公式对所有的基因进行排序,分别在每一类中选取一个得分最高的特征基因。通过该方法在维数高、样本少的基因表达图谱中选取与癌症具有重要相关性的基因,随后使用支持向量机对提取的特征基因进行分类验证并获得正确率。文章通过在结肠癌数据库上的实验验证图能量在特征基因提取中可以获得很好的效果。为了验证文章提出方法的性能,本文给出了一个全面科学的验证。验证包括：与传统的信噪比函数方法进行交叉对比;使用其他文献中提出的信噪比函数替代本文提出的基因选取方法中的SNRGE公式;使用不同的分类器对不同基因提取方法进行对比;针对选取的特征基因进行生物相关性分析;在四个常用的基因芯片数据库上对比不同的基因提取方法的分类效果。将以上五个实验获得的结果进行对比研究,结果证明本文提出的特征基因提取方法在癌症分类问题中是有效的。

关键词：基因选取图能量 SNRGE k-均值聚类支持向量机

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

大规模图能量计算的随机算法研究

大规模图能量计算的随机算法研究

作者：王健健中国矿业大学

学位级别：硕士

图能量是图的邻接矩阵的特征值的绝对值之和,可视为基于图谱的一个不变量,具有实际应用背景和重要应用价值,是图论、量子化学、复杂网络分析、大规模科学计算等领域的重要研究方向之一。大量的已有研究给出了图能量的上下界或者具有特... 详细信息

图能量是图的邻接矩阵的特征值的绝对值之和,可视为基于图谱的一个不变量,具有实际应用背景和重要应用价值,是图论、量子化学、复杂网络分析、大规模科学计算等领域的重要研究方向之一。大量的已有研究给出了图能量的上下界或者具有特定性质图能量的上下界,但是这些上下界可能与实际数值偏差很大。为此,我们提出了一些新的算法来快速有效的估算图能量,使得估计的结果与实际结果在“同一量级”上。基于图邻接矩阵低秩的假设,本文首先提出了基于随机奇异值分解（RSVD）的算法计算图能量,但是该方法中样本的采样量事先难以确定。为了提高计算结果的精度,我们提出一种估算图能量的“不重开始”算法,并给出算法的误差分析和收敛性,该算法需要不停的扩充正交矩阵的列,因此所需的运算量和存储量随迭代会越来越大。为此我们又提出一种“重开始”算法克服该缺陷,并给出新策略的合理性解释。所有算法都可以用来计算大规模无向图和有向图的能量,而且不重开始和重开始的算法都可以用来估算百万量级以上图的能量。数值实验表明了新策略的合理性和算法的有效性。

关键词：图能量邻接矩阵无向图有向图随机算法大规模稀疏矩阵

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

关于图能量的界

内蒙古师范大学学报（自然科学版） 2022年第1期51卷 106-110页

作者：常艳邵燕灵中北大学理学院山西太原030051

研究简单无向连通图的能量。利用图的顶点数、边数、谱半径、最小特征值,获得了图能量的若干个新的上界和下界。这些结论在一定程度上加强了图能量与不同参数的联系。

关键词：图邻接矩阵谱半径图能量

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

图的ISI指数及其能量的研究

图的ISI指数及其能量的研究

作者：李海毓中北大学

学位级别：硕士

图论是以图为研究对象,将事物和事物之间的关系转化为图的点和线,由此研究图的相关性质得到事物之间的关系。图的拓扑指数是从化合物的分子结构图中衍生出的一种数学不变量。图能量的研究来源于化学分子结构的研究,对于不同的图类所对... 详细信息

图论是以图为研究对象,将事物和事物之间的关系转化为图的点和线,由此研究图的相关性质得到事物之间的关系。图的拓扑指数是从化合物的分子结构图中衍生出的一种数学不变量。图能量的研究来源于化学分子结构的研究,对于不同的图类所对应的指数与能量的上下界也有所不同,进而研究指数与能量的界也是现在流行的趋势。本文主要研究的内容是图的基于顶点度的拓扑指数与其能量,分析指数的特殊形式,结合相应的理论知识,通过不等式的放缩和证明,给出指数与能量更为精确的上下界。第一章介绍了图的拓扑指数、图能量的研究背景、意义以及图论的相关概念,并给出了图的ISI指数与能量的研究现状。第二章运用一些熟知的不等式,研究图的ISI指数与能量的上下界,通过考虑ISI指数和能量与图的不变量(最大度、最小度、边度等)和一些已知的拓扑指数之间的关系,从而得到图的ISI指数与能量的一些新上下界。第三章运用ISI-Estrada指数的基本性质,利用图的顶点数和边数等图不变量给出了ISI-Estrada指数的一些上下界,并刻画所对应的极值图,并得到二部图的ISI-Estrada指数的界以及ISI-Estrada指数与ISI能量之间的关系。

关键词：拓扑指数图能量 ISI矩阵 ISI矩阵特征值 ISI能量 ISI-Estrada指数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于图能量的节点重要性的度量方法研究

基于图能量的节点重要性的度量方法研究

作者：马悦山东大学

学位级别：硕士

在网络分析中,度量节点中心性早已成为一个关键问题,它决定了网络中节点的重要性。复杂网络中的重要节点往往在网络的结构和功能上起着举足轻重的作用。因此,识别网络中的重要节点是至关重要的,并且有广泛的实际应用价值,如控制流行病... 详细信息

在网络分析中,度量节点中心性早已成为一个关键问题,它决定了网络中节点的重要性。复杂网络中的重要节点往往在网络的结构和功能上起着举足轻重的作用。因此,识别网络中的重要节点是至关重要的,并且有广泛的实际应用价值,如控制流行病的爆发、宣传电子商务产品、预测流行科学出版物、防止电网或网络的灾难性故障等。对于无权网络,已经存在很多度量节点重要性的经典算法,例如度中心性、接近中心性、介数中心性、PageRank算法和Coreness等。图能量是测定图中所包含的结构信息的一种度量方法,它已经广泛应用于许多领域,包括生物学、化学和社会学。图能量也可以用来衡量节点重要性,即一个节点重要性等价于移除这一节点前后图能量的变化量。本文中,将基于图能量这一概念,引入两种新的节点重要性度量算法。第一种方法称之为Quasi-Laplacian中心性。我们将会根据quasi-Laplacian矩阵引进一种新的图能量——Quasi-Laplacian能量,并基于这一能量构造一种新的节点中心性度量方法——Quasi-laplacian中心性。该算法的中心思想是利用网络G删去某个节点v后,Quasi-Laplacian能量的变化量来反映这一节点的重要性。首先,我们证明移除任何一个节点后Quasi-Laplacian能量的变化量都为正值。其次,证明网络G的Quasi-Laplacian能量不仅与原网络G的边数有关,而且与它对应线图L（G）的边数有关。因此,节点v的Quasi-Laplacian中心性不仅考虑了节点在原图G中的位置,而且考虑了它在线图L（G）中的位置。我们进一步研究了新节点中心性方法的有效性和鲁棒性,把这一方法应用于3个经典的社会网络和14个来自其他领域的网络,并将实验结果与常用的SIR评价模型比较,有力地证实了新中心性方法的效用。第二种方法称为hyper-Zagreb中心性。因为hyper-Zagreb指标常常用于刻画分子间的能量关系,因此我们把这一指标推广到图能量领域,提出一种新的节点中心性度量方法—hyper-Zagreb中心性,并将其应用于衡量节点重要性。我们发现节点v的hyper-Zagreb中心性不仅与它自身的度和邻点的度有关,而且与它邻点的邻点有关。同样将该中心性在实际网络上进行实验,验证了其效用。特别指出的是,Quasi-Laplacian、hyper-Zagreb中心性都与图的参数直接相关,因此运算比较便捷。尤其是Quasi-Laplacian中心性与其他方法（除度中心性）相比有更低的时间复杂度,因此可以应用于大型网络。

关键词：节点中心性图能量 Quasi-Laplacian能量 Hyper-Zagreb指标时间复杂度

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的能量关于控制数的界

图的能量关于控制数的界

作者：黄锐中国矿业大学

学位级别：硕士

令G是一个无向简单图,顶点集为V(G),图G的控制集定义为V(G)的一个子集D,使得任意不在D中的点都至少与D中的一个点邻接.G的控制数是最小控制集中包含点的个数,记作γ(G).图G的能量ε(G),定义为G的所有特征值的绝对值之和.本文主要研究图... 详细信息

令G是一个无向简单图,顶点集为V(G),图G的控制集定义为V(G)的一个子集D,使得任意不在D中的点都至少与D中的一个点邻接.G的控制数是最小控制集中包含点的个数,记作γ(G).图G的能量ε(G),定义为G的所有特征值的绝对值之和.本文主要研究图的能量与控制数之间的关系,全文共分四章内容,具体如下:第一章介绍研究内容的历史和现状,以及本文用到的基本概念和研究背景.第二章借助一些已有的结论,用图的控制数证明能量的下界,对于无孤立点的图G,有ε(G)≥2γ(G),等号成立当且仅当G的连通分支是P2或C4.第三章利用图的控制数得到能量的上界,对于无孤立点的图G,有ε(G)≤(△+1)((△+1)+1)/2γ(G),其中△是G的顶点的最大度,等号成立当且仅当G = K4.第四章对本文的主要内容进行了总结,并对后续的研究做了一个简单的展望.

关键词：图能量特征值控制数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

关于匹配数的图能量的下界

关于匹配数的图能量的下界

作者：王毫霏中国矿业大学

学位级别：硕士

图G的能量ε(G)是G中所有特征值的绝对值之和,记作ε(G)=(?).我们用V(G)和E(G)分别表示G的顶点集和边集.图G中的匹配M是指成对的非相邻边的集合,也就是说M中任意两条边都没有公共顶点.最大匹配是指包含边数最多的匹配,最大匹配中的边的... 详细信息

图G的能量ε(G)是G中所有特征值的绝对值之和,记作ε(G)=(?).我们用V(G)和E(G)分别表示G的顶点集和边集.图G中的匹配M是指成对的非相邻边的集合,也就是说M中任意两条边都没有公共顶点.最大匹配是指包含边数最多的匹配,最大匹配中的边的数目叫作G的匹配数,记作u(G).本篇文章中我们关注于图G的能量和匹配数μ(G)之间的关系,我们证明了对于每一个图G有ε(G)≥2μ(G),且ε(G)≥2μ(G)+(?)c1(G).其中G中的圈(如果存在)是顶点两两不相交的,c1(G)表示G中奇圈的个数.此外,我们证明了如果G有至少一个奇圈且不是满秩的,则ε(G)≥r(G)+1/2.本文主要研究关于匹配数的图能量的下界,全文共分为五章.第一章是绪论部分,主要介绍了论文的选题背景,课题的研究现状和一些重要的符号知识.第二章介绍了相关概念和与本文有关的已知结论.第三章主要研究了关于秩的图能量的新界.第四章主要证明了关于匹配数的图能量的下界的两个重要结论.第五章总结了本篇论文的主要内容,并提出了今后进一步的研究目标。

关键词：图能量匹配数秩

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于图能量的蛋白质2D图形表示及其应用

基于图能量的蛋白质2D图形表示及其应用

作者：孙丹丹山东大学

学位级别：硕士

人类基因组计划的顺利实行与测序技术的急速发展,造成了生物序列数量的急剧增多。面对数以万计的数据,如何发现潜藏在生物数据中的生物信息,分析这些生物序列间的关系,是分子生物学研究中的重要任务。作为构成生命体的物质基础,蛋白质... 详细信息

人类基因组计划的顺利实行与测序技术的急速发展,造成了生物序列数量的急剧增多。面对数以万计的数据,如何发现潜藏在生物数据中的生物信息,分析这些生物序列间的关系,是分子生物学研究中的重要任务。作为构成生命体的物质基础,蛋白质在各种生命活动中发挥着非常重要的作用。在生物信息学的研究领域中,对蛋白质序列进行图形表示和相似性分析,是研究的热点也是难点。本文依据氨基酸的物理化学性质,构建20种氨基酸对应的图形表示。引入图能量的相关理论知识,计算20种氨基酸对应的图能量。进一步构建一种简单新颖的蛋白质序列的图形表示,并从中提取蛋白质序列的数值特征,对蛋白质序列进行相似性分析。论文的主要研究内容如下:（1）本文根据氨基酸的理化性质,提出了一种新颖的氨基酸2D图形表示方法。对于选取的6种理化性质,根据20种氨基酸在不同理化性质下的实验数据以及本文设定的阈值计算公式,构建20种氨基酸对应的图形表示,根据图能量的相关知识,计算20种氨基酸对应的图能量。（2）根据求得的20种氨基酸的图能量以及氨基酸在蛋白质序列中的位置信息,给出蛋白质序列的2D图形表示。应用该方法对ND5数据集中的蛋白质序列进行图形表示,结果证明本文提出的图形表示方法是简单有效的,且具有良好的可视效果。（3）根据本文构建的蛋白质序列的图形表示,进行蛋白质序列的相似性分析。利用转换公式将蛋白质序列转换为多维向量,根据相关理论和实验确定向量的维数。应用欧氏距离计算蛋白质序列两两间的距离并构造距离矩阵,应用距离矩阵构建系统发生树对结果进行检验。（4）为了验证本文提出方法的合理有效性,将该方法应用到ND5、24TFs和36PDs三个数据集中,实验结果与现有的算法一致甚至更加合理。实验证明,本文提出的根据氨基酸理化性质构建氨基酸2D图形表示的方法是合理的,并且具有一定的生物学意义。计算所得的20种氨基酸的图能量也可以很好地表征对应氨基酸。本文提出的蛋白质序列的图形表示方法是简单有效的,将该方法应用到蛋白质序列的相似性分析中,取得了比较理想的实验结果。

关键词：氨基酸理化性质图能量蛋白质图形表示蛋白质相似性分析