导读:本文包含了最小强直径定向论文开题报告文献综述及选题提纲参考文献,主要关键词:顶点扩张图,强直径,定向
最小强直径定向论文文献综述
张果香,杨爱民[1](2009)在《2顶点扩张图的最小强直径定向》一文中研究指出给出了直径小于等于2的2顶点扩张图的最小强直径定向及一般的2顶点扩张图的最小的强直径的界,并且对直径大于等于3的树的2顶点扩张图也给出了最小强直径定向。(本文来源于《计算机工程与应用》期刊2009年27期)
张果香[2](2009)在《若干特殊图的最小强直径定向》一文中研究指出无向图G中两点u,v的距离是G中最短的(u,v)路的长.无向图G的直径是指G中任意两个顶点之间的最大距离.有向图中直径定义类似.有向图D中点u,v之间的强距离是包含u,v的D的强连通子图的最小弧数,有向图D的强直径指D中任意两点强距离的最大者.图G的定向是对G的每条边指定一个方向,这样由G得到的有向图D叫做G的定向.如果G的定向D中任意两点之间可以相互到达,则称D为G的强定向.在G的所有可能的定向中,强直径最小的定向称为G的最小强直径定向,其最小强直径记为sdiam(G).本文分为叁章,主要内容如下:第一章的第一部分介绍了图的一些基本概念和术语.第二部分给出了强直径和最小强直径定向的一些重要结果.第二章的第一部分主要讨论了最小强直径定向,得到了以下结果:定理设H是n(n≥3)阶树,则另外,对一般的n(n≥3)阶连通无向图G,我们还得到了下面的关系式:第二章的第二部分讨论了圈的最小强直径定向,得到了以下结果:定理当n是偶数时,当n是奇数时,第二章的第叁部分讨论了单圈图的最小强直径定向,并有下面的结论:定理若G是n阶单圈图,diam(G)≥3,则第叁章的第一部分讨论了路与路的乘积的最小强直径定向,得到了以下结果:定理记Pk是长度为k-1的路,令G=Pm×Pn(m≥2,n≥2)则并且还证明了,对无向图G,若ρ(G)=0,有sdiam(G)=2diam(G).第二部分讨论了路与路的强乘积的最小强直径定向,得到了以下结果:定理记Pk是长k-1的路,令G=Pm(?)Pn(m≥2,n≥4),则(本文来源于《山西大学》期刊2009-06-01)
黄怡,陈美润[3](2009)在《路和路的笛卡尔积的最小和最大定向强半径和强直径(英文)》一文中研究指出强有向图D中任意两个点u,v的强距离sd(u,v)定义为D中包含u和v的最小有向强子图Duv的大小(弧的数目).D中一点u的强离心率se(u)定义为u到其他顶点的强距离的最大值.强有向图D的强半径srad(D)(相应的强直径sdiam(D))定义为D中所有顶点强离心率的最小值(相应的最大值).无向图G的最小定向强半径srad(G)(相应的最大定向强半径SRAD(G))定义为D中所有强定向的强半径的最小值(相应的最大值).无向图G的最小定向强直径sdiam(G)(相应的最大定向强直径SDIAM(G))定义为D中所有强定向的强直径的最小值(相应的最大值).本文确定了路和路的笛卡尔积的最小定向强半径srad(Pm×Pn)和强直径的值sdiam(Pm×Pn),给出了最大定向强半径SRAD(Pm×Pn)的界并提出关于最大定向强直径SDIAM(Pm×Pn)的一个猜想.(本文来源于《新疆大学学报(自然科学版)》期刊2009年01期)
王培[4](2008)在《定向完全分裂图的最小有向直径》一文中研究指出研究了完全分裂图所有定向中的最小有向直径,并得出如下结论:如果|X|=m,|Y|=n,那么当n≥m﹂m/2」时,完全分裂图的最小有向直径是3;当n≤﹂mm/2」-g(m)时,其最小有向直径是2,其中m,n≥5,g(m)是一个已知函数.(本文来源于《郑州轻工业学院学报(自然科学版)》期刊2008年02期)
赵桃艳[5](2007)在《K_m∨■的定向图的最小直径》一文中研究指出对于图H(m,n)=Km∨■,给图定向,使其直径最小.当m≥2,n≥1时,可以得到如下结论:(1)(m是奇数时)对于m=2p+1,p≥1这种情况,当n≤〔m [m/2]〕-m时,图的直径是2;当n≥〔m [m/2]〕时是3.(2)(m是偶数时)对于m=4p+2,p∈N这种情况,如果当n≤〔m [m/2]〕-m/2,那么直径是2,其他的时候是3;对于m=4p,p≥1这种情况,如果n≤〔m [m/2]〕-m/2-1,那么直径是2,其他的时候是3.(本文来源于《黄石理工学院学报》期刊2007年06期)
缪小燕,孙志人[6](2007)在《K_m∨的最小直径定向(英文)》一文中研究指出For a graph G,let D denote an orientation of G having minimum diameter. Define f(G)=diamD.In this paper,we concentrate on exploring the minimum diameter of K_m∨(m≥1,n≥1).Some special cases are known:f(K_m∨)=∞,2,3, where m=1 and n≥1,m=2 or m≥4 and n=1,m=3 and n=1,respectively. So we only consider the case when m≥2 and n≥2.The following results are obtained. (1) f(K_m∨)=3,where m=2,3,n≥2 and m=n=4.(2) f(K_m∨)=2, where m≥5 and m is odd,2≤n≤■-m.(3) f(K_m∨)=2,where m≥4 and m≡0(mod4),2≤n≤■-(m/2+1).(4) f(K_m∨)=2,where m≥6 and m≡2(mod4),2≤n≤■-m/2.(5) f(K_m∨)=3,where m≥4,n>■.(本文来源于《数学季刊》期刊2007年03期)
李艳军[7](2007)在《两类图的最小直径定向》一文中研究指出本文共分两章,主要研究了图的最小直径定向问题。图的最小直径定向问题是在对单行街改造和流言传播等问题的研究中首次提出的,即如何把一个交通系统的每一条路改为单行路,使得任何两点均可互相到达且路程最长者达到最小。这两个问题由于其广泛的应用背景颇受人们关注,目前仍为研究热点。一个无向图G的一个定向是指一个有向图D,它是给G的每条边定一个方向而得到的。如果G的定向D中任何两个顶点是互相可达的,则称D是G的一个强定向。一个连通无向图G中一条边e称为G的桥如果G—e不连通。单行街问题可以追溯到Robbins的经典论文[1],文中给出了着名的单行街定理:一个连通的无向图G有强定向当且仅当G无桥,当一个图G可以强定向时,它的直径便为有限的。如何给G定向使得其直径达到最小,便为图的最小直径定向问题。对于一个无桥的连通无向图G,令D(G)表示G的强定向图的集族,对任意D∈D(G),我们用d(D)(d(G))表示D(G)的直径。定义d(G)=min{d(D)|D∈D(G)}。G(s_1,s_2,…,s_n)(此记号来自[2])为连通无向图G的顶点扩张图(n≥3,s_i≥2,i=1,2,…,n),Koh和Tay在他们的论文[2]中得到不等式:d(G)≤(?)(G(s_1,s_2,…,s_n))≤d(G)+2因而所有形如G(s_1,s_2,…,s_n)的图被分为叁类:φ_i={G(s_1,s_2,…,s_n)|(?)(G(s_1,s_2,…,s_n))=d(G)+i},i=0,1,2同时他们还提出一个猜想[2]:如果无向图G的直径大于或等于3,则G的顶点扩张图G(s_1,s_2,…,s_n)不属于第叁类图φ_2,即G(s_1,s_2,…,s_n)(?)φ_2,(s_i≥2,i=1,2,…,n).该问题举出反例和给出证明都很困难.本文第一章在前人论文的基础上,得出了树的2-顶点扩张图T~(2)的最小直径定向图的两个基本性质,单圈图直径的计算方法,并最终验证了此猜想在单圈图的顶点扩张图中的正确性,即当G是单圈图时猜想成立。第二章研究了两条路强乘积的最小直径定向.Koh和Tay研究了路,圈,完全图等图类的乘积图的最小直径定向问题,本章则给出了两条路强乘积的最小直径定向。(本文来源于《山西大学》期刊2007-06-01)
李艳军,杨爱民[8](2006)在《路与路强乘积的最小直径定向》一文中研究指出给定一个无向图G,将G的每条边{xy}用弧xy或yx替代得到的有向图称为G的的定向图。使得G的所有定向图中直径最小的定向图称为G的最小直径定向。文章给出了两条路强乘积的最小直径定向。(本文来源于《太原科技大学学报》期刊2006年06期)
王琦,赵红銮[9](2006)在《Split完全图的最小直径定向》一文中研究指出利用n-部完全图定向问题的结论,研究一类特殊图———split完全图的最小直径的定向问题,得到split完全图满足2-直径定向的条件及构作.(本文来源于《山东大学学报(理学版)》期刊2006年06期)
冯文丽[10](2006)在《树的顶点扩张图的最小直径定向》一文中研究指出文献[1]将3阶以上的连通无向图的顶点扩张图按照其最小定向直径分为叁类,并给出了如下猜想:直径至少为3的连通无向图的顶点扩张图不属于第叁类图.本文运用顶点标号法,证明了猜想对树是成立的,即树的顶点扩张图的最小定向直径与原树相比最多增加1.(本文来源于《中北大学学报(自然科学版)》期刊2006年02期)
最小强直径定向论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
无向图G中两点u,v的距离是G中最短的(u,v)路的长.无向图G的直径是指G中任意两个顶点之间的最大距离.有向图中直径定义类似.有向图D中点u,v之间的强距离是包含u,v的D的强连通子图的最小弧数,有向图D的强直径指D中任意两点强距离的最大者.图G的定向是对G的每条边指定一个方向,这样由G得到的有向图D叫做G的定向.如果G的定向D中任意两点之间可以相互到达,则称D为G的强定向.在G的所有可能的定向中,强直径最小的定向称为G的最小强直径定向,其最小强直径记为sdiam(G).本文分为叁章,主要内容如下:第一章的第一部分介绍了图的一些基本概念和术语.第二部分给出了强直径和最小强直径定向的一些重要结果.第二章的第一部分主要讨论了最小强直径定向,得到了以下结果:定理设H是n(n≥3)阶树,则另外,对一般的n(n≥3)阶连通无向图G,我们还得到了下面的关系式:第二章的第二部分讨论了圈的最小强直径定向,得到了以下结果:定理当n是偶数时,当n是奇数时,第二章的第叁部分讨论了单圈图的最小强直径定向,并有下面的结论:定理若G是n阶单圈图,diam(G)≥3,则第叁章的第一部分讨论了路与路的乘积的最小强直径定向,得到了以下结果:定理记Pk是长度为k-1的路,令G=Pm×Pn(m≥2,n≥2)则并且还证明了,对无向图G,若ρ(G)=0,有sdiam(G)=2diam(G).第二部分讨论了路与路的强乘积的最小强直径定向,得到了以下结果:定理记Pk是长k-1的路,令G=Pm(?)Pn(m≥2,n≥4),则
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最小强直径定向论文参考文献
[1].张果香,杨爱民.2顶点扩张图的最小强直径定向[J].计算机工程与应用.2009
[2].张果香.若干特殊图的最小强直径定向[D].山西大学.2009
[3].黄怡,陈美润.路和路的笛卡尔积的最小和最大定向强半径和强直径(英文)[J].新疆大学学报(自然科学版).2009
[4].王培.定向完全分裂图的最小有向直径[J].郑州轻工业学院学报(自然科学版).2008
[5].赵桃艳.K_m∨■的定向图的最小直径[J].黄石理工学院学报.2007
[6].缪小燕,孙志人.K_m∨的最小直径定向(英文)[J].数学季刊.2007
[7].李艳军.两类图的最小直径定向[D].山西大学.2007
[8].李艳军,杨爱民.路与路强乘积的最小直径定向[J].太原科技大学学报.2006
[9].王琦,赵红銮.Split完全图的最小直径定向[J].山东大学学报(理学版).2006
[10].冯文丽.树的顶点扩张图的最小直径定向[J].中北大学学报(自然科学版).2006