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

一类优美图

作　者: 李慧军
导　师: 杨元生
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 优美图顶点标号边标号
分类号: TP301.6
类　型: 硕士论文
年　份: 2006年
下　载: 158次
引　用: 0次
阅　读: 论文下载

内容摘要

优美图是图论中极有趣的研究课题之一。它的研究始于1963年G. Ringel提出的一个猜想和1966年A. Rosa的一篇论文。1972年,S. W. Golomb明确给出了优美图的定义。对一个给定的简单图G=（V（G）,E（G））,|V（G）|和|E（G）|分别是图G的顶点数和边数,令|E（G）|=q,如果存在一个一一映射f:V（G）→{0,1,2,…,q},使得对所有边（u,v）∈E（G）,由f′（u,v）=|f（u）-f（v）|所导出的函数f′:E（G）→{1,2,…,q)是一个一一对应,则称f是图G的一个优美标号,图G被称为优美图。本文研究n为奇数时C_n^t图的优美性。令C_n^t图为有一个公共顶点v的t个长度为n的回路所组成的图。用v₀ⁱ,v₁ⁱ,v₂ⁱ,…v_n-1ⁱ表示C_n^t图第i（1≤i≤t）个长度为n的回路上的顶点,对所有的i,有v₀ⁱ=v。A. Rosa给出了具有q条边的欧拉图为优美图的必要条件为q≡0,3（mod 4）,C_n^t图是欧拉图,因此C_n^t图是优美图的必要条件为nt≡0,3（mod 4）。 1979年,K. M. Koh等人猜想:当且仅当nt≡0,3（mod 4）时,C_n^t图是优美图。已经证明了当n=3,5,4p,4p+2（p≥1）时该猜想成立。本文设计了计算机辅助下求解C_n^t图优美标号的算法,并利用C_n^t图的对称性,对顶点进行合理的分组,采用顶点的分布规律制约边的分布规律的策略,给出了搜索C_n^t图的优美标号的有效的分支限界条件,给出了当n=7,9,11,13时,C_n^t图的一种优美标号,并证明了当n=7,9,11,13,K. M. Koh等人的猜想成立。

全文目录

摘要  4-5
Abstract  5-7
引言  7-9
1 图的基本概念  9-11
2 优美图研究动态  11-31
  2．1 树的优美性  12-16
    2．1．1 通路  12-13
    2．1．2 毛毛虫  13-14
    2．1．3 花树  14-16
  2．2 回路及其相关图的优美性  16-28
    2．2．1 回路  16-17
    2．2．2 轮图  17-20
    2．2．3 齿轮图  20-21
    2．2．4 恰有一个公共顶点的多个回路  21-28
  2．3 完全图及其相关图的优美性  28-29
    2．3．1 完全图  28-29
    2．3．2 荷兰风车  29
    2．3．3 法国风车  29
  2．4 本文工作  29-31
3 C_n~(t)图的优美性  31-55
  3．1 C_7~(t)图的优美性  31-36
  3．2 C_9~(t)图的优美性  36-42
  3．3 C_11~(t)图的优美性  42-48
  3．4 C_13~(t)图的优美性  48-55
结论  55-56
参考文献  56-58
攻读硕士学位期间发表学术论文情况  58-59
致谢  59-60
大连理工大学学位论文版权使用授权书  60

一类优美图

内容摘要

全文目录

相似论文