| 【中文题名】 | 图的Kirchhoff指标 |
| 【英文题名】 | Kirchhoff Index of Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-20 |
| 【中关键词】 | 电阻距离,Kirchhoff指标,Wiener指标,弦图,p部图,阈图 |
| 【英关键词】 | resistance distance,Kirchhoff index,Wiener index,chordal graphs,p-partite graphs,threshold graphs, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
连通图G的两个顶点t和j之间的电阻距离r_(ij)定义为通过用单位电阻来代替G中的每条边而构造出的电网络N中的节点i和j之间的有效电阻的阻值。图G的Kirchhoff指标Kf(G)定义为G中所有点对之间的电阻距离之和。在本文中，首先，我们根据图的Laplacian谱得到了两类弦图的Kirchhoff指标的计算公式；接着，对n阶p部图G=G(N_1，N_2，…，N_p)(|N_i|=n_i，i=1，2，…，p；n_1≤n_2≤…≤n_p)，我们得到其Kirchhoff指标的可达上界和下界，且表明：若2n_p-n≤1，当其同构于路R_n时达到上界；若2n_p-n≥2，当其同构于树T′(n_1，n_2，…，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 |
|
| 【DOI】 | LunWen.ID:2.2008.11839 |
