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

树的代数连通度

作　者: 管宇
导　师: 张晓东
学　校: 上海交通大学
专　业: 应用数学
关键词: 赋权图树顶点边权重 Laplacian矩阵代数连通度 Fiedler向量
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 121次
引　用: 0次
阅　读: 论文下载

内容摘要

在本文中,首先介绍了图和Laplacian矩阵的一些基本概念和结果.利用代数连通度的二次型形式和瓶颈矩阵的Perron值,我们研究了当迁移或改变分支和变动一些边的权重时树的代数连通度的变化,得到了比过去更多的关于赋权树的代数连通度的结论.(1)以下几种情形时树的代数连通度将不会增加: (a)当不含有任何特征点的分支从较小非负Fiedler值的点或从较大非正Fiedler值的点迁移到较大非负Fiedler值的点或较小非正Fiedler值的点,同时这些分支中某些边的权重可以变小; (b)将接近特征点的较大权重的边与远离特征点的较小权重的边(要求接近特征点的的边位于连接特征点与远离特征点的路上)相交换; (c)减小某些边的权重; (d)增加若干条新的边.(2)以下几种情形时树的代数连通度将不会减小: (a)当不含有任何特征点的分支从较大非负Fiedler值的点或从较小非正Fiedler值的点迁移到较小非负Fiedler值的点或较大非正Fiedler值的点,同时这些分支中某些边的权重可以变大; (b)将接近特征点的较小权重的边与远离特征点的较大权重的边(要求接近特征点的的边位于连接特征点与远离特征点的路上)相交换; (c)增加某些边的权重; (d)删除掉若干条边.

全文目录

摘要  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

树的代数连通度

内容摘要

全文目录

相似论文