| 【中文题名】 | 树的代数连通度 |
| 【英文题名】 | Algebraic Connectivity of Weighted Trees |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-9-14 |
| 【中关键词】 | 赋权图,树,顶点,边,权重,Laplacian矩阵 |
| 【英关键词】 | weighted graph,trees,vertex,edge,weighted,Laplacian matrix,algebraic connectivity,Fiedler vector, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
在本文中,首先介绍了图和Laplacian矩阵的一些基本概念和结果.利用代数连通度的二次型形式和瓶颈矩阵的Perron值,我们研究了当迁移或改变分支和变动一些边的权重时树的代数连通度的变化,得到了比过去更多的关于赋权树的代数连通度的结论.
(1)以下几种情形时树的代数连通度将不会增加: (a)当不含有任何特征点的分支从较小非负Fiedler值的点或从较大非正Fiedler值的点迁移到较大非负Fiedler值的点或较小非正Fiedler值的点,同时这些分支中某些边的权重可以变小; (b)将接近特征点的较大权重的边与远离特征点的较小权重的边(要求接近特征点的的边位于连接特征点与远离特征点的路上)相交换; (c)减小某些边的权重; (d)增加若干条新的边.
(2)以下几种情形时树的代数连通度将不会减小: (a)当不含有任何特征点的分支从较大非负Fiedler值的点或从较小非正Fiedler值的点迁移到较小非负Fiedler值的点或较大非正Fiedler值的点,同时这些分支中某些边的权重可以变大; (b)将接近特征点的较小权重的边与远离特征点的较大权重的边(要求接近特征点的的边位于连接特征点... |
| 【论文题纲】 |
|
摘要 |
2-3 |
|
ABSTRACT |
3-5 |
|
第一章 图和Laplacian矩阵 |
5-7 |
|
第一节 图论基本概念 |
5-6 |
|
第二节 Laplacian矩阵 |
6-7 |
|
第二章 图的代数连通度 |
7-10 |
|
第一节 Fiedler的工作 |
7-8 |
|
第二节 其他学者的工作 |
8-9 |
|
第三节 作者工作简介 |
9-10 |
|
第三章分 支迁移下代数连通度 |
10-17 |
|
第一节 代数连通度变小 |
10-15 |
|
第二节 代数连通度变大 |
15-17 |
|
第四章 改变权重下代数连通度 |
17-19 |
|
第五章 结论 |
19 |
|
致谢 |
19-20 |
|
参考文献 |
20-21 |
|
| 【DOI】 | LunWen.ID:2.2008.11831 |
