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

图的生成连通性及哈密尔顿连通指标

作 者: 依明江·沙比尔
导 师: 艾尔肯·吾买尔
学 校: 新疆大学
专 业: 应用数学
关键词: 生成连通度?幂图?哈密尔顿指标?哈密尔顿连通指标??单圈图
分类号: O157.5
类 型: 硕士论文
年 份: 2013年
下 载: 6次
引 用: 0次
阅 读: 论文下载
?

内容摘要


设G=(V, E)是一个连通图。图G是哈密尔顿的,如果它有一个哈密尔顿圈(包含G的所有的顶点的圈)。如果G的任意两个顶点之间存在一个哈密尔顿路(包含G的所有的顶点的路),则G称为哈密尔顿连通的。图G称为k连通的,如果G的任意两个顶点之间存在k条内部不交的路。连通度κ(G)是最小的正整数k,使得删掉G的k个顶点后G是不连通的。在本文中,我们研究幂图的生成连通性以及单圈图的哈密尔顿连通指标。图的生成连通性是连通性和哈密尔顿性的融合与推广。我们的主要结果是:(a).对于任意u,v∈V(G),--个k*-container C(u,v)是k-条内部不交的(u,v)-路的集合,使得C(u,v)包含G的所有顶点。G是k*-连通的,如果任意两个顶点之间存在一个k*-container.如果G是1*-连通的,那么G的生成连通度K*(G),是最大的正整数k,使得对所有的i:1≤i≤k,G是i*-连通的,否则生成连通度没有定义。图G的s-次幂,记作Gs,是定义在V(G)上的图,使得在Gs中两个顶点相连当且仅当它们在G中的距离不超过s。我们证明:如果G是一个|V(G)|≥k+1≥4的连通图,那么Gk是k*-连通的。(b).图G=(V(G),E(G))的线图L(G)是一个图,它以E(G)作为顶点集,且L(G)中两个顶点相连当且仅当相应的边在G中相邻。叠加线图递归地定义为L0(G)=G且Lk+1(G)=L(Lk(G))(k∈N,其中N表示自然数集)。图G的哈密尔顿指标h(G)(哈密尔顿连通指标hc(G))是使得G的叠加线图Lk(G)是哈密尔顿的(哈密尔顿连通的)最小的k。Chatrand和Wall给出了树的哈密尔顿指标的精确的计算公式。我们证明:对于树T,h(T)≤hc(T)≤h(T)+1,对于单圈图G有:h(G)≤hc(G)≤max{h(G)+1,k’+1},其中k’满足下列三个条件的最长的路的长度:(1)全部顶点在某个圈上,(2)两个端点的度数至少为3,(3)内部顶点的度数全是2。我们还刻画了对于满足hc(T)=h(T)+1和hc(G)=h(G)+1的所有的树T和单圈图G。

全文目录


摘要??3-4
Abstract??4-6
1 绪论??6-11
??1.1 预备知识??6-9
??1.2 本文的主要结果??9-11
2 幂图的生成连通性??11-17
??2.1 相关背景和已知结果??11-13
??2.2 主要结果的证明??13-17
3 图的哈密尔顿连通指标??17-26
??3.1 相关背景和已知结果??17-20
??3.2 图的哈密尔顿连通指标的结果及证明??20-26
4 结论??26-27
参考文献??27-30
攻读硕士学位期间的研究成果??30-31
致谢??31

相似论文

  1. 卫星光通信粗瞄控制系统的设计及故障诊断,V443.1
  2. 病险水库溃坝概率分析方法研究,TV697
  3. 支持XML数据查询的F&B索引结构的研究,TP311.13
  4. 基于串核的蛋白质分类算法的研究与实现,TP301.6
  5. 基于支持向量机的故障诊断方法研究,TP18
  6. 紫金山树木菌根多样性的调查分析,S718.81
  7. 新疆油田地面工程造价指标和管理信息系统的研究与应用,F284
  8. 古树名木综合价值评价研究,S788
  9. 树突状细胞在多柔比星诱导的大鼠肾纤维化模型中的作用,R692.5
  10. P-选择蛋白对人单核细胞源性树突状细胞分化和免疫功能成熟的影响,R543.5
  11. 方东树的学术与古文创作,I206.2
  12. 数据挖掘在高职院校学生成绩分析中的应用,TP311.13
  13. 莱芜九龙山寒武系张夏组树形石特征及地质意义,P581
  14. 树突状细胞及CC趋化因子配体20在大鼠慢性阻塞性肺疾病中的作用,R563.9
  15. 基于数据挖掘的个性化在线教学辅助系统的研究与设计,TP311.13
  16. 基于数据挖掘的课程考核与分析决策系统的设计和实现,TP311.13
  17. 关于充分悬挂单圈图取得极小Hosoya指标图的研究,O157.5
  18. 教学质量评估数据挖掘系统设计与开发,TP311.13
  19. 杀伤细胞免疫球蛋白样受体基因在骨髓衰竭性疾病及造血干细胞移植中的实验研究,R551.3
  20. 基于SOA构架的社区医疗管理系统研究与实现,TP311.52
  21. 数据挖掘技术在高职教师绩效考核中的应用研究,TP311.13

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学(组合学) > 图论
? 2012 www.xueweilunwen.com