学位论文 > 优秀研究生学位论文题录展示

关于赋权图中重圈的一个范型定理

作　者: 余荣
导　师: 胡智全
学　校: 华中师范大学
专　业: 运筹学与控制论
关键词: 拟正规赋权图重路哈密尔顿圈权度
分类号: O157.5
类　型: 硕士论文
年　份: 2005年
下　载: 26次
引　用: 0次
阅　读: 论文下载

内容摘要

设G=（V,E;ω）为赋权图,定义G中点v的权度d_G^ω（v）为G中与v相关联的所有边的权和,图G中圈的权值定义为圈中所有边的权和。范更华[7]中证明了下述众所周知的结论:设G是n阶2-连通图,c是满足3≤c≤n的一个整数。如果对任意的u,v∈V（G）, d（u,v）=2（?）max{d（u）,d（v）}≥c/2, 那么G中存在哈密尔顿圈或者存在一个长度至少为c的圈。Bedrossian等人[1]和Zhang等人[12]中分别将上述范定理进行了推广。本文将范定理更进一步推广为: 假设G是满足下述条件的2-连通赋权图, （1）对G中每一个与K_1,3同构的导出子图T,T中所有边的权都相等; （2）对G中每一个与K_1,3+e同构的导出子图T,T中所有边的权都相等; （3）对G中每一个与K_1,3或者与K_1,3+e同构的导出子图T, min{max{d_G^ω（x）,d_G^ω（y）}:d（x,y）=2,x,y∈V（T）}≥c/2。那么,G中存在哈密尔顿圈或者存在一个权值至少为c的圈。此外,我们还证明了该定理中的条件（1）和（2）是不能被减弱为条件（1）或条件（2）的。

全文目录

摘要  4-5
Abstract  5-8
第一节引言  8-12
  1．1 研究背景和现状  8
  1．2 定义  8-10
  1．3 已知结论  10-11
  1．4 主要结论  11-12
第二节结构引理  12-16
  2．1 引理1  12
  2．2 引理2  12-16
第三节主要结论的证明  16-36
  3．1 引理3  16-35
  3．2 定理4的证明  35-36
第四节主要结论的最好可能性  36-38
第五节后记  38-39
参考文献  39-41
致谢  41

关于赋权图中重圈的一个范型定理

内容摘要

全文目录

相似论文