相邻叶边交换森林图的连通性

一、邻接叶边交换森林图的连通性（论文文献综述）

张英豪^[1]（2014）在《拟阵基的交图的性质》文中认为图论和拟阵理论在二十世纪经历了空前的发展.图论起源于着名的哥尼斯堡七桥问题.在图论的历史中,还有一个最着名的问题-四色问题.四色问题又称四色猜想,是世界近代三大数学难题之一.四色猜想的提出来自英国.1852年,毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时,发现了一种有趣的现象：”看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色.”1872年,英国当时最着名的数学家Cayley正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题.世界上许多一流的数学家都纷纷参加了四色猜想的大会战.1878-1880年两年间,着名律师兼数学家Kapel和Taylor两人分别提交了证明四色猜想的论文,宣布证明了四色定理.但后来数学家Heawood以自己的精确计算指出肯普的证明是错误的.不久, Taylor的证明也被人们否定了.于是,人们开始认识到,这个貌似容易的题目,其实是一个可与费马猜想相媲美的难题.二十世纪三十年代,Whitney在他的论文中,作为对矩阵和向量的独立性的抽象概括,首次提出了拟阵的概念.同时,拟阵也抽象了很多图的性质.拟阵理论为组合优化问题和设计多项式算法提供了强有力的工具.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图类为了研究拟阵中圈的性质,P.Li和G.Liu提出了拟阵圈图的概念,并且研究了拟阵圈图的连通度,圈图中的路和圈的性质.为了进一步研究拟阵中基的性质,Y.Zhang和G.Liu提出了拟阵基的交图的概念.设G是一个图,图G的点集和边集分别记为V（G）和E（G）.包含G的每个点的路称为G的一条哈密尔顿路；同样的,包含G的每个点的圈称为G的一个哈密尔顿圈.如果一个图存在一个哈密尔顿圈,则称之为哈密尔顿的.如果对于一个图G的任意两个顶点来说,G都有一条哈密尔顿路连接他们,则称G是哈密尔顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密尔顿圈,则称G是边哈密尔顿的,或者称G是正哈密尔顿的,写作G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密尔顿圈,则称G是负哈密尔顿的,写作G∈H-.如果G既是正哈密尔顿的,又是负哈密尔顿的,我们称G是一致哈密尔顿的.一个拟阵M就是对于一个有限集E,令I为集合E中非空子集族,它满足如下的条件：（I1）（?）∈I（12）若I2∈I且I1（?）I2,则I1∈I;（13）若I1,I2∈I并且|I1|<|I2|,则存在e∈I2I1,使得I1∪{e}∈I.那么我们称M=（E,I）为定义在有限集E上的拟阵.当I∈Z（M）,我们称I为M的一个独立集.对于不在Z中E的子集,我们称之为相关集.极小的相关集称为拟阵的圈,我们可以用拟阵的圈集合去定义拟阵.令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的一个极大独立集被称为拟阵M的基,表示为B（M）.拟阵M中一个基B（M）的元素个数定义为拟阵M的秩.令B（M）表示拟阵M中基的集合.同样我们也可以用拟阵的基来定义拟阵：（B1）所有的基的基数相同；（B2）如果B1,B2∈B且x∈B1,则存在y∈B2,使得（B1{x}）∪{y}∈B.拟阵M=（E,B）的基图是这样的一个图G,其中V（G）=B,E（G）={BB’|B,B’∈B,|BB’|=1},注意在这里图G的顶点和M的基用同样的符号表示.现在我们给出拟阵基的交图的概念.定义拟阵M的基的交图G=G（M）的顶点集V（G）=B,边集E（G）={BB’|B,B’∈B,|B∩B’|≠0}这里B和B’既代表G的顶点,也代表M的基.下面我们给出整数流,也就是处处非零的k-流的定义：给定一个图G,设D为图G的一个方向,设函数f:E（G）→Z,使得-k<f（e）<k,对于任意的e∈E（G）都成立.序偶（D,f）称为图G的k-流,如果对于任意的u∈V（G）,它满足平衡条件：其中,E+（v）和E-（v）分别表示方向在点上出边的集合和入边的集合.一个k-流（D,f）是处处非零的（或简称为k-NZF）如果f（e）≠0,对于任意的e∈E（G）都成立.设图G是无向图,A是一个非平凡的阿贝尔加群（单位元为0）,A*是A中非零元素所构成的集合.我们定义F（G,A）={f|f:E（G）→4)和F*（G,A）={f|f:E（G）→A*).对于每一个f∈F（G,A）,f的边界函数（?）f（v）:V（G）→A的定义如下：其中“∑”指的是阿贝尔群里的加法.我们定义一个图G的处处非零A-流（简称A-NZF）指的是一个函数f∈F*（G,A）使得（?）f=0成立.如果一个图G有一个处处非零的k-流当且仅当图G有一个处处非零的Zk-流.对于任意的b∈Z（G,A）,如果有一个函数f∈F*（G,A）使得af=b成立,那么我们称f是一个处处非零（A,b）-流（简称（A,b）-NZF）.Jaeger等人推广了整数流的概念,提出了A-连通的概念,一个无向图G称为A-连通的,如果G的每一个定向G’对于每一个函数b∈Z（G’,A）,都存在一个（A,b）一NZF,记作G∈（A）.同样的,G有A-NZF当G有定向G’使得G’有A-NZF.A-连通性的概念是Jaeger等人在[31]中提出的,A-NZF与A-连通性有密切关联.本文主要研究的是拟阵基的交图的一致哈密尔顿性,边不交的哈密尔顿圈个数,图中顶点不交的圈以及拟阵基图的整数流性质,全文共分为四章.第一章给出了一个相对完整的简介.首先介绍一些图论中的基本术语和定义,然后给出了关于树图,拟阵基图以及森林图的一个简短但相对完整的综述,并介绍了拟阵基的交图和整数流的研究现状,最后,给出了本文的主要结论.第二章我们研究了拟阵基的交图中的哈密尔顿圈.首先我们给出了一个对于拟阵基的交图的简短的介绍.然后我们证明了拟阵基的交图的一致哈密尔顿性,接着我们还继续证明了简单拟阵的拟阵基的交图有两条边不交的哈密尔顿圈.第三章主要讨论拟阵基的交图中顶点不交的圈的性质.同样的,首先,给出了对于拟阵基的交图的一个简短的介绍.然后我们讨论了拟阵基的交图中的顶点不交的圈的一些性质,并给出证明.第四章主要讨论拟阵基图的整数流问题.在这一章里,我们首先给出了对于整数流和群连通度的一个简短的介绍以及一些已知的结论.之后,我们讨论了拟阵基图的群连通性以及拟阵基图上的处处非零的3-流,我们证明了简单拟阵的拟阵基图上有处处非零的3-流.

樊昊^[2]（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-哈密尔顿性。在这一章的最后,我们讨论了拟阵圈图的边容错哈密尔顿性。第三章主要讨论拟阵圈图的点容错哈密尔顿性。同样的,首先,给出了对于拟阵圈图容错哈密尔顿性的一个简短的介绍。然后我们讨论了拟阵圈图的点容错哈密尔顿性,并给出证明。第四章主要讨论一般图的森林均匀染色问题。在这一章里,我们首先给出了对于均匀染色的一个简短的介绍。之后,我们讨论了一般图的森林均匀染色问题,并且给出了一个多项式时间算法去构建这样的染色。

徐鑫^[3]（2012）在《拟阵基图的一些性质》文中进行了进一步梳理图论和拟阵理论在二十世纪经历了空前的发展。图的支撑图及拟阵的基图都是组合理论的基本研究对象。一个连通图的树图能够反映该图的不同支撑树之间的变换关系。因此,研究一个图的树图有助于我们更好地了解该图的性质。同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系。因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质。近些年来,树图和拟阵的基图被推广得到了一些新的图。一个拟阵就是一个有限元素的集合E以及E的子集族B构成的系统,并且满足以下条件：对于任意的B1，B2∈B,则|B1|=|B2|,并且对于任一的x∈B1,存在一个元素y∈B2,使得(B1{x}∪{y}∈B,记作M=（E,B）。其中B的每一个元素称为拟阵的基。拟阵M中一个基的任何子集都是M的一个独立集,特别地空集是独立集。如果C（?）E不是一个独立集,并且任何C的子集都是独立集,则称C为M的一个圈。如果M的一个圈只有一个元素,那么这个元素称为M的环.如果两个元素的集合{x.y}是M的一个圈,称{x.y}为一对平行元。如果M既没有环也没有平行元,则称M为一个简单拟阵。如果一个元素含在M的任意一个基中,则称之为M的一个反环。对于任意e（?）B,B+e包含唯一一个圈,称之为基本圈。拟阵的秩是基中元素的个数,余秩是拟阵基本圈的个数。如果S是E的一个子集,且对任意的圈C,都有C（?）S或者C（?）ES,则称S是M的一个分离集.显然E和（?）都是M的分离集。M的极小分离集称为M的一个分支.如果拟阵M只有一个分支,则称M为连通拟阵。设e∈E,则M/e和Me分别表示由M通过收缩和删除e后得到的拟阵。拟阵M的子拟阵是拟阵M通过有限步的收缩、删除变换后得到的拟阵。拟阵的基图G=G（M）是以M,的基集B为顶点集的图,基图的边集定义为E（G）={BB’：B,B’∈B,且|BB’|=1}。这里图G的点与拟阵M的基用同样的符号表示。设G是一个图,图G的点集和边集分别记为V（G）和E（G）,令v（G）=|V（G）|。包含G的每个点的路称为G的一条哈密顿路；同样的,包含G的每个点的圈称为G的一个哈密顿圈。如果一个图存在一个哈密顿圈,则称图为哈密顿的。如果对于图的任意两个顶点,都有一条哈密顿路连接它们,那么称G是哈密顿连通的。如果对于图G的任意一条边,G都有一个含这条边的哈密顿圈,则称G是边哈密顿的,或者称G是正哈密顿的,记作G∈H+。如果对于一个图G的任意一条边来说,G都有一个不包含这条边的哈密顿圈,则称G是负哈密顿的,记作G∈H-。如果G既是正哈密顿的,又是负哈密顿的,我们称G是一致哈密顿的。如果G的任意两条边都在G的一个哈密顿圈中,称G是E2-哈密顿的。设G是一个阶不少于3的简单图,若G的每条长为2的路都包含在G的一个哈密顿圈中,则称G是P3-哈密顿的。若对G的每一对顶点τ1和τ2以及任意一条边v2v3（其中τ1≠υ3）来说,G都存在一条从v1到v2的经过边v2v3的哈密顿路,则称G是1-哈密顿连通的。用M5表示有5个顶点的轮。对于一个图G,如果对于任意的子集F（?）V（G）,其中|F|≤f,使得图G—F仍然是哈密顿圈的,那么称图G是f-顶点容错哈密顿的。同样的,我们可以定义∫-顶点容错边哈密顿的、∫-顶点容错哈密顿连通的。本文分为三章,第一章给出树图、森林图、拟阵基图的一个简短但相对完整的综述。第二章讨论拟阵基图的哈密顿性,一致哈密顿性。第三章讨论容错性条件下拟阵基图的一些哈密顿性质。下面列出本文的主要结果：结论1设M=（E,B）是一个简单拟阵, G=G（A,）是拟阵M的基图。如果|V（G）|≥5并且M中任何子拟阵的基图不同构于W5,则对于图G中任意两条边e和e’,存在一个包含e,不包含e’的哈密顿圈。结论2设G=G（M）是拟阵M的基图,|V（G）|≥4.如果有M（?）N,其中N表示每一个分支都是平行元或反环且至少有两对平行元的拟阵组成的集合,则M的基图G（M）是1-顶点容错哈密顿的。结论3设M=（E，B）是简单拟阵,G（M）是拟阵M的基图,且有|V（G）|≥4,那么G（M）是1-顶点容错边哈密顿的。结论4设M=（E,B）是简单拟阵,G（M）是拟阵M的基图,且有|V（G）|≥3,那么G（M）是1-顶点容错哈密顿连通的。结论5设M=（E，B）是简单拟阵,G（M）是拟阵M的基图,且有|V（G）|≥5,那么G（M）是2-顶点容错哈密顿的。

李萍^[4]（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-连通的.

刘晓妍,李乐学^[5]（2006）在《拟阵基关联图中的路》文中进行了进一步梳理证明了如果M=（E,B）是一个简单拟阵,拟阵M的秩ρ=ρ（M）至少为2,E中的每一个元素都包含在M的某一个圈中,Δ（M）=Δ（E,B,F）为拟阵M的基关联图,则Δ（M）中存在一条路P,使得P覆盖E中的所有元素.

李乐学,刘桂真^[6]（2004）在《邻接叶边交换森林图的连通性》文中研究表明证明了若图G是 2 连通的 ,则图G的邻接叶边交换森林图是连通的 .

二、邻接叶边交换森林图的连通性（论文开题报告）

（1）论文研究背景及目的

此处内容要求：

首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。

写法范例：

本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。

（2）本文研究方法

调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。

实证研究法：依据现有的科学理论和实践的需要提出设计。

定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。

定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。

跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。

模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

三、邻接叶边交换森林图的连通性（论文提纲范文）

（1）拟阵基的交图的性质（论文提纲范文）

（2）拟阵圈图的性质和图的染色问题（论文提纲范文）

（3）拟阵基图的一些性质（论文提纲范文）

（4）拟阵圈图的一些性质（论文提纲范文）

（5）拟阵基关联图中的路（论文提纲范文）

（6）邻接叶边交换森林图的连通性（论文提纲范文）

四、邻接叶边交换森林图的连通性（论文参考文献）

• [1]拟阵基的交图的性质[D]. 张英豪. 山东大学, 2014(10)
• [2]拟阵圈图的性质和图的染色问题[D]. 樊昊. 山东大学, 2013(10)
• [3]拟阵基图的一些性质[D]. 徐鑫. 山东大学, 2012(02)
• [4]拟阵圈图的一些性质[D]. 李萍. 山东大学, 2010(09)
• [5]拟阵基关联图中的路[J]. 刘晓妍,李乐学. 山东大学学报(理学版), 2006(02)
• [6]邻接叶边交换森林图的连通性[J]. 李乐学,刘桂真. 山东大学学报(理学版), 2004(06)

标签：哈密顿论文;  连通图论文;  图论论文;