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

图的临界群研究

作　者: 王健
导　师: 徐俊明；潘永亮
学　校: 中国科学技术大学
专　业: 应用数学
关键词: Laplacian矩阵 Smith标准型临界群不变因子
分类号: O157.5
类　型: 博士论文
年　份: 2010年
下　载: 57次
引　用: 0次
阅　读: 论文下载

内容摘要

图G的Laplacian矩阵L(G)是研究图的性质的一个重要工具.人们传统上用L(G)的特征值来研究图论,得到很多很好的结论.近二十年来,人们发现L(G)的Smith标准型和特征值一样,同为图的同构精细不变量,自然也是研究图论的好工具.作者最早接触到的临界群概念,是源自Godsil和Royle的著作GTM207.国际著名数学家Biggs在1999年的时候证明了图的临界群能够被L(G)的Smith标准型所刻划.本文研究了两类Cartesian乘积图Km×Cn和C4×Cn的Laplacian矩阵,得到了它们的Smith标准型,给出了这两类图的临界详细群结构和生成树数目.对于一般化的图,我们给出了其Smith标准型的前三个不变因子的精确上界.下面的是本篇论文得到的主要结果,其中的参数在正文对应部分都有详细的介绍：若n=2s+1,则Km×Cn(m,n≥3)的临界群为其中若n=2s,则Km×Cn(m,n≥3)的临界群为其中由此得到Km×Cn的支撑树的数目为若n=2s+1,则C4×Cn(n≥3)的临界群为若n=2s且s为奇数,则C4×Cn(n≥3)的临界群为若n=2s且s为偶数,则C4×Cn(n≥3)的临界群为由此得到图C4×Cn的支撑树的数目为从而证明了当n≥3时,有以下三角函数恒等式成立此外,对n≥5阶的简单连通非完全图G,还得到了它的第三位不变因子的定位：s3(G)≤n,并且s3(G)=n当且仅当G=Kn-e,其中e的任意一条边Kn；s3(G)=n-1当且仅当G=v.Kn-1,其中n≥5且G由完全图Kn-1连接一个垂点v所得；s3(G)=n-2当且仅当n=5且G=K5-2e,其由K5删除两条不相邻的边所得,或G=K5-C4,其由K5删除长为4的圈的边所得；s3(G)=n-3当且仅当G为下述六种图之一：K2,3,K5-C3,K6-C3,K7-2C3,K3,3及K7-K3,3.

全文目录

摘要  5-7
ABSTRACT  7-10
目录  10-11
第一章引言  11-15
  1.1 图的基本概念  11-12
  1.2 图的运算  12
  1.3 与图相关的矩阵  12-15
第二章图的临界群和Tutte多项式  15-37
  2.1 筹码发射游戏  15-20
  2.2 临界群  20-29
  2.3 Tutte多项式  29-35
    2.3.1 递减序列  30-31
    2.3.2 递减序列与支撑树  31-33
    2.3.3 递减序列和临界态  33-35
  2.4 幺模相抵  35-37
第三章两类Cartesian乘积图的临界群  37-77
  3.1 基本思想  37-39
  3.2 图K_m×C_n的临界群  39-57
  3.3 图C_4×C_n的临界群  57-77
第四章图的Smith标准型  77-89
  4.1 Smith标准型的前三个不变因子的定位  77-87
  4.2 未来工作的展望  87-89
参考文献  89-93
致谢  93-95
作者攻读博士学位期间完成论文目录  95

图的临界群研究

内容摘要

全文目录

相似论文