（应用数学专业论文）图的拉普拉斯谱半径的讨论.pdf

a b s t r a c t 摘要 代数图论将图论和代数有机地结合在一起，图的邻接矩阵和拉普拉斯矩阵 与图有着自然的联系，代数图论的一个主要问题就是研究图的性质能否及如何 由这些矩阵的代数性质反映出来，经常要用到的矩阵的代数性质有矩阵的特征 值与特征向量等。用代数的方法研究图的性质，用图论的方法研究代数性质会 有很好的效果。 图的邻接矩阵的特征值已经有了大量的研究，出现许多有用的工具。拉普 拉斯矩阵含有图的顶点度的信息，因此图的拉普拉斯矩阵的特征值与图的许多 不变量之间有着更加密切的联系，在物理和化学的很多问题中有着广泛的应用。 树是最简单的连通图，在研究一些困难的图论问题中，先对树进行研究进 而推广被证明是很有效的。 本文在田丰教授等对树的拉普拉斯谱半径排序以及袁西英等对完美匹配树 的拉普拉斯谱半径排序研究的基础上，对完美匹配树的谱半径进行了进一步的 研究。对一些分类作了内部排序，增加了若干分类并作了讨论。最后得出了第 七至第八大谱半径并给出了相应的极树。 关键词：树，完美匹配，拉普拉斯谱半径 a b s t r a c t a l g e b r a i cg r a p ht h e o r yc o m b i n e st h eg r a p ht h e o r ya n da l g e b r at i g h t l y t h e a d j a c e n c ym a t r i x a n dt h el a p l a c i a nm a t r i xo fag r a p ha s s o c i a t ew i t ht h eg r a p h n a t u r a l l y o n eo ft h em a i np r o b l e m so fa l g e b r a i cg r a p ht h e o r y i st od e t e r m i n e p r e c i s e l yh o w , o rw h e t h e r ，p r o p e r t i e so fg r a p h s a l er e f l e c t e di nt h ea l g e b r a i c p r o p e r t i e ss u c ha st h ee i g e n v a l u e s a n de i g e n v e c t o r so ft h em a t r i c e sm e n t i o n e da b o v e t h ee i g e n v a l u e so ft h ea d j a c e n c ym a t r i c e sw e r em u c hm o r ei n v e s t i g a t e d l a p l a c i a nm a t r i xo fag r a p hc o n t a i n st h ei n f o r m a t i o no ft h ed e g r e e so ft h ev e r t e x e s ， a n dh a sac l o s er e l a t i o nt ot h eg r a p h i ti sw i d e l ya p p l i e di nt h ef i e l d so fp h y s i c sa n d c h e m i s t r y t r e e sa r et h es i m p l e s tc o n n e c t e dg r a p h o nt h er e s e a r c ho ft h ed i f f i c u l t y p r o b l e m so ft h eg r a p ht h e o r y , w em a y r e s e a r c ht h et r e e sf i r s ta n dt h e n ，g e n e r a l i z et o t h ec o n n e c t e dg r a p h i t sp r o v e dt ob ea ne f f i c i e n tw a y t os o l v et h ep r o b l e m s 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月目 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月 日 第1 章引言 1 1 概述 第1 章引言 图谱理论主要研究图的邻接矩阵和拉普拉斯矩阵的特征值和特征向量，是 图论研究的一个重要方向。图的邻接谱的研究已形成比较成熟的理论，有很多 重要的结论和公式、工具。与图的邻接矩阵相比，拉普拉斯矩阵含有图的度的 信息，与图的结构有更自然的联系，更能反应图的性质，因此拉普拉斯谱半径 的研究越来越越引起人们的关注。 树是最简单的连通图，在研究一些困难的图论问题中，先对树进行研究进 而再加以推广被证明是很有效的。 本文在田丰教授等对树的拉普拉斯谱半径排序以及袁西英等对完美匹配 树的拉普拉斯谱半径排序研究的基础上，对完美匹配树的谱半径进行了进一步 的研究。本文运用图论中的嫁接、收缩、加边、夺邻的技巧与代数中多项式方 程大根比较的方法相结合，采用淘汰优先，比拼为辅的策略，增加了若干分类 并对一些分类作了内部排序。最后得出了第七至第八大谱半径并给出了相应的 完美匹配树。 1 2 分类与记号 本文讨论简单无向图，全部讨论在后苫8 下进行。以丁( 舭) 记2 七阶完美匹配 树的集合。当re t ( 2 k ) i f j ，其完美匹配唯一，记为m ( r ) 。m ( r ) 中悬挂边数 记为胁。( 丁) ，其中一个端点度数为2 的悬挂边数记为班。：( 丁) ，分别简记为m l 、m 1 2 。 显然，l 。 m a ：。将r ( 觋) 按数值大小分成若干子集： z 。( 勉) = t i r t ( 2 k ) ，m 1 = q ) 。 第1 章引言 以h ；记顶点数为k ，拉普拉斯谱半径第i 大的树。田丰 1 等对拉普拉斯谱 半径为第一至第八的k 阶树作了排序。 以正记顶点数为2 七，拉普拉斯谱半径第f 大的完美匹配树。郭继明【2 】、袁 西英【3 】等给出了第一至第六大完美匹配树谱半径和相应的完美匹配树。 以( g ) 记图的拉普拉斯谱半径。如果( g ) 3 ，h ，v 之间有一条长 大于1 的内路。收缩“， ，间的边，使h ，v 路变成掰，y 边得到新图g ，则g g 。； 3 【1 1 加边：在树g 的任一顶点处加一条悬挂边得到新图g ，则g i x v l ，将v 的悬挂路全部或部分移到“点得到新图 g ，则g c ( 好：) 。 定义1 2 图类厂( t ) 对任意r z ( 放) ，慨( 丁) 七，将完美匹配m ( t ) 中的每条非悬挂边收缩 为一点后再在每一个收缩点上加一条新悬挂边得到的唯一的树记为r ( r ) 。 性质1 。2 1 、，( r ) 瓦( 2 k ) 2 、班，：( 厂( 丁) ) ，m ，：( 丁) 3 、t 厂( z ) 定理1 1 如果r ( 2 足) ，七一3 q 墨尼一1 ，惕：= 七一3 ，( 丁) 圣 c ( h 。) ，c ( i - i , ) ) ， 则丁 c ( 日，) 证明：m 。：( z ) = k 一3 的前三大完美匹配树为c ( h 。) c ( u ，) c ( h ，) 。 ，( z ) 圣 c ( 日。) ，c ( 玩) ) ，则z 0 ，贝i jg ( x ) 的大根大于肛。 2 24 类，二叉图 袁西英等的文章 2 对4 类也已作了全排序。记4 类树f 的完美匹配中唯一 非悬挂边为”y ，两点分别接出去l ，j 个叉的图为t ( i ，j ) ，则五；z ( t 七- 2 ) 。记 此类中排第二第三的两个图为z ( 2 ，k - 3 ) 。4 、t ( 3 ，k - 4 ) a 4 。 定理2 1 ( c 5 ，4 ，4 之比较) 设2 k 阶完美匹配树c 5 ，4 ，4 如上所定义，则我们有 1 c 5 4 证明：不难计算： m ( 4 ) = 工( 石一2 ) ( z 2 3 x + 1 ) “3 口：( z ) 口：( x ) = z 4 - ( k + 5 ) z 3 + ( 6 七+ 1 ) x 2 一( 龇- l o ) x + k m ( c 5 ) = x ( x 一2 ) ( x 2 3 x + 1 ) “5c 5 ( z ) c 5 ( x ) t 工8 - ( k + 1 ) 石7 + ( 1 2 k + 4 1 ) x 6 一( 5 微+ 5 2 ) x 5 + ( 1 1 6 k - 2 6 ) x 4 6 一( 1 2 6 k 一1 1 4 ) x 3 + ( 6 8 k - s 6 ) x 2 - 0 6 , 一2 0 ) x + 七 m ( a ，) 一xx - - 3 x + 1 广a ，( x ) 口，( x ) 一x 4 一( 七+ 5 ) x 3 + ( 弛一5 ) x 2 - ( 1 0 k - 2 2 ) x + k 由引理2 1 可知( 4 ) 是口：( x ) 的大根，( c 5 ) 是c ，( x ) 的大根，( 鸽) 是a ，( x ) 的 大根 1 经计算： c 5 ( x ) 一( x 4 5 x 3 + 1 0 x 2 6 x ) a ：( x ) + p ( x ) p ( x ) 一( 七一6 ) x 4 一( 4 k 一2 0 ) x 3 + o o k - 2 6 ) x 2 - ( 1 0 k 一2 0 ) x + k 设肛是c ，( z ) 的大根，。( c 5 ) z 七- 2 ， a + i = k 一1 苫7 作变换k ；h + 1 ，x = y + | f l 贝i j p ( x ) = q ( y ) = ( j l 一5 ) r 4 + 4 ( 2 6 h + 4 ) y 3 + ( 劬3 - 4 2 h 2 + 5 8 h 一1 6 ) y 2 + ( 4 j i l 4 3 2 h 3 + 6 8 h 2 4 2 h + 1 0 ) y + ( h 5 - 9 h 4 + 2 6 h 3 - 2 6 h 2 + 1 1 h + 1 ) 当七苫8 时，h 之7 ，所有系数为正 p ( ) = q ( p - h ) 0 又4 6 3 + 1 0 p 2 6 0 ，由引理2 3 得a 2 ( x ) 的大根大于 4 c 2 将4 ，c s 分别与前述辅助图g 作比较。 c ；( x ) = ( 工3 5 x 2 + 3 x 一2 ) g ( 石) 一p ( x ) p ( z ) = 5 x 4 一( 3 k + 1 2 ) x 3 + ( 1 3 k + 1 9 ) x 2 - ( 1 6 k 一1 4 ) x + 3 k g ( x ) = z 口，( x ) - q ( x ) 7 碍( x ) - x 4 1 3 x 3 + ( 酞+ 1 4 ) x 2 一( 1 放一1 7 ) x + 放 由引理2 3 及证明1 的变换方法可得4 g 1 , n 3z 1 , n 1 + 1 1 2 + 如= 七一2 ) 文章f 2 】的结果：五一z ( 1 ，o ，七一3 ) 引理3 1 2 1v t e b 瓦) 有 1 r 0 b 2 ( ) 肛 b 2 b 2 比较b ，色 a = ( b ) = 七- 3 , t = ( 马) a + i - - k 一2 芑6 6 4 ( z ) 一岛( z ) 一( 七一5 ) x ( x 3 一缸2 + a 一2 ) 6 4 ( ) 一岛( ) 0 1n 么( 弘) j c l 。马 日 3 比较日，也 一a ( 8 2 ) = 尼- 2 ，p 一( 砬) a + l fk 一1 苫7 岛( x ) 一( x 2 - 3 x + 1 ) b ：( x ) + p ( x ) p ( x ) - - 一( 七一4 ) x ( x 一1 ) 2 ( x 一2 ) 由引理2 3 可得( b ) 乒1 蜀 岛 综合以上三步可得m a x ( 日) ，( 吃) ，( 色) ，( 色) ) - - ( b i ) 定理3 2 将b 类图中谱半径最大者毋与前面筛选出的c 5 比较得c 5 a + l f k - lz7 下面利用c 5 4 来说明p ( ) o ) a 而b x ( 肛) k 一1 。鸟( 弘) o 当七 1 3 时，f f y q ( x ) - ( k - s ) x 3 - 2 ( k - 1 3 ) x 2 + 2 ( 七一1 3 ) x - 2 k + 1 2 求导得 q ( z ) = 3 ( 七- 8 ) x 2 4 ( k 一1 3 ) x + 2 ( k - 1 3 ) 此首项系数为正的两次三项式的判别式为- 8 ( k - 1 3 ) ( k + 2 ) 0 q ( x ) 单调增加 q ( k - 1 ) = 七4 1 3 k 3 + 5 9 k 2 - 1 0 9 k + 7 2 0 q ( 1 - t ) q ( k 一1 ) 0 3 2d 类：四叉图 d 一 z ( m ，挖：，伤，露。) ，嘞1 , n 4 ：- 1 ，啊+ 刀：+ 撑，+ 挥。一七一2 ) d l = t ( l o ，k - 4 ，1 ) ，d 2 。z ( 后- 3 ，0 ，0 ，1 ) 1 2 z j l 理3 2 【2 】v 丁d d 1 ，d 2 ) 则p ( z ) 7 由引理2 3 知( d 1 ) 从而d 2 d l 定理3 4 将d 类中谱半径最大的d x 与前面讨论的图比较得d 1 置 证明：记d 1 中接出k 一4 个叉的点为u 。u 点发出一条长为4 ，一条长为3 ，k 一4 条 长为2 的悬挂路，嫁接成u 发出3 条长为3 ，k 一5 条长为2 的路得到辅助图g 。由引理1 1 有q g 。由定理2 1 的证明，有g g ，b g + c 5 最 结论： 除互至瓦、4 、b ，a ，b ，c ，d 类中任一树r ，z 日 4 1 3 第4 章u 类、y 类、w 类的讨论 由定理1 2 ，在只的六个顶点的若干点处接叉，再按鸭分成此三类。记只的6 个点依次为，分别接个叉，i = l 2 ，3 ，4 ，5 ，6 。该图记为丁= s ( 玩，n 2 ，心，n 。，n ，) ， 则 ( r ) = c ( p ( ，z 。+ ，l ：，_ ，l 。+ ，l 。，+ ) ) ，其中p ( a ，b ，c ) 表示在只的三个顶点处分别 有a ，b ，c 条悬挂边的图。 若，( t ) c ( n 。) ，则r ，( t ) sc s 置 若，( t ) = c ( 日。) ，则进一步讨论。 u 2 u 3u 4u 5 u i 4 1u 类，四叉二根图 1 4 u u 2 u 3u 4 ：；七一3 ，鸭- k - 1 ，完美匹配中只有“。m ；是非悬挂边。 此类图中，( z ) 一c ( 只) 的树丁的结构为丁= s ( o ，1 ，如，露。，l o ) 对丁作如下变换： 1 u 3 ，1 1 4 对称，“3 夺“4 叉得r = s ( o ，1 ，k - 5 ，0 ，1 , o ) 2 在u 。处加一悬挂边 3 d ( z f ，) 3 ，d ( h ，) - - 5 经第1 步变换d ( “。) = 2 。收缩“，比，路成m 。“，边。 经上述变换，得到新图t ( 2 ，k - 5 ，1 ) b z 色 4 2y 类，五叉一根图 u l u 2 u s 1 5 m a 2 一是- 3 ，m i = k - 2 m ( r ) 中有两条非悬挂边“。h ：，“，“。此类图中l ( r ) = c ( h 。) 的丁的结构为 r s ( o ，1 ，万3 ，忍。，1 o ) 对t 作收缩z f 。u 2 加悬挂边变换后得s ( 0 ，1 ，他，厅。，1 o ) u r 马 4 3 w 类，六叉图：m i ：= = k 一3 u 1u 2 u 3u 4 u 5 u 此类图中厂( 丁) = c ( h 。) 的z 的结构为： t = s ( 1 ，0 ，1 3 ，l 。，0 ，1 ) 对t 作收缩“。u 2 加悬挂边、收缩“，u 6 加悬挂边变换后得r ；s ( 1 ，0 ，珂，以。，0 ，1 ) eu r 马 结论：u 类、y 类、矽类中任一图均被聩淘汰。 1 6 第5 章e 型图 由定理1 2 ，在c ( 只) 的六个点的若干点处接叉得到的完美匹配树记为e 型 图。 设c ( b ) 的三个一度点依次为“。，“：，“，相应的邻点依次为u ，v 2 ，v 3 。在点 “，处接个叉、a v , 处种五个叉，t 。1 ，2 ，3 的图记为e ( ，i ：，i 3 ，j l ，j ：，j f 3 ) 。 其中，i 2 ，如不全为0 且f l + 五1 ，毛+ j 3 1 ，+ 之+ f 3 + j 1 + j 2 + 矗；七一3 v t e e ，f ( r ) = c ( p ( + 矗，i 2 + j 2 ，毛+ 厶) ) 若厂( ? ) c ( 日。) ，则丁 ，( r ) 墨c 5 马 若，( 丁) - - c ( h 。) 即f l + 矗= f 3 + 五一1 ，分成一下三个子类： 1 磊= e ( 1 ，之，1 , o ，j 2 ，0 ) 2 e 2 = e ( 1 , i 2 ，0 ，0 ，歹2 ，1 ) 3 e 3 = e ( o ，i 2 ，0 ，1 ，_ 2 ，1 ) 5 1 巨的讨论易 对巨型图作变换： 1 收缩“：v 2 加悬挂边得e ( 1 ，0 ，1 ，0 ，k - 5 ，0 ) ； 2 a v ：发出一条长为1 ，一条长为4 的悬挂路。嫁接成一条长为2 、一条长为3 的 悬挂路得图d 1 v t 巨，t 日 鼠 1 7 6 2 e 2 的讨论 对e ：型图作变换： 1 收缩“： ，：加悬挂边得e ( l o ，0 ，0 ，k 一5 ，1 ) ； 2 v 2 发出一条长为1 、一条长为4 的悬挂路。嫁接成一条长为2 、一条长为3 的 路，得图置 。v 丁置，t 日 5 3 毛的讨论 对e 3 型图作变换。 h ，坞对称，屹夺h 叉得图t ( i 2 ，厶+ 1 ，2 ) 曰一五 v t e e 3 ，t b 结论：犁图均小于b 1 1 8 6 1 结论 第6 章结论与展望 定理6 1 完美匹配树谱半径第7 大的是二叉图中的第二大。第八大是三叉一根图 中最大者。即： 1 乃= 4 = z ( 2 ，k 一3 ) ，五2 置= z ( 1 ，七一4 ，1 ) 2 ( 弓) 是口：( x ) 的大根，( 瓦) 是2 j l ( x ) 的大根。 证明：由前面的讨论即得。 6 2 进一步工作的方向 在图的比较淘汰中，很多类别的图都被c 5 淘汰，只是计算更复杂。猜想接 下来谱半径第9 大的图是c 5 。相信随着研究的深入，可以得到更有效的工具、 更好更一般的结论。这也是我今后进一步工作的方向。 1 9 致谢 在职读研三年，完成繁重的教学任务之余，没有整块的时间去连续地思考、 记录、整理、研究。刚有了点想法，一忙又全部忘了。断断续续作了大量的绘 图、演算只凝聚成这么薄薄的一本毕业论文。其中艰辛唯有自己去回味。完成 之际，面临毕业，真诚地感谢三年一路走来陪伴我的老师、同学、父母家人。 感谢我的导师邵嘉裕教授，是他将我带进了科研的领域。邵先生渊博的学 术造诣、严谨的治学风格、精益求精的教学理念深深感染了我。在我今后的科 研和教学工作中帮助极大。三年来，邵先生不但在学业上悉心指导，而且在生 活上给予关怀帮助。得遇良师，此生之幸。 感谢李雨生教授。李教授授课风趣幽默，让我在教学上学到很多东西。感 谢郭镜明教授。郭教授如慈祥的长者不断鼓励我帮助我，让我坚定了克服困难 完成学业的信心。感谢同济大学的领导和同事在这三年中给予的关心和支持。 感谢我的同学，虽然我年长很多，学业上却起步最晚。三年来你们关心我 帮助我。尤其是刘月同学，在论文的输入，资料的提供等等方面给予了很多帮 助。 最后感谢我的父母，在学习期间承担了所有的家务。感谢我的儿子杨辰兮， 在论文绘图排版上做的工作，尤其是在学习上自觉自立，让我能集中精力做好 自己的工作和学习。 2 0 2 0 0 7 年5 月 参考文献 【1 】1 j m g u o ，o nt h el a p l a c i a ns p e c t r a lr a d i u so fat r e e ，l i n e a ra l g e b r aa p p l 3 6 8 ( 2 0 0 3 ) 3 7 9 - 3 8 5 【2 】2 j i a - y us h a o ，x i - y i n gy u a n ，c h a n g x i a n gh e ，o nt h el a p l a c i a ns p e c t r a lo ft r e e sw i t hp e r f e c t m a t c h i n g ，s u b m i t t e dt ol i n e a ra l g e b r aa p p l 【3 】n a l o n ，e i g e n v a l u e sa n de x p a n d e r s ，c o m b i n a t o r i c a ，6 ( 1 9 8 6 ) 8 3 - 9 6 【4 】a m y u ，m l u ，f t i a n ，o r d e r i n gt r e e sb yt h e i rl a p l a c i a ns p e c t r a lr a d i i ，l i n e a ra l g e b r a a p p l 4 0 5 ( 2 0 0 5 ) 4 5 5 9 【5 】j h b e v i s ，f j h a l l ，i n t e g e rl u f a c t o r i z a t i o n s ，l i n e a ra l g e b r aa p p l ，1 5 0 ：2 6 7 2 8 6 ( 1 9 9 1 ) 【6 】n lb i g g s ，a l g e b r a i cg r a p h t h e o r y ，c a m b r i d g eu n i v p r e s s ，c a m b r i d g e ，1 9 7 4 【7 】b b o l l o b a s ，m o d e mg r a p ht h e o r y ，s p r i n g e r v e r l a g ，1 9 9 8 【8 】j a b o n d y a n du s r m u r t y ，g r a p h t h e o r y w i t h a p p l i c a t i o n s ，t h em a c m i l l a np r e s s ，1 9 7 6 【9 】9v b r a n k o v ，p h a n s e n ，d s t e v a n o v i c ，a u t o m a t e d c o n j e c t u r e so nu p p e rb o u n d sf o r t h e l a r g e s tl a p l a c i a ne i g e n v a l u eo fg r a p h s ，l i n e a ra l g e b r aa p p l ，t oa p p e a r 【1 0 】a c h a n g ，q h u a n g ，o r d e r i n gt r e e sb yt h e i rl a r g e s te i g e n v a l u e s ，l i n e a ra l g e b r aa p p l ， 3 7 0 ( 2 0 0 3 ) 1 7 4 - 1 8 4 【11 】f r 1 ( c h u n g ，d i a m e t e ra n de i g e n v a h e s ，j a m m a t h s o c 2 ( 2 ) ( 1 9 8 9 ) 1 8 7 1 9 6 【1 2 】f r kc h u n g ，s p e c t r a lg r a p h t h e o r y ，c b m s ( c o n f e r e n c eb o a r do f t h em a t h e m a t i c a l s c i e n c e s ) r e g i o n a lc o n f e r e n c es e r i e si nm a t h e m a t i c s ，9 2 ，a m s ，p r o v i d e n c e ，1 9 9 7 【1 3 】d m c v e t k o v ic ，m d o o b ，i g u t m a na n da t o r g a s e v ，r e c e n tr e s u l t si nt h et h e o r yo f g r a p hs p e c t r a ，n o r t h h o l l a n d ，1 9 8 8 【1 4 d m c v e t k o v i c ，m d o o b a n dh s a c h s ，s p e c t r ao fg r a p h s - t h e o r ya n da p p l i c a t i o n ，j o h a n n a m b r o s i u sb a r t hv e f l a g ，1 9 9 5 【1 5 】d m c v e t k o v ic ，p r o w l i n s o n ，s s i m i c ，e i g e n s p a c e so fg r a p h s ，c a m b r i d g eu n i v e r s i t y p r e s s ，1 9 9 7 ，5 6 - 6 0 【1 6 】kc d a s ，a ni m p r o v e d u p p e rb o u n df o rl a p l a c i a ng r a p h e i g e n v a l u e s ，l i n e a ra l g e b r aa p p l ， 3 6 8 ( 2 0 0 3 ) 2 6 9 2 7 8 【1 7 】l ( c d a s ，ac h a r a c t e r i z a t i o no ng r a p h sw h i c ha c h i e v et h eu p p e rb o u n df o r t h el a r g e s t l a p l a c i a ne i g e n v a l u eo fg r a p h s ，l i n e a ra l g e b r aa p p l ，3 7 6 ( 2 0 0 4 ) 1 7 3 1 8 6 【1 8 】m d o o b ，t h el i m i tp o i n t so fe i g e n v a l u e so fg r a p h s ，l i n e a ra l g e b r aa p p l ，1 1 4 1 1 5 ( 1 9 8 9 ) , 6 5 9 6 6 2 【1 9 】b e e i c h i n g e r ，a na p p r o a c h t o d i s t r i b u t i o nf u n c t i o n sf o rg a u s s i a nm o l e c u l e s ， m a c r o m o l e c u l e s1 0 ( 1 9 7 7 ) 6 7 1 6 7 5 f 2 0 】b e e i c h i n g e r , s c a t t e r i n g f u n c t i o n sf o rg a u s s i a nm o l e c u l e s ，m a c r o m o l e c u l e s1 1 ( 1 9 7 8 ) 4 3 2 - 4 3 3 【2 1 】b e e i c h i n g e r , s c a t t e r i n gf u n c t i o n sf o rg a u s s i a nm o l e c u l e s 2 i n t e n n o l e c u l a rc o r r e l a t i o n ， m a c r o m o l e c u l e s1 1 ( 1 9 7 8 ) 1 0 5 6 - 1 0 5 7 【2 2 】b e e i c h i n g e r , c o n f i g u r a t i o ns t a t i s t i c so fg a u s s i a nm o l e c u l e s , m a c r o m o l e c u l e s1 3 ( 1 9 8 0 ) 1 1 1 【2 3 】b e e i c h i n g e r ，j e m a r t i n ，d i s t r i b u t i o nf u n c t i o n sf o rg a u s s i a n m o l e c u l e s i i r e d u c t i o no ft h ek i r c h h o f fm a t r i xf o rl a r g em o l e c u l e s ，j c h e m p h y s 6 9 ( 1 0 ) ( 1 9 7 8 ) 4 5 9 5 4 5 9 9 【2 4 】s f a l l a t ，s k i r k l a n d ，e x t r e m i z i n ga l g e b r a i cc o n n e c t i v i t ys u b j e c t t og r a p ht h e o r e t i c c o n s t r a i n t s ，e l e c t r o n j l i n e a ra l g e b r a3 ( 1 9 9 8 ) 4 8 - 7 4 【2 5 】s f a l l a t ，s k i r k l a n d ，s p a t i ，m i n i m i z i n ga l g e b r a i cc o n n e c t i v i t yo v e rc o n n e c t e dg r a p h sw i t h f i x e dg i r t h ，d i s m a t h 2 5 4 ( 2 0 0 2 ) 1 1 5 - 1 4 2 【2 6 】s f a l l a t ，s k i r k l a n d ，s p a t i ，m a x i m i z i n ga l g e b r a i cc o n n e c t i v i t yo v e ru n i c y c l i cg r a p h s ， l i n e a ra n dm u l t i l i n e a ra l g e b r a ，v 0 1 51 ，n o 3 ( 2 0 0 3 ) 2 2 1 - 2 4 1 【2 7 】s f a l l a t ，s k i r k l a n d ，s p a t i ，o ng r a p h sw i t ha l g e b r a i cc o n n e c t i v i t ye q u a lt om i n i m u me d g e d e n s i t y ，l i n e a ra l g e b r aa p p l ，3 7 3 ( 2 0 0 3 ) 3 1 5 0 【2 8 】i f a r i a ，p e r m a n e n t a lr o o t sa n dt h es t a rd e g r e eo fag r a p h ，l i n e a ra l g e b r aa p p l ，6 4 ：2 5 5 2 6 5 ( 1 9 8 5 ) 【2 9 】m f i e d l e r ，a l g e b r a i cc o n n e c t i v i t yo fg r a p h s ，c z e c h m a t h j 2 3 ( 9 8 ) ( 1 9 7 3 ) 2 9 8 3 0 5 【3 0 】m f i e d l e r ，ap r o p e r t yo fe i g e n v e c t o r so fn o n n e g a t i v es y m m e t r i cm a t r i c e sa n di t sa p p l i c a t i o n t og r a p ht h e o r y ，c z e c hm a t h j 2 5 ( 1 9 7 5 ) 6 1 9 6 3 3 【3 1 】m e f i s h e r ，o nh e a r i n g t h es h a p eo f ad r u m , j c o m b i n t h e o r y ，1 ：1 0 5 1 2 5 ，1 9 6 6 【3 2 】w c f o r s m a n ，g r a p ht h e o r ya n dt h es t a t i s t i c sa n dd y n a m i c so fp o l y m e rc h a i n s ， j c h e m p h y s 6 5 ( 1 9 7 6 ) ，4 1 1 1 4 11 5 2 2 【3 3 】t g a l l i ，u b e re x t r e m ep u n k t u n dk a n t e n m e n g e n ，a n n u n i v s c i b u d a p e s t ，e o t v o ss e c t m a t h 2 ( 1 9 5 9 ) 1 3 3 - 1 3 8 【3 4 1e r c g a n t m a c h e r ，t h et h e o r yo fm a t r i c e s ，v o l u m ei i ，c h e l s e a ，n e wy o r k , 1 9 5 9 【3 5 1c g o d s i la n dg r o y l e ，a l g e b r a i cg r a p ht h e o r y ，s p r i n g e r - v e d a g ，2 0 0 1 【3 6 】r g r o n e ，o n t h e g e o m e t r y a n d l a p l a c i a no fag r a p h ，l i n e a ra l g e b r aa p # ， 1 5 0 ( 1 9 9 1 ) 1 6 7 1 7 8 【3 7 】r g r o n e ，r m e r d s ，a l g e b r a i cc o n n e c t i v i t yo ft r e e s ，c z e c h m a t h j 3 7 ( 11 2 ) ( 1 9 8 7 ) 6 6 0 6 7 0 【3 8 】r g r o n e ，r m e r r i s ，o r d e r i n gt r e e sb ya l g e b r a i cc o n n e c t i v i t y , g r a p h sc o m b i n 6 ( 1 9 9 0 ) 2 2 9 2 3 7 【3 9 】r g r o n e ，r m