6连通图完美匹配上的可收缩边

采用分类讨论的方法,研究了6-连通图中可收缩边在完美匹配上的分布情况,得到了如下新结果.设G是阶大于12的6-连通图,M是G的一个完美匹配,若图G的任意断片的阶都大于3,则M上至少有2条可收缩边.     

k-连通图的可收缩边

证明了对k-连通图G,若G的任意一个断片满足当N(F)中含有边就有|F|k/4,则G至少有2条可收缩边.     

极小k-连通图中的k-可收缩边

Ando 证明了如果G是极小的k-连通图,且G中不含有K1 C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任-k度点x,都存在与x关联的不在三边形中的边,那么G中有k-可收缩边.     

k-连通图中最长圈上可收缩边的数目

给出了k-连通图中最长圈上的可收缩边的数目,得到如下结果:任意断片的阶至少为「k/2+1 的k-连通图中最长圈上至少有3 条可收缩边;更进一步,若该k-连通图中存在哈密顿圈,则哈密顿圈上至少有6 条可收缩边。     

k-树图的收缩边

Narayanaswamy,Sadagopan和Sunil Chandran证明了k-树图G可收缩边数目的下界为V(G)+k-2,并指出这个界是紧的.该文给出了k-树图G可收缩边数目更一般的下界,由该文的结果可以推出Narayanaswamy等人的结果,进一步证明了可收缩边数目恰好为V(G)+k-2的图的特征.     

n连通图的可收缩边

ｎ连通图的可收缩边，人们分别在图中无三角形及图Ｇ的最小度≥３／２ｎ－１时等情况中，给出了边数下界，利用边断片给出了ｎ连通图在边原子阶≥ｎ／２时可收缩边的下界，进而给出在最小度≥４／３ｎ－１时的边数下界。     

5连通图的分裂和可收缩边

引入5连通图中度为5的顶点的分裂,利用分裂和收缩的运算对某类5连通图进行归纳,证明了对于阶至少为7的5连通图G,当G的任一断片的阶不等于2,且对G的任一5度顶点z,G[NG(z)]中含子图(K2∪2K1)+K1,则对G的任意顶点x,下列断言之一成立:1)x关联一条可收缩边;2)在NG(x)中存在一个5度顶点y关联一条可收缩边;3)在NG(x)中存在一个5度顶点y,使得对y作某一个分裂运算所得的图是5连通的.     

3连通图生成树上的可去边

摘要：设G是3连通图，e是G中的一条边．若G—e是3连通图的一个剖分．则称e是3连通图G的可去边．否则，称e是G的不可去边．本文给出某些3连通图的生成树上可去边的分布情况及数目。     

5-连通图的可收缩边的分布

图的可收缩边问题对于研究图的结构和证明图的某些性质有着重要作用。本文给出了5-连通图中某些最长圈可收缩边的分布情况,用树型结构理论进行分类讨论,得到如下结论:不含2-断片的5-连通图的最长圈上至少有三条可收缩边。     

某些5-连通图中最长圈上的可收缩边

给出某些5-连通图中某些最长圈上的可收缩边的分布情况,得到如下结果:某些5-连通图的某些最长圈上至少有两条可收缩边。     

具最小度距离的完美匹配单圈图

证明了k≥11时,2k(k∈N)阶具完美匹配的单圈图的最小度距离图是由一个三角形并在三角形一个顶点粘上k-2条长度为2的路和一条悬挂边构成的.     

基于最小生成树的立体匹配算法

在传统的局部立体匹配算法中,代价聚合要对相关邻域内的点进行加权聚合,这种方式计算量大,非常耗时。文章提出一种基于最小生成树的立体匹配算法,该方法将图论中的最小生成树引入代价聚合和视差细化中,使得图像中所有点都对兴趣点进行聚合支持,弥补了局部算法在弱纹理区误匹配率高的局限性,提高了匹配的准确性,并且最小生成树能够对图像所有点进行层次性的划分,极大地简化了计算量。实验证明,该算法能够快速得到平滑且精度高的视差图。     

Δ(G)≤3的具有完美匹配的单圈图的能量下界

讨论了Δ(G) ≤ 3的具有完美匹配的单圈图G的能量问题 ,给出了该类图的能量的一个紧的下界     

切比雪夫多项式与循环图中生成树的个数

生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量.利用切比雪夫多项式的性质推出了循环图中计算生成树个数的在线性时间内即可实现的方法,并讨论了渐进特性.     

极大欧拉生成子图边数的几个定理

利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 .     

附有条件的最小支撑树算法

传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。