导读:本文包含了超图划分论文开题报告文献综述、选题提纲参考文献及外文文献翻译,主要关键词:超图,线性,在线,模块,知识,单色,建模。
超图划分论文文献综述
金晶,许宝刚[1](2019)在《超图与图公平划分的l-元组》一文中研究指出令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数. Fan和Hou(2017)证明了每个最大度为?的m阶图G都存在一个k部划分(V_1, V_2,..., V_k),使得对于任意1≤i <j≤k,都成立e(V_i∪V_j)min≤{4/k~2×m+4?/k,m/k-1}+o(m~(7/8)).令H表示最大度为?的m阶r-一致超图,本文证明H存在一个k部划分(V_1, V_2,..., V_k),对于任意1≤i <j≤k,满足e(V_i∪V_j)≤r-1/k-1×m+o(m);也证明当?=o(m)时, H存在一个k部划分(V_1, V_2,..., V_k),使得对于任意l∈[k-1]和每个l元组(V_(j1),..., V_(jl)),有e(V_(j1)∪···∪V_(jl))≤l~r/k~r/m+o(m).(本文来源于《中国科学:数学》期刊2019年07期)
李婷婷,张霞[2](2019)在《均衡的完全3-部3-一致超图的单色放松路划分》一文中研究指出目前对于k-一致超图的2-边染色的单色放松路、放松圈的划分问题的相关结论很少,并且已有的结论主要是对完全的k-一致超图进行了研究.本文首次研究了关于均衡的完全3-部3-一致超图的2-边染色的单色放松路的划分问题,为今后进一步研究一般的k-部k-一致超图的单色划分问题打下基础.(本文来源于《山东师范大学学报(自然科学版)》期刊2019年02期)
李婷婷[3](2019)在《超图的多色染色和单色路划分问题研究》一文中研究指出设H是一个超图.如果超图H=(V(H),E(H)),|V(H)|=n,满足任意kk个点都恰好是一条超边∈∈E(则称超图H为完全的k-一致超图,简记为Kn~((k)).完全的3-部3-一致超图,我们简记为K_(n_1,n_2,n_3)~((3)),它是指将V(H)划分成点不交的叁部分V_1,V_2,V_3,即(?)V_i=V(H),V_i∩V_j=(?),其中1≤i<j≤3,并且对任意的u ∈ V_1,v ∈V_2,ω∈V_3.对应有超边uvw ∈ E(H).超图H的一个m-点染色是指对超图H的顶点进行m种颜色1,2,.…,m的一个分配,如果超图H的一个m-点染色使得超图中没有单色超边,那么我们称超图H是m-可染的.特别地,超图H是2-可染的也称超图H有性质B.如果超图H的一个m-点染色,满足每条超边包含每种颜色的至少一个顶点,则我们称超图H的这个m-点染色为多色m-染色(polychromatic m-coloring).值得注意的是,如果超图H有一个多色m-染色那么超图H就有一个多色l-染色,其中1 ≤ l ≤ m.首先,本论文在研究已有的超图的2-染色的相关结论的基础之上,讨论了关于超图的顶点的多色染色.我们对两个问题很感兴趣:(1)如何让超图的一个多色m-染色的m的值尽可能的大?(2)怎样在多色染色中让超边中每种颜色的顶点数出现的尽可能的均匀?我们得到了关于超图的顶点的多色染色的两个结果,改进了之前的部分结果.我们定义超图H~*为超图H=(V,E)的对偶,其中V={X_1,x_2,...,x_n},E={Y_i,Y_2,...,Y_m},超图H~*的顶点f_1,f_2,...,f_m对应超图H的超边,并且它的超边X_i={y_j|x_i ∈ Y_j},i=1,2,...,n.超图H~*的一个多色m-染色对应H的一个覆盖m-分解.因此超图H的多色m-染色的结论可以用对偶形式陈述.其次,我们讨论了完全超图的2-边染色,通常用红色和蓝色这两种颜色来表示.目前对于完全超图的2-边染色的单色放松路划分的研究结果相对较少,先前主要集中对完全kk-一致超图的研究.本论文首次研究了均衡的完全3-部3-一致超图的2-边染色的单色放松路的划分问题,为以后研究一般的kk-部k-一致超图的单色划分问题打下基础.本论文共分四章进行讨论.第一章,我们主要介绍了图与超图的染色问题及超图划分问题的背景及意义,给出了本篇论文中所涉及到的基本概念与符号,阐述了超图的多色染色和单色划分问题的研究现状,列出了本文的主要结果.第二章,我们讨论了超图的点的多色染色与边覆盖分解.第叁章,我们研究了均衡的完全3-部3-一致超图的单色放松路划分的问题.第四章,我们指出了本论文可进一步研究的问题.(本文来源于《山东师范大学》期刊2019-03-20)
王兵[4](2018)在《边染色超图的划分和覆盖问题研究》一文中研究指出图(超图)的划分和覆盖是属于图论的Ramsey理论的一类经典问题.它包含两个子问题:一、在一个任意的r-边染色完全图(超图)中我们一定能够找到最多包含多少个顶点且具有特定结构的单色子图(超图)?二、需要至少多少个特定类型的单色子图(超图)就一定可以覆盖一个任意r-边染色完全图(超图)的所有顶点?该类问题在图的层面结果很多,然而在超图中相应的结果很少,甚至在2-边染色一致完全超图中,基本的路和圈划分和覆盖以及相关的Ramsey数问题也没有得到完全解决.本论文主要研究边染色一致超图的线性路和线性圈划分和覆盖问题.在此基础上研究边染色一致完全超图的?-路和?-圈以及其他子图的划分和覆盖问题.本论文分为以下五个章节.第一章我们介绍了一些基本概念和定义,比较全面地介绍了与本论文相关的边染色图划分和覆盖的已知结果和重要猜想.第二章我们介绍了边染色超图的基本概念,给出了边染色超图划分和覆盖的相关结论.并重点研究了2-边染色k-一致完全超图线性路划分和覆盖问题.这一问题源于2013年Gy′arf′as和S′ark¨ozy提出的如下猜想.猜想:每个2-边染色k-一致完全超图Kk n一定存在两条顶点不交且颜色不同的单色线性路覆盖Kk n中至少n-k+2个顶点.Gy′arf′as和S′ark¨ozy说明了如果猜想成立,则该结果对充分大的n是紧的.Gy′arf′as和S′ark¨ozy证明了每个2-边染色k-一致完全超图Kk n一定存在两条顶点不交且颜色不同的单色线性路覆盖Kk n中至少n-2k+5个顶点.该结果表明猜想对k=3是成立的.我们证明了一个比Gy′arf′as和S′ark¨ozy提出的猜想更强的结论.定理.设k≥3为任意正整数.对每个2-边染色k-一致完全超图Kk n而言,如果n=r(k-1)+2对某个非负整数r成立,则V(Kk n)可以划分成两条不同颜色的单色线性路.基于这个结论,我们自然地考虑如下的覆盖问题:对任意一个2-边染色Kk n,我们是否可以找到两条不同颜色的单色线性路(不必顶点不交)覆盖V(Kk n)满足这两条路相交的顶点数尽可能少?我们得到了如下2-边染色k-一致完全超图的线性路覆盖结果.定理.设k≥3为任意正整数.对任意2-边染色k-一致完全超图Kk n,它的所有顶点可以由两条不同颜色的单色线性路覆盖使得这两条路至多共用k-2个顶点.这个结果是紧的.第叁章我们介绍了单色线性圈划分和覆盖的现有结果.我们猜想:对k≥3和任意的2-边染色k-一致完全超图Kk n,V(Kkn)可以由两个不同颜色的单色线性圈(不必顶点不交)覆盖.我们证明了k=3时,该猜想是成立的.定理.设K3n是一个2-边染色3-一致完全超图.则V(K3n)能被两个不同颜色的单色线性圈覆盖满足这两个圈至多共用2个顶点.第四章我们考虑了边染色完全超图的?-路和?-圈覆盖和划分问题.我们提出如下猜想:设s≥0,k≥3为两个任意的正整数,如果n=s(k-?)+2?,则2-边染色k-一致完全超图Kk n的所有顶点可以划分成两条不同颜色的单色?-路.我们证明了当?|k或?≤k3时,该猜想是成立的.定理.设?,s,k为任意的叁个正整数且?≤k3.如果n=s(k-?)+2?,则2-边染色k-一致完全超图Kk n的所有顶点可以划分成两条不同颜色的单色?-路.第五章我们对本论文进行了简单的总结,提出了以后要进一步考虑的主要问题.(本文来源于《华东师范大学》期刊2018-05-08)
王田[5](2018)在《基于超图划分的高维数据聚类方法研究》一文中研究指出聚类分析是一个相当重要的课题,随着现代技术的发展,数据结构变得复杂,使得数据的维度相应增大,数据维度的增长,对传统的聚类算法带来了不同的挑战,特别是,对于高维数据,由于维灾难的影响,传统聚类算法使用的相似性度量在高维空间中是没有意义的,高维数据存在的普遍性,使得高维数据聚类的算法研究已成为聚类分析的一个重要研究方向,很多针对高维数据的聚类方法被提出来。其中,基于降维的聚类方法是处理高维聚类的一个行之有效的手段,通过将高维数据降低到相对较低的维度,在减少数据维度的过程中,又很好的保留了数据的结构特征,然后再使用传统聚类算法对其进行聚类。数据降维的技术近些年得到了快速的发展,典型的降维算法有PCA,LLE,SNE,Autoencoder等,不同的方法适合于不同的数据结构。同时,由于高维数据的很多属性都是冗余的,只有少量的主要特征决定数据的结构,这启发了子空间聚类的产生,子空间聚类就是找到嵌入在原始数据空间的特征子空间,并在这些子空间考察聚类的过程。超图划分被认为是处理高维数据聚类的有效方法。在本文的研究中,提出了一个新的高维聚类方法称为MDSG(Merging Dense SubGraphs)。该方法首先通过共享近邻(SNN)方法,构造数据的共享近邻图G,然后将图G中的最大团定义为超图的超边,构造出一个超图。最后利用一个改进的超图划分方法得出最终聚类结果。使用几种不同类型的高维数据集对本文提出的MDSG方法进行评估,实验结果表明,在高维数据的聚类方面,该方法优于传统的聚类方法和其他超图划分方法。(本文来源于《兰州大学》期刊2018-05-01)
黄月盈[6](2018)在《基于超图划分的华为社区界面标签设计》一文中研究指出随着WEB 2.0技术的发展,电子商务市场的变化以及消费者消费习惯的改变,越来越多的品牌创建了自己的在线社区。在线社区比现实社区更便捷,更高效且更多元,吸引着越来越多的品牌消费者参与到当中,成为了社区用户交互的平台,其中,海量的用户生成内容(UGC,User-Generated Content)也应运而生。这给社区的信息管理带来了严峻的挑战,存在如信息过载,信息噪声,用户无法准确定位需求的相关信息,有价值的信息无法被发现等问题。如何良好的梳理社区信息,将其有效分类,使得用户和企业都能挖掘出有价值的信息成为当下研究热门。本文基于在线社区——华为花粉俱乐部“功能建议”版块的用户生成内容未分类情况,利用用户生成内容构建社区用户知识超图,并结合超图划分算法挖掘社区领域知识,并将挖掘出的领域知识作为标签添加到该社区界面,以求在挖掘出该版块价值信息的同时,优化版块标签系统,实现良好的信息分类。本文的主要工作包括如下几方面:对华为花粉俱乐部“功能建议”版块用户生成内容采用Python抓取工具采集,采集变量主要包括用户,帖子,浏览量和回复量等关键信息,并在考虑浏览量和回复量的同时分析出帖子的关键知识,最后通过分析用户,帖子和关键知识内在关系,构建了华为花粉俱乐部“功能建议”版块知识超图模型,以求完整全面的描绘出该版块信息分布情况,为研究社区用户生成内容的全要素管理提供了思路。基于构建的华为花粉俱乐部“功能建议”版块知识超图模型,采用hMETIS超图划分工具对该模型进行划分,挖掘出了该社区版块的领域知识,对知识超图模型的研究采取了探索性分析。并在hMETIS超图划分工具中的参数选择和程序选择方面做出了对比分析,找出本文研究背景下最佳划分程序和参数匹配方案。针对挖掘出的华为花粉俱乐部“功能建议”版块领域知识,从管理在线社区信息的角度出发,结合PS界面设计,将领域知识作为分类标签应用于华为在线社区,优化了该社区界面的信息管理。将超图方法应用到实际的管理问题中,在解决了实际现存的管理问题时,为超图方法的应用提供了新的视角。(本文来源于《暨南大学》期刊2018-04-01)
冷明,孙凌宇,朱平,李金忠[7](2016)在《赋权超图划分问题的多水平迁移优化算法研究》一文中研究指出伴随着赋权超图划分问题的规模不断地增长,对赋权超图划分的处理效率和能力、准确性有了更高程度的要求.本文采用形式化符号描述了赋权超图优化划分问题,阐明了基于多水平思想求解该问题的粗化、初始划分和迁移优化叁个阶段;提出了基于离散粒子群和多水平思想的迁移优化算法,在|V|维空间中每个粒子所处的位置对应于超图划分方案;伴随着投影优化阶段的细化,每个粒子对应的划分方案映射到下一水平层的粗化超图;随着划分问题解空间的维度|V|增加,粒子的自由度增大;将结点迁移的收益值作为粒子的启发式搜索信息,利用粒子之间聚集协同表现出的智能行为有效地搜索解空间;给出了赋权超图的改进压缩存储格式,提出了割切值和收益值的快速计算方法,有效降低了划分算法的时空复杂度.基于ISPD98测试基准的对比实验数据表明:与基于迁移方法的赋权图、赋权超图优化划分算法相比,本文算法有效地增强了迁移优化算法逃离局部最优的能力.(本文来源于《小型微型计算机系统》期刊2016年06期)
魏小凤,胡继承,罗永恩[8](2016)在《基于超图模型的软件模块自动划分》一文中研究指出应用超图理论模型设计软件模块的自动划分算法。通过分析软件源码建立超图模型,将类抽象为超图的顶点,使多个类之间存在关联,将软件模块划分转换为超图划分问题,再利用超图模型实现对超图的划分,从而达到软件模块划分的目的。基于高内聚低耦合原则给出模块度的概念,得到优化的分割结果。以开源软件为实验数据,并与传统的划分算法hMetis进行对比,结果表明该算法的划分结果较优,验证了其合理性与有效性。(本文来源于《计算机工程》期刊2016年01期)
宋国治,张大坤,马杰超,涂遥,刘畅[9](2016)在《异构叁维片上网络布局优化的超图划分算法》一文中研究指出片上网络作为一种将大量嵌入式内核集成到单个晶圆片上的可行性技术,与传统片上系统相比,更能应对未来需要更大规模集成内核的挑战,从而得到了更广泛的应用。然而,目前大多数对片上网络的研究是在规则的架构上进行的,即假定所有单元片面积相同,但是这种假设过于理想化。因此,基于异构布局的叁维片上网络的研究是非常有必要的,而其中网络单元的合理划分对片上网络的性能有着重要的影响。介绍了基于异构布局的叁维片上网络架构,并将超大规模集成网络中的单元映射成一张超图,并且对此超图进行了多级划分。在算法框架的不同阶段,介绍了常见的算法,并且对相应算法的潜在问题进行分析,随后对这几种算法进行改进以提高片上网络的性能。最后,通过对几个常见的超大规模集成单元数据集进行实验分析,比较了不同阶段的算法对该片上网络各个性能的影响,并得出各个数据集上最优的hMetis算法框架。(本文来源于《计算机科学与探索》期刊2016年06期)
于丰,刘威,李鹏[10](2014)在《P2P网络负载调度的超图划分算法》一文中研究指出目的解决P2P用户数量持续增多时,网络节点异质性造成的负载不均衡问题,提高节点和带宽利用率.方法基于超图的动态划分思想和排队论的理论证明,将网络划分为若干个小区域的集合,利用定义的超级节点对本区域内的节点进行管理.每个区域随机选取另一个区域共同进行超图的2路划分过程,使划分后的区域总负载保持一致.通过每个小区域的节点负载平衡来获得整个网络负载的相对平衡.结果实验结果表明,采用负载均衡算法的网络节点利用率有了明显改善,而且能在更短的时间内调整至均匀分布状态.在连接数较高的情况下,网络仍然能够保持较好的稳定性.结论基于超图划分的负载调度方案可以使系统的局部范围处于平衡状态,进而实现P2P网络整体的负载均衡.(本文来源于《沈阳建筑大学学报(自然科学版)》期刊2014年05期)
超图划分论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
目前对于k-一致超图的2-边染色的单色放松路、放松圈的划分问题的相关结论很少,并且已有的结论主要是对完全的k-一致超图进行了研究.本文首次研究了关于均衡的完全3-部3-一致超图的2-边染色的单色放松路的划分问题,为今后进一步研究一般的k-部k-一致超图的单色划分问题打下基础.
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
超图划分论文参考文献
[1].金晶,许宝刚.超图与图公平划分的l-元组[J].中国科学:数学.2019
[2].李婷婷,张霞.均衡的完全3-部3-一致超图的单色放松路划分[J].山东师范大学学报(自然科学版).2019
[3].李婷婷.超图的多色染色和单色路划分问题研究[D].山东师范大学.2019
[4].王兵.边染色超图的划分和覆盖问题研究[D].华东师范大学.2018
[5].王田.基于超图划分的高维数据聚类方法研究[D].兰州大学.2018
[6].黄月盈.基于超图划分的华为社区界面标签设计[D].暨南大学.2018
[7].冷明,孙凌宇,朱平,李金忠.赋权超图划分问题的多水平迁移优化算法研究[J].小型微型计算机系统.2016
[8].魏小凤,胡继承,罗永恩.基于超图模型的软件模块自动划分[J].计算机工程.2016
[9].宋国治,张大坤,马杰超,涂遥,刘畅.异构叁维片上网络布局优化的超图划分算法[J].计算机科学与探索.2016
[10].于丰,刘威,李鹏.P2P网络负载调度的超图划分算法[J].沈阳建筑大学学报(自然科学版).2014