导读:本文包含了拟阵圈图论文开题报告文献综述及选题提纲参考文献,主要关键词:拟阵,拟阵圈图,哈密尔顿圈,均匀染色
拟阵圈图论文文献综述
樊昊[1](2013)在《拟阵圈图的性质和图的染色问题》一文中研究指出图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象。一个连通图的树图能够反映该图的不同支撑树之间的变换关系。因此,研究一个图的树图有助于我们更好地了解该图的性质。同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系。因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质。近些年来,树图和拟阵的基图被推广得到了一些新的图。为了研究拟阵中圈图的性质,P.Li和G.Liu提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中的路、圈的性质。我们继续对拟阵圈图的性质进行了研究,着重研究了拟阵圈图的边、点容错哈密尔顿性。一个拟阵M就是对于一个有限集E,令C为集合E中非空子集族,它满足如下的公理:(C1)(?)C.(C2)若C1,C2∈C且C1(?)C2,则C1=C2。(C3)若C1≠C2,C1,C2∈C并且存在e∈C1∩C2,则恒有C3∈C满足C3(?)(C1(?) C2)-e.那么我们称M=(E,C)为定义在元素集E上的拟阵。当C∈C(M),我们称C为M的一个圈。如果M的一个圈只有一个元素,则称之为M的一个环。如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元。如果M既没有环也没有平行元,则称M是一个简单拟阵。如果一个元素含在M的任一基中,则称之为M的一个反圈。如果S是E的一个子集,且对任意的圈C,都有C(?)S或者C(?)E\S.则称S为M的一个分离集.显然E和(?)都是M的分离集。^M的极小分离集称为M的一个分支。如果拟阵M只有一个分支,则称"为连通拟阵.设e∈E,则M/e和M\e分别表示由拟阵M经过收缩和约束e后所得到的拟阵。拟阵M=(E,B)的基图是这样的一个图G,其中V(G)=B,E(G)={B1B2|B1,B2∈B,|B,\B2|=1},这里图G的顶点和M的基用同样的符号表示。设G是一个图,图G的点集和边集分别记为V(G)和E(G),令v(G)=|V(G)|。包含G的每个点的路称为G的一条哈密尔顿路;同样的,包含G的每个点的圈称为G的一个哈密尔顿圈。如果一个图存在一个哈密尔顿圈,则称之为哈密尔顿的。如果对于一个图G的任意两个顶点来说,G都有-条哈密尔顿路连接他们,则称G是哈密尔顿连通的。如果对一个图G的任意一条边来说,G都有一个含这条边的哈密尔顿圈,则称G是边哈密尔顿的,或者称G是正哈密尔顿的,写作G∈H+。如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密尔顿圈,则称G是负哈密尔顿的,写作G∈H-。如果G既是正哈密尔顿的,又是负哈密尔顿的,我们称G是一致哈密尔顿的。如果对于图G的任意两条边,均存在一一个哈密尔顿圈包含他们,这个图G就被称为Ez-哈密尔顿的。一个图G被称为k-点容错哈密尔顿的,如果在任意删除不多于k个顶点以后,图仍然是哈密尔顿的,即在余图中仍然存在哈密尔顿圈。类似的,个图G被称为k-边容错哈密尔顿的,如果在任意删除不多于k条边以后,图仍然是哈密尔顿的。现在我们给出拟阵圈图的概念。定义拟阵M的圈图G=G(M)的顶点集V(G)=C,边集E(G)={CC′|C,C′∈C,|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈。对于一个图G=(V,E),它的一个t-顶点染色,或者t-染色,是指图G的一个从顶点集V到颜色集{1,2…,t}的映射c。如果染色c对于G中的每一条边uu都满足c(u)≠c(u),则称染色c是G的一个正常t-顶点染色且G是可t-染色的.在染色c下,具有相同颜色的顶点构成的集合称为一个色类。如果图G的某个t-顶点染色c的每个色类在G中都能导出一个最大度至多为k的森林,则称c是图G的一个k-森林t-染色。如果G的一个正常t-顶点染色c的任意两个色类的基数之差的绝对值至多为1,则称c是图G的均匀t-顶点染色。图的强均匀染色数χeq*(G)是这样一个整数t的最小值,它使得图G对于每个不小于t的整数t’,都具有一个均匀t’-染色。关于图的强均匀染色数,有一个着名的Chen-Lih-Wu猜想(又称为均匀△-染色猜想),它认为,如果图G是一个连通图,并且G既不是完全图,也不是奇圈,还不是完全二分图K2m+1,2m+1,则χeq*(G)≤△(G)。本文主要研究的是拟阵圈图的边容错哈密尔顿性,点容错哈密尔顿性以及一般图的森林均匀染色问题,全文共分为四章。第一章给出了一个相对完整的简介。首先介绍一些图论中的基本术语和定义,然后给出了关于树图,拟阵基图以及森林图的一个简短但相对完整的综述,最后,给出了本文的主要结论。第二章我们研究了拟阵圈图中的哈密尔顿圈性质。首先我们给出了一个对于拟阵圈图的简短的介绍。然后我们证明了拟阵圈图的E2-哈密尔顿性。在这一章的最后,我们讨论了拟阵圈图的边容错哈密尔顿性。第叁章主要讨论拟阵圈图的点容错哈密尔顿性。同样的,首先,给出了对于拟阵圈图容错哈密尔顿性的一个简短的介绍。然后我们讨论了拟阵圈图的点容错哈密尔顿性,并给出证明。第四章主要讨论一般图的森林均匀染色问题。在这一章里,我们首先给出了对于均匀染色的一个简短的介绍。之后,我们讨论了一般图的森林均匀染色问题,并且给出了一个多项式时间算法去构建这样的染色。(本文来源于《山东大学》期刊2013-01-23)
李萍[2](2010)在《拟阵圈图的一些性质》一文中研究指出图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图.为了研究拟阵中圈图的性质,我们提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中圈的性质,路的性质,并且把圈图的概念推广为n阶圈图,并得到了n阶圈图的一些性质。设E是一个有限集.如果S1,S2(?)E,那么S1-S2={χ(?)χ∈S1和x(?)S2}.一个拟阵M就是一个有限集E以及E的一个非空子集族(?),且满足以下条件:(C1)若C1,C2∈(?)且C1(?)C2,则C1=C2.(C2)设C1,C2∈(?)并且a,b∈E.若a∈C1∩C2且b∈C1-C2,则存在C3∈(?)满足b∈C3(?)(C1∪C2)-{a}.当C∈(?)(M),我们称C为M的一个圈.如果M的一个圈只有一个元素,则称之为M的一个环.如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元.如果M既没有环也没有平行元,则称M是一个简单拟阵.如果一个元素含在M的任一基中,则称之为M的一个反环.如果S是E的一个子集,且对任意的圈C,都有C(?)S或者C(?)E\S.则称S为M的一个分离集.显然E和(?)都是M的分离集.M的极小分离集称为M一个分支.如果拟阵M只有一个分支,则称M为连通拟阵.设e∈E,则M·e和M△e分别表示由拟阵M经过收缩和删除e后所得到的拟阵.拟阵M=(E,(?))的基图是这样一个图G,其中V(G)=(?),E(G)={B1B2:B1,B2∈(?),且|B1\B2|=1},这里图G的顶点和M的基用同样的符号表示.设G是一个图,图G的点集和边集分别记为V(G)和E(G),令v(G)=|V(G)|.包含G的每个点的路称为G一条哈密顿路;同样地,包含G的每个点的圈称为G一个哈密顿圈.如果个图存在一个哈密顿圈,则称之为哈密顿的.如果对一个图G的任意两个顶点来说,G都有一条哈密顿路连接它们.则称G是哈密顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密顿圈,则称G是边哈密顿的,或者称G是正哈密顿的,记为G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密顿圈,则称G是负哈密顿的,记为G∈H-.如果G既是正哈密顿的,又是负哈密顿的,我们称G是一致哈密顿的。一个有n个顶点的图G称为顶点泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一个顶点,G都存在一个过该顶点的长度为k的圈.一个有n个顶点的图G称为边泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一条边,G都存在一个长度为k的圈包含这条边.现在我们给出拟阵圈图的概念.定义拟阵M的圈图G=G(M)的顶点集V(G)=(?),边集E(G)={CC′|C,C′∈(?),|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈.定义拟阵M的k阶圈图Ck(M)的顶点集为V(Ck(M))=(?)(M).两个顶点C,C′∈(?)(M)在Ck(M)中相邻当且仅当在M中|C∩C′|≥k.为了符号表示方便,我们既用C表示Ck(M)的顶点,也用C表示M中的圈.本文分为五章.第一章给出关于树图,拟阵基图以及森林图的一个简短但相对完整的综述.第二章给出拟阵圈图的概念,并讨论拟阵圈图的连通度和边连通度.第叁章我们深入讨论了拟阵圈图的哈密顿性,边泛圈性以及圈图中顶点不交圈的性质.第四章讨论了拟阵圈图中路的性质.第五章我们给出了拟阵的圈图的定义,并讨论了它的直径和连通度.下面列出本文的主要结果.结论1设G=G(M)是一个连通拟阵M的圈图,而且B是M的一个基,则G的连通度k(G)≥2|E-B|-2.结论2设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则δ(G)≥2|E-B|-2.结论3设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则G的边连通度k′(G)=δ(G).结论4设G=G(M)是一个连通拟阵M的圈图,而且M含有至少叁个圈,则G=G(M)是边泛圈的.结论5设G=G(M)是一个连通拟阵M的圈图,而且M含有至少四个圈,则G是一致哈密顿的.结论6设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且k1+k2+…+kp=n(ki为整数,ki≥3,i=1,2,…,p),则G有一个2-因子F包含p个顶点不交的圈D1,D2,…,Dp而且圈Di的长度为ki(i=1,2,…,p).结论7设G=G(M)是一个连通拟阵M的圈图,而且M含有至少叁个圈,则G的直径不超过2.并且,d(G(M))=2当且仅当M中有两个没有公共元素的圈.结论8设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且C1,C2∈V(G),则对于任意的k满足2≤k≤n-1,存在一条长度为k的路连接C1和C2.结论9设M是一个连通简单拟阵.则如下结论成立.(ⅰ)C2(M)是连通的.(ⅱ)如果M没有一个约束子拟阵同构于U2,6,则在C2(M)中任何两个不相邻的顶点C1和C2有一个公共邻点C3.(ⅲ)C2(M)的直径不超过2当且仅当对于任何边集合X(?)E,M在X上的约束子拟阵都不同构于U2,6.结论10设M是一个包含至少两个圈的连通简单拟阵,且M不是一条线,则C2(M)是2-连通的.(本文来源于《山东大学》期刊2010-04-10)
拟阵圈图论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图.为了研究拟阵中圈图的性质,我们提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中圈的性质,路的性质,并且把圈图的概念推广为n阶圈图,并得到了n阶圈图的一些性质。设E是一个有限集.如果S1,S2(?)E,那么S1-S2={χ(?)χ∈S1和x(?)S2}.一个拟阵M就是一个有限集E以及E的一个非空子集族(?),且满足以下条件:(C1)若C1,C2∈(?)且C1(?)C2,则C1=C2.(C2)设C1,C2∈(?)并且a,b∈E.若a∈C1∩C2且b∈C1-C2,则存在C3∈(?)满足b∈C3(?)(C1∪C2)-{a}.当C∈(?)(M),我们称C为M的一个圈.如果M的一个圈只有一个元素,则称之为M的一个环.如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元.如果M既没有环也没有平行元,则称M是一个简单拟阵.如果一个元素含在M的任一基中,则称之为M的一个反环.如果S是E的一个子集,且对任意的圈C,都有C(?)S或者C(?)E\S.则称S为M的一个分离集.显然E和(?)都是M的分离集.M的极小分离集称为M一个分支.如果拟阵M只有一个分支,则称M为连通拟阵.设e∈E,则M·e和M△e分别表示由拟阵M经过收缩和删除e后所得到的拟阵.拟阵M=(E,(?))的基图是这样一个图G,其中V(G)=(?),E(G)={B1B2:B1,B2∈(?),且|B1\B2|=1},这里图G的顶点和M的基用同样的符号表示.设G是一个图,图G的点集和边集分别记为V(G)和E(G),令v(G)=|V(G)|.包含G的每个点的路称为G一条哈密顿路;同样地,包含G的每个点的圈称为G一个哈密顿圈.如果个图存在一个哈密顿圈,则称之为哈密顿的.如果对一个图G的任意两个顶点来说,G都有一条哈密顿路连接它们.则称G是哈密顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密顿圈,则称G是边哈密顿的,或者称G是正哈密顿的,记为G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密顿圈,则称G是负哈密顿的,记为G∈H-.如果G既是正哈密顿的,又是负哈密顿的,我们称G是一致哈密顿的。一个有n个顶点的图G称为顶点泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一个顶点,G都存在一个过该顶点的长度为k的圈.一个有n个顶点的图G称为边泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一条边,G都存在一个长度为k的圈包含这条边.现在我们给出拟阵圈图的概念.定义拟阵M的圈图G=G(M)的顶点集V(G)=(?),边集E(G)={CC′|C,C′∈(?),|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈.定义拟阵M的k阶圈图Ck(M)的顶点集为V(Ck(M))=(?)(M).两个顶点C,C′∈(?)(M)在Ck(M)中相邻当且仅当在M中|C∩C′|≥k.为了符号表示方便,我们既用C表示Ck(M)的顶点,也用C表示M中的圈.本文分为五章.第一章给出关于树图,拟阵基图以及森林图的一个简短但相对完整的综述.第二章给出拟阵圈图的概念,并讨论拟阵圈图的连通度和边连通度.第叁章我们深入讨论了拟阵圈图的哈密顿性,边泛圈性以及圈图中顶点不交圈的性质.第四章讨论了拟阵圈图中路的性质.第五章我们给出了拟阵的圈图的定义,并讨论了它的直径和连通度.下面列出本文的主要结果.结论1设G=G(M)是一个连通拟阵M的圈图,而且B是M的一个基,则G的连通度k(G)≥2|E-B|-2.结论2设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则δ(G)≥2|E-B|-2.结论3设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则G的边连通度k′(G)=δ(G).结论4设G=G(M)是一个连通拟阵M的圈图,而且M含有至少叁个圈,则G=G(M)是边泛圈的.结论5设G=G(M)是一个连通拟阵M的圈图,而且M含有至少四个圈,则G是一致哈密顿的.结论6设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且k1+k2+…+kp=n(ki为整数,ki≥3,i=1,2,…,p),则G有一个2-因子F包含p个顶点不交的圈D1,D2,…,Dp而且圈Di的长度为ki(i=1,2,…,p).结论7设G=G(M)是一个连通拟阵M的圈图,而且M含有至少叁个圈,则G的直径不超过2.并且,d(G(M))=2当且仅当M中有两个没有公共元素的圈.结论8设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且C1,C2∈V(G),则对于任意的k满足2≤k≤n-1,存在一条长度为k的路连接C1和C2.结论9设M是一个连通简单拟阵.则如下结论成立.(ⅰ)C2(M)是连通的.(ⅱ)如果M没有一个约束子拟阵同构于U2,6,则在C2(M)中任何两个不相邻的顶点C1和C2有一个公共邻点C3.(ⅲ)C2(M)的直径不超过2当且仅当对于任何边集合X(?)E,M在X上的约束子拟阵都不同构于U2,6.结论10设M是一个包含至少两个圈的连通简单拟阵,且M不是一条线,则C2(M)是2-连通的.
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
拟阵圈图论文参考文献
[1].樊昊.拟阵圈图的性质和图的染色问题[D].山东大学.2013
[2].李萍.拟阵圈图的一些性质[D].山东大学.2010