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

图的Kirchhoff指标

作　者: 陈方珂
导　师: 张和平
学　校: 兰州大学
专　业: 运筹学与控制论
关键词: 电阻距离 Kirchhoff指标 Wiener指标弦图 p部图阈图
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 63次
引　用: 1次
阅　读: 论文下载

内容摘要

连通图G的两个顶点t和j之间的电阻距离r_ij定义为通过用单位电阻来代替G中的每条边而构造出的电网络N中的节点i和j之间的有效电阻的阻值。图G的Kirchhoff指标Kf（G）定义为G中所有点对之间的电阻距离之和。在本文中，首先，我们根据图的Laplacian谱得到了两类弦图的Kirchhoff指标的计算公式；接着，对n阶p部图G=G（N₁，N₂，…，N_p）（|N_i|=n_i，i=1，2，…，p；n₁≤n₂≤…≤n_p），我们得到其Kirchhoff指标的可达上界和下界，且表明：若2n_p-n≤1，当其同构于路R_n时达到上界；若2n_p-n≥2，当其同构于树T′(n₁，n₂，…，n_p-1；n_p)时达到上界；当其为完全p部图时达到下界。我们进一步得到，在所有的n阶p部图中，Turán图的Kirchhoff指标最小。最后，我们发现步长为1和z（2≤z≤[n/2]-1）的n阶4-正则循环图G_n（1，z）的Kirchhoff指标当z=2时取得最大值。通过计算和验证，此结论当7≤n≤30000时均成立。

全文目录

摘要  4-5
ABSTRACT(英文摘要)  5-7
第一章引言  7-14
  1.1 基本概念和记号  7-9
  1.2 研究进展和已有结果  9-11
  1.3 图运算的Laplacian谱  11-14
    1.3.1 补图  11
    1.3.2 直和  11-12
    1.3.3 联图  12
    1.3.4 直积  12
    1.3.5 合成图  12-14
第二章两类弦图的Kirchhoff指标  14-23
  2.1 第一类弦图的Kirchhoff指标  14-16
  2.2 第二类弦图的Kirchhoff指标  16-23
第三章 p部图的Kirchhoff指标的界  23-42
第四章 G_n(1,z)的Kirchhoff指标极值的一个发现  42-45
参考文献  45-47
附录  47-51
致谢  51

图的Kirchhoff指标

内容摘要

全文目录

相似论文