导读:本文包含了分量共轭圈论文开题报告文献综述及选题提纲参考文献，主要关键词:运筹学,分量共轭圈,贪心算法,共轭圈
分量共轭圈论文文献综述
何志红,李国君,李曙光[1]（2009）在《局部几乎正则多部竞赛图中的分量共轭圈》一文中研究指出一个n-部竞赛图是n-部完全图的一个定向。令V1,V2,…,Vn是n-部有向图D的部集。如果D中存在两个不相交的圈C和C′使得对于每一个i∈{1,2,…,n}都有Vi∩(V(C)∪V(C′))≠Φ,则称C和C′是D的一对分量共轭圈。针对多部竞赛图的共轭圈问题,提出了分量共轭圈的定义,同时证明了每一个至少有6个顶点的部集具有相等基数的局部几乎正则多部竞赛图的分量共轭圈的存在性问题。(本文来源于《系统工程与电子技术》期刊2009年10期）
何志红[2]（2007）在《多部竞赛图中的分量共轭圈与共轭圈》一文中研究指出众所周知，竞赛图作为有向图的一部分，具有比较丰富的理论，如1966[47]，综述文章1978[48]和[49]，1981[50]，1994[51]，和1996[52]等。在这种情况下我们对竞赛图的推广图产生了浓厚地兴趣，并对其进行了深入地研究。1990年，Bang-Jensen对竞赛图作了一个非常有意义的推广，得到局部半完全有向图(locally semicomplete digraphs)。如果一个有向图中任意两个不同的点之间至少存在一条弧，则这个有向图是半完全的。如果一个有向图中任何一点的出邻集和入邻集的导出子图均是半完全的，则此有向图为局部半完全有向图。不含长为2的圈的局部半完全有向图称为局部竞赛图。半完全多部有向图(semicomplete multipartite digraphs)是竞赛图的另一类非常有趣的扩展图。一个完全n-部图的每一条边被一条弧或者一对有公共顶点的相反的弧所代替得到的有向图被称为半完全n-部有向图或半完全多部有向图。一个不包含长为2的圈的半完全多部有向图被称为多部竞赛图。竞赛图是每个部集恰有一个点的多部竞赛图。显然，根据定义局部半完全有向图和半完全多部有向图这两类图均比竞赛图这类图更广泛，并且均包含竞赛图这类图。如果有向图D中存在两个不相交的圈C和C′使得V(D)=V(C)∪V(C′)，则D是圈共轭的(cycle complementary)且C和C′是D的一对共轭圈(complementarycycles)。多部竞赛图的共轭圈的存在性依赖于多部竞赛图和它的正则图之间的差距是多少。因此，我们引进被Yeo给出的整体非正则度i_g(D)和局部非正则度i_g(D)这两个参数。一个有向图D的整体非正则度i_g(D)定义为i_g(D)=max{|(?)(d~+(x)，d~-(x))-(?)(d~+(y)，d~-(y))|}。如果i_g(D)=0，则D是正则的(regular)，并且如果i_g(D)≤1，则D是几乎正则的(almost regular)。一个有向图的局部非正则度为i_g(D)，定义为i_e(D)=(?)|d~+(x)-d~-(x)|。如果i_e(D)≤1，则D是局部几乎正则的(locally almost regular)。竞赛图的共轭圈问题几乎已经被Reid在1985年和Song在1993年完全解决。他们证明了对于所有的t∈{3，4，…，|V(D)|-3}，每一个至少有8个点的2-连通的竞赛图D都包含一对长分别为t和|V(D)|-t的共轭圈。几年以后，Guo和Volkmann推广这个结果到局部半完全有向图中。另外，Z．Song，K．Zhang，Manoussakis和J．Wang分别给出二部竞赛图中存在共轭圈的一些结果。2004年，Volkmann证明了每一个正则多部竞赛图都是圈共轭的，除非它属于正则多部竞赛图中的一个有限类。但是，除了竞赛图、二部竞赛图、局部半完全有向图和正则多部竞赛图以外的多部竞赛图的共轭圈的存在性问题仍然是open问题，并且这个问题看起来是相当困难的。于是我们首次给出“分量共轭圈(componentwise complementary cycles)”的定义：定义令V_1，V_2，…，V_c是有向图D的部集。如果在D中存在两个不相交的圈C和C′使得V_1∩(V(C)∪V(C′))≠(?)，对于所有的i=1，2…，c，则称C和C′为D的一对分量共轭圈。如果有向图D中存在两个分量共轭圈，则称D是圈分量共轭的(cycle componentwise complementary)。本文主要是证明多部竞赛图中的分量共轭圈和共轭圈的存在性，共为五章。文章的开始是引言。在第二章中，我们首次给出分量共轭圈这样一个定义。根据定义知共轭圈也是分量共轭圈，于是该定义具有重要的意义。同时首次研究几类多部竞赛图的分量共轭圈的存在性，得到以下重要的成果。首先，我们尝试着证明2-强连通多部竞赛图的分量共轭圈的存在性。注意到每一个2-强连通的多部竞赛图都包含一个3-圈。令C是2-强连通多部竞赛图D的一个3-圈。如果D-V(C)是强连通的，则D-V(C)包含一个最长圈C′使得C和C′是D的一对分量共轭圈。我们主要是证明当D-V(C)不是强连通时D是否包含一对分量共轭圈?结论1令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D-V(C)不是强连通的。对于D-V(C)唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，如果强连通分支中仅有某一个D_i包含圈而其它的分支分别仅由一个点构成，其中1＜i＜α，则D包含一对分量共轭圈。结论2令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D-V(C)不是强连通的。对于D-V(C)的唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，如果|V(D_(α+1-i))|=1，D_i包含圈而其它的分支分别仅由一个点构成，其中i=1或者i=α，则D包含一对分量共轭圈。结论3令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D-V(C)不是强连通的。对于D-V(C)的唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，如果D_1和D_α分别包含圈而其它的分支分别仅由一个点构成，则D包含一对分量共轭圈。由结论1，结论2和结论3，我们得到下面的结论。结论4令D是一个2-强连通的n-部竞赛图但不是竞赛图(n≥6)，C是D的一个3-圈且D-V(C)是非强连通的。对于D-V(C)的唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，令D_c={D_i|D_i包含圈，i=1，2，…，α}和D_(?)={D_1，D_2，…，D_α)＼D_c。如果D_c≠(?)且D_(?)中的每一个元素分别仅由一个点构成，则D包含一对分量共轭圈。其次，我们对局部几乎正则多部竞赛图进行研究，发现当它的所有的部集均有相等的基数时存在一对分量共轭圈，除非它属于局部几乎正则多部竞赛图的一个有限类。于是得到下面的结论：结论5令D是一个局部几乎正则c-部(c≥3)竞赛图且|V(D)|≥6。如果D的所有部集的基数均相等，则D包含一对分量共轭圈，除非它同构于T_7~1或者D_(3，2)(如图1.1，图1.3)。最后，我们考虑了一类特殊图“几乎正则3-部竞赛图”，得到如下结论：结论6如果D是一个几乎正则3-部竞赛图且|V(D)|≥6，则D包含一对分量共轭圈，除非D同构于D_(3，2)(如图1.3)。下面是我们关于多部竞赛图中具有一定长度的共轭圈的一些结论。第叁章我们部分解决了Yeo在1999年提出的猜想，这对于完全解决Yeo猜想具有促进作用，结论如下：结论7如果D是一个至少有8个点的c-部(c≥5)竞赛图，则D包含一对点不相交的长分别为5和|V(D)|-5的圈。第四章我们首次将正则多部竞赛图的共轭圈问题推广到非正则多部竞赛图中考虑，得到一个重要结果，已有的许多重要的结果都可以由它推出。结论8令D是一个至少有8个点的局部几乎正则的c-部(c≥3)竞赛图。如果它的部集具有相等的基数，则D包含一对点不相交的长分别为3和|V(D)|-3的圈。由此结果很容易得到上面的结论5是成立的。由于每一个正则多部竞赛图都是一个部集具有相同基数的局部几乎正则的多部竞赛图，因此得到以下两个推论。推论1 (Volkmann[16])如果D是一个正则的3-部竞赛图且|V(D)|≥6，则D包含一对点不相交的长分别为3和|V(D)|-3的圈，除非D同构于D_(3，2)(如图1.3)。推论2 (Volkmann[15])令D是一个正则的c-部竞赛图且c≥4和|V(D)|≥6。则D包含两个长分别为3和|V(D)|-3的共轭圈，除非D同构于T_7~1，D_(4，2)或者D_(4，2)~*(如图1．1，图1．4，图1．5)。同时将Yeo的猜想推广到更一般的情况，得到下面的猜想：猜想令D是一个至少有8个点的局部几乎正则的c-部(c≥3)竞赛图。如果它的部集具有相等的基数，则对于每一个t∈{3，4，…，|V(D)|-3}，D都包含一对点不相交的长分别为t和|V(D)|-t的圈。猜想如果D是一个至少有6个点的几乎正则c-部(c≥3)竞赛图，则D包含一对共轭圈，除非D属于多部竞赛图的一个有限类。在论文的最后我们给出一些进一步需要解决的问题。(本文来源于《山东大学》期刊2007-05-11）
何志红,李国君[3]（2006）在《正则多部竞赛图中的分量共轭圈》一文中研究指出竞赛图的共轭圈问题已经完全解决,而关于多部有向图的共轭圈问题仍然是一个open问题。Yeo于1999年提出正则多部竞赛图包含共轭圈的猜想。论文根据分量共轭圈(componentwisecomplementarycycles)的定义,证明了:如果D是一个正则的n-部竞赛图(n≥4),则D包含一对分量共轭圈C1和C2,除非它同构于T71。这对于解决Yeo的猜想和多部有向图的共轭圈问题有一定的意义。(本文来源于《计算机工程与应用》期刊2006年17期）
何志红,亓兴勤,李曙光[4]（2005）在《2-均匀多部竞赛图的分量共轭圈问题(Ⅱ)》一文中研究指出讨论均匀多部竞赛图,证明一个2-强连通2-均匀的-n部竞赛图(n6)包含一对分量共轭圈.(本文来源于《山东大学学报(理学版)》期刊2005年05期）
何志红[5]（2004）在《2-均匀多部竞赛图的分量共轭圈问题》一文中研究指出Reid证明了n个顶点的2-强连通竞赛图D包含长分别为3和n-3的一对共轭圈(n≥6)，除非它同构于竞赛图T_7~1(参看图1)。Song证明了在满足Reid定理的条件下，对任意满足3≤t≤n-3的t，竞赛图D都包含长分别为t和n-t的一对共轭圈，除非它同构于竞赛图T_7~1(参看图1)。以上两个定理已经完全解决了竞赛图的共轭圈问题，而多部竞赛图的共轭圈问题尚未解决。本文将竞赛图的结果推广到均匀多部竞赛图上，并证明了2-强连通2-均匀多部竞赛图包含一对分量共轭圈，除非它同构于竞赛图T_7~1(参看图1)。(本文来源于《山西大学》期刊2004-06-01）
何志红,李瑞娟,李胜家[6]（2004）在《均匀多部竞赛图的分量共轭圈问题(英文)》一文中研究指出GUO Yubao和 Volkm ann证明了一个 2 -强连通多部竞赛图包含两个分量共轭圈 ,使得每部至少有一个点在其中的一个圈中 .得到的结论是 Guo和 Volkm ann的定理的进一步推广(本文来源于《山西大学学报(自然科学版)》期刊2004年02期）
分量共轭圈论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
众所周知，竞赛图作为有向图的一部分，具有比较丰富的理论，如1966[47]，综述文章1978[48]和[49]，1981[50]，1994[51]，和1996[52]等。在这种情况下我们对竞赛图的推广图产生了浓厚地兴趣，并对其进行了深入地研究。1990年，Bang-Jensen对竞赛图作了一个非常有意义的推广，得到局部半完全有向图(locally semicomplete digraphs)。如果一个有向图中任意两个不同的点之间至少存在一条弧，则这个有向图是半完全的。如果一个有向图中任何一点的出邻集和入邻集的导出子图均是半完全的，则此有向图为局部半完全有向图。不含长为2的圈的局部半完全有向图称为局部竞赛图。半完全多部有向图(semicomplete multipartite digraphs)是竞赛图的另一类非常有趣的扩展图。一个完全n-部图的每一条边被一条弧或者一对有公共顶点的相反的弧所代替得到的有向图被称为半完全n-部有向图或半完全多部有向图。一个不包含长为2的圈的半完全多部有向图被称为多部竞赛图。竞赛图是每个部集恰有一个点的多部竞赛图。显然，根据定义局部半完全有向图和半完全多部有向图这两类图均比竞赛图这类图更广泛，并且均包含竞赛图这类图。如果有向图D中存在两个不相交的圈C和C′使得V(D)=V(C)∪V(C′)，则D是圈共轭的(cycle complementary)且C和C′是D的一对共轭圈(complementarycycles)。多部竞赛图的共轭圈的存在性依赖于多部竞赛图和它的正则图之间的差距是多少。因此，我们引进被Yeo给出的整体非正则度i_g(D)和局部非正则度i_g(D)这两个参数。一个有向图D的整体非正则度i_g(D)定义为i_g(D)=max{|(?)(d~+(x)，d~-(x))-(?)(d~+(y)，d~-(y))|}。如果i_g(D)=0，则D是正则的(regular)，并且如果i_g(D)≤1，则D是几乎正则的(almost regular)。一个有向图的局部非正则度为i_g(D)，定义为i_e(D)=(?)|d~+(x)-d~-(x)|。如果i_e(D)≤1，则D是局部几乎正则的(locally almost regular)。竞赛图的共轭圈问题几乎已经被Reid在1985年和Song在1993年完全解决。他们证明了对于所有的t∈{3，4，…，|V(D)|-3}，每一个至少有8个点的2-连通的竞赛图D都包含一对长分别为t和|V(D)|-t的共轭圈。几年以后，Guo和Volkmann推广这个结果到局部半完全有向图中。另外，Z．Song，K．Zhang，Manoussakis和J．Wang分别给出二部竞赛图中存在共轭圈的一些结果。2004年，Volkmann证明了每一个正则多部竞赛图都是圈共轭的，除非它属于正则多部竞赛图中的一个有限类。但是，除了竞赛图、二部竞赛图、局部半完全有向图和正则多部竞赛图以外的多部竞赛图的共轭圈的存在性问题仍然是open问题，并且这个问题看起来是相当困难的。于是我们首次给出“分量共轭圈(componentwise complementary cycles)”的定义：定义令V_1，V_2，…，V_c是有向图D的部集。如果在D中存在两个不相交的圈C和C′使得V_1∩(V(C)∪V(C′))≠(?)，对于所有的i=1，2…，c，则称C和C′为D的一对分量共轭圈。如果有向图D中存在两个分量共轭圈，则称D是圈分量共轭的(cycle componentwise complementary)。本文主要是证明多部竞赛图中的分量共轭圈和共轭圈的存在性，共为五章。文章的开始是引言。在第二章中，我们首次给出分量共轭圈这样一个定义。根据定义知共轭圈也是分量共轭圈，于是该定义具有重要的意义。同时首次研究几类多部竞赛图的分量共轭圈的存在性，得到以下重要的成果。首先，我们尝试着证明2-强连通多部竞赛图的分量共轭圈的存在性。注意到每一个2-强连通的多部竞赛图都包含一个3-圈。令C是2-强连通多部竞赛图D的一个3-圈。如果D-V(C)是强连通的，则D-V(C)包含一个最长圈C′使得C和C′是D的一对分量共轭圈。我们主要是证明当D-V(C)不是强连通时D是否包含一对分量共轭圈?结论1令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D-V(C)不是强连通的。对于D-V(C)唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，如果强连通分支中仅有某一个D_i包含圈而其它的分支分别仅由一个点构成，其中1＜i＜α，则D包含一对分量共轭圈。结论2令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D-V(C)不是强连通的。对于D-V(C)的唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，如果|V(D_(α+1-i))|=1，D_i包含圈而其它的分支分别仅由一个点构成，其中i=1或者i=α，则D包含一对分量共轭圈。结论3令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D-V(C)不是强连通的。对于D-V(C)的唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，如果D_1和D_α分别包含圈而其它的分支分别仅由一个点构成，则D包含一对分量共轭圈。由结论1，结论2和结论3，我们得到下面的结论。结论4令D是一个2-强连通的n-部竞赛图但不是竞赛图(n≥6)，C是D的一个3-圈且D-V(C)是非强连通的。对于D-V(C)的唯一的强连通分支无圈序D_1，D_2，…，D_α(α≥2)，令D_c={D_i|D_i包含圈，i=1，2，…，α}和D_(?)={D_1，D_2，…，D_α)＼D_c。如果D_c≠(?)且D_(?)中的每一个元素分别仅由一个点构成，则D包含一对分量共轭圈。其次，我们对局部几乎正则多部竞赛图进行研究，发现当它的所有的部集均有相等的基数时存在一对分量共轭圈，除非它属于局部几乎正则多部竞赛图的一个有限类。于是得到下面的结论：结论5令D是一个局部几乎正则c-部(c≥3)竞赛图且|V(D)|≥6。如果D的所有部集的基数均相等，则D包含一对分量共轭圈，除非它同构于T_7~1或者D_(3，2)(如图1.1，图1.3)。最后，我们考虑了一类特殊图“几乎正则3-部竞赛图”，得到如下结论：结论6如果D是一个几乎正则3-部竞赛图且|V(D)|≥6，则D包含一对分量共轭圈，除非D同构于D_(3，2)(如图1.3)。下面是我们关于多部竞赛图中具有一定长度的共轭圈的一些结论。第叁章我们部分解决了Yeo在1999年提出的猜想，这对于完全解决Yeo猜想具有促进作用，结论如下：结论7如果D是一个至少有8个点的c-部(c≥5)竞赛图，则D包含一对点不相交的长分别为5和|V(D)|-5的圈。第四章我们首次将正则多部竞赛图的共轭圈问题推广到非正则多部竞赛图中考虑，得到一个重要结果，已有的许多重要的结果都可以由它推出。结论8令D是一个至少有8个点的局部几乎正则的c-部(c≥3)竞赛图。如果它的部集具有相等的基数，则D包含一对点不相交的长分别为3和|V(D)|-3的圈。由此结果很容易得到上面的结论5是成立的。由于每一个正则多部竞赛图都是一个部集具有相同基数的局部几乎正则的多部竞赛图，因此得到以下两个推论。推论1 (Volkmann[16])如果D是一个正则的3-部竞赛图且|V(D)|≥6，则D包含一对点不相交的长分别为3和|V(D)|-3的圈，除非D同构于D_(3，2)(如图1.3)。推论2 (Volkmann[15])令D是一个正则的c-部竞赛图且c≥4和|V(D)|≥6。则D包含两个长分别为3和|V(D)|-3的共轭圈，除非D同构于T_7~1，D_(4，2)或者D_(4，2)~*(如图1．1，图1．4，图1．5)。同时将Yeo的猜想推广到更一般的情况，得到下面的猜想：猜想令D是一个至少有8个点的局部几乎正则的c-部(c≥3)竞赛图。如果它的部集具有相等的基数，则对于每一个t∈{3，4，…，|V(D)|-3}，D都包含一对点不相交的长分别为t和|V(D)|-t的圈。猜想如果D是一个至少有6个点的几乎正则c-部(c≥3)竞赛图，则D包含一对共轭圈，除非D属于多部竞赛图的一个有限类。在论文的最后我们给出一些进一步需要解决的问题。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
分量共轭圈论文参考文献
[1].何志红,李国君,李曙光.局部几乎正则多部竞赛图中的分量共轭圈[J].系统工程与电子技术.2009
[2].何志红.多部竞赛图中的分量共轭圈与共轭圈[D].山东大学.2007
[3].何志红,李国君.正则多部竞赛图中的分量共轭圈[J].计算机工程与应用.2006
[4].何志红,亓兴勤,李曙光.2-均匀多部竞赛图的分量共轭圈问题(Ⅱ)[J].山东大学学报(理学版).2005
[5].何志红.2-均匀多部竞赛图的分量共轭圈问题[D].山西大学.2004
[6].何志红,李瑞娟,李胜家.均匀多部竞赛图的分量共轭圈问题(英文)[J].山西大学学报(自然科学版).2004