论文部分内容阅读
本文主要研究图论及其应用中两个方面的问题：1、缺省n-可扩图：2、求赋权Halin图任意给定两点之间最优Hamilton路的有效算法。
论文的第一章介绍了文中所涉及的相关概念和术语、对可扩图的研究现状和对Halin图Hamilton性的研究现状，并以此为背景引入论文研究的对象：缺省n-可扩图和Halin图的OHP问题。
论文的第二章到第五章对缺省n-可扩图进行了多角度的研究。主要结论可概括为以下五部分：
1.解决了缺省，n-可扩图连通度的取值范围问题，证明缺省n-可扩图的连通度可以取任意自然数。而Plummer[1]证明了n-可扩图的连通度至少为n+1，故缺省，n-可扩图在连通度方面比n-可扩图更复杂。
2.分别刻画了连通度为1，连通度不小于2和连通度不小于n的缺省n-可扩偶图并给出连通度取值不同的缺省，n-可扩偶图的若干性质。得到：
定理2.2.1：设偶图G=(U,W)满足：|W|=|U|+1和κ(G)=1。设x是G的割点，H=(X,Y)是G-x的一个分支并且正整数n≤(|V(G)|-2)/2，则G是缺省n-可扩图当且仅当下面语句成立：
(1)‖X|-|Y‖≤1；
(2)G-x只有两个奇分支而没有偶分支或者G-x的所有分支都是偶分支；
(3)若|X|=|Y|=m，则H是s-可扩图并且G[V(H)∪{x}]是缺省t-可扩图，其中s=min{n-1，m-1}并且t=min{n,m-1}；
(4) 若|X|=|Y|+1=m+1，则
(4.1)x∈U，Y U并且X W:
(4.2)若，m≥1，则H是缺省s-可扩图，其中s=min{n,m-1}；
(4.3)若顶点u满足u∈V(H)并且xu∈E(G)，则H-u的每个分支H’=(X’,Y’)是t-可扩图，其中m’=|X’|和t-=min{n-1，m’-1}；
(5)若G-x有奇分支并且对G-x中的任意一个分支H=(X,Y),其中|X|=|Y|+1都有：|Γ<,G>(x)∩V(H)|<|X|，则d<,G>(x)≥n+1。
定理2.3.5：若偶图G=(U,W)满足：κ(G)≥2，正整数n≤(|V(G)|-2)/2，则下列语句等价：
(1)G是缺省n-可扩图；
(2)‖W|-|U‖-1成立并且若|W|-|U|=1，则对所有S W并且2≤|S|≤|W|-n，有：Γ<,G>(S)≥|S|+n-1。
(3)对所有u<,1>u<,2>,...,u<,n>∈U和W<,1>，W<,2>,...,W<,n.∈W，都有：图G’=G-u<,1>-u<,2>-...-u<,n>-W<,1>-w<,2>-...-w<,n>有几乎完美对集。
定理2.3.11：设偶图G=(U,W)满足：k(G)≥n和|W|=|U|+1，正整数n≤(|V(G)|-2)/2)/2。G是缺省，n-可扩图当且仅当对所有w∈W,G-W的所有分支都是(n-1)-可扩图。
定理2.3.2：设n为正整数，偶图G=(U,W)是缺省n-可扩图并且|W|=|U|+1。则对所有w∈W,G-w的分支为k-可扩图，其中k=min{k(G)-1，n-1}。
定理2.4.2：设图G=(U,W)是缺省n-可扩偶图，其中|W|=|U|+1并且2≤k(G)≤n。若S是G的最小点割集，则下列结论成立：
(1)G-S有两个分支，其中一个分支是W中的一个顶点，另一个分支是偶图H=(X,Y)，并且，若逛X W,Y U,则|X|-|Y|=k(G)；
(2)S U。
3.研究极小缺省，n-可扩偶图的结构和最小度。一个缺省，n-可扩图G是极小的当且仅当对所有e∈E(G)，G-e不是缺省，n-可扩图。
论文第三章证明了极小缺省1-可扩图的最小度为1。并通过引入关键边和关键集的概念对连通度至少为2并且n≥2的极小缺省，n-可扩偶图的结构和最小度进行了研究。证明连通度至少为2并且n≥的缺省n-可扩偶图是极小的当且仅当图中所有边都是关键边，也证明了图中所有度数至少为n+2的顶点的导出子图为森林。此外，还得到连通度至少为2并且n≥2的极小缺省n-可扩偶图最小度的取值范围为[2,n+1]和连通度为1并且n≥的极小缺省，n-可扩偶图最小度的取值范围为[1，n+1]。并举图例证明当n≥，则对[2，n]中任意自然数s和对[1，n]中任意自然数t，存在连通度至少为2而最小度为s的极小缺省n-可扩偶图以及连通度为1和最小度为t的极小缺省n-可扩偶图。
4.从不同角度对缺省1-可扩偶图进行刻划，并根据其中一个刻划定理设计了一个判定缺省1-可扩偶图的算法。主要结论有：
定理4.1.1：设偶图G=(U,W)满足：|W|=|U|+1和|U|≥2。设u V(G)，图G’=G∪{u}u{顶点u与W中所有顶点相连的边}，则图G是缺省1-可扩图当且仅当G’是1-可扩图。
定理4.1.2：设偶图G=(U,W)满足：|W|=|U|+1和|U|≥2，则下面的语句等价：
(1)G是缺省1-可扩图；
(2)G只有一个最小点覆盖集U(3)对所有逛X U并且X≠φ，都有：|Γ<,G>(X)|≥|X|+1。
定理4.1.3：设偶图G=(U,W)满足：|W|=|U|+1和|U|≥2，M是G的一个几乎完美对集，w是G的M-非饱和顶点，则G是缺省1-可扩图当且仅当对所有v∈U,G中有一条M-交错路连接w和v。
此外，第四章引入了路径分解概念：设偶图G=(U,W)满足：|W|=|U|+1。若G=w+P<,1<+P<,2>+...+P<,r>,其中w∈W并且P<,i><1≤i≤r)满足下面两个条件之一：
(1)P<,i>是奇路径并且仅在两个端点处与G<,i-1>相交，其中G<,i-1>=w+P<,1>+P<,2>+...+P<,i-1>；
(2)P<,1>是起始于W∩G<,i-1>中一个顶点的偶路径，并且P<,i>与G<,i-1>没有其它交点，其中G<,i-1>=w+P<,1>+P<,2>+…+P<,i-1>：
则w+P<,1>+P<,2>+…P<,r>称为G的一个路径分解。并证明顶点数至少为5的偶图是缺省1-可扩当且仅当它有路径分解。该路径分解定理是对缺省1-可扩偶图结构的比较直观的描述。
5.刻划缺省n-可扩一般图和(2k+1)-临界图。若一个图至少有k+2个顶点并且删除该图中任意k个顶点，剩下的图都有完美对集，则该图为k-临界图。显然，(2k+1)-临界图是缺省k-可扩图。论文第五章利用M-交错路分别刻划了缺省，n-可扩一般图和(2k+1)-临界图。主要结论如下：
定理5.2.2：设图G有奇数个顶点，M是G的一个几乎完美对集，r是M非饱和顶点，正整数n≤(|V(G)|-2)/2。则下面两个语句等价：
(1)G是缺省n-可扩图；
(2)定义函数f(v)：V(G)→V(G)如下：
任选F M，其中|F|=r并且0≤r≤n。在G-V(F)中任选(n-r)条独立边x<,i’y<,i>’(1≤i≤n-r)满足：x<,i’y<,i>’M。设f(x<,i>’)=x<,i>和f(y<,i>’)=y<,i>,其中1≤i≤n-r。令Z=({x}∪{x<,1>,x<,2>,...,x<,n-r>,y<,1>,y<,2>,...,y<,n-r>}){x<,1>’,x<,2>’,....x<,n-r>’,y<,1>’y<,2>’,...,y<,n-r>’},显然，|Z|为奇数。不妨设|Z|=2m+1。若m≥1，则G-(V(F)∪-(V(F))∪{x<,1>,x<,2>,...,x<,n-r>,y<,1>,y<,2>,...,y<,n-r>’})中存在m条独立的M-交错路P<,1>，P<,2>,…P<,m>将Z中的顶点成对相连并且起始和终止于E(G)M中的边。
定理5.3.5：设图G有奇数个顶点且|V|(G)|≥2k+3，其中k是整数。M是G的几乎完美对集，x是G的M-非饱和顶点。则G是(2k+1)-临界图当且仅当下面语句成立：
(1) 任选G-x中2k个顶点x<,1>，x<,2>,...,x<,2>，G中存在k条独立M-交错路P<,1>，P<,2>,...,P<,k>将x<,1>，x<,2>,...,x<,2k>中的顶点成对相连并且P<,i>(i=1，2,...,k)起始与终止于M中的边；
(2) 任选G中2斛2个顶点：u<,1>(x)，u<,2>，…，u<,2k+2>,则G中存在k+1条独立的M-交错路P<,1>，P<,2>,...,P<,k+1>将u<,1>,u<,2>,...,u<,2k+2>中的顶点成对相连，其中，P<,1>起始于x，终止于{u<,2>,...,u<,2k+2>}中的一个顶点并且P<,1>的起始边在E(G)M中而终止边在M中：P<,i>(2≤i≤k+1)的起始边与终止边都在M中。
论文第六章利用递归压缩扇结构的方法，设计了一个求Halin图OHP问题的有效算法并证明其时间复杂度为O(|V|<3>)。