（计算机软件与理论专业论文）图的整谱性理论及其解的计算机搜索.pdf

摘要 摘要 图论是一门充满生机的学科。它与理论计算机科学有密切的关系，图论为 研究理论计算机科学提供了强有力的数学工具，高速发展的计算机技术又促 进了图论学科的发展图沦在以信息为特征的知识经济时代具有重要的前瞻 性和广泛的应用前景本论文选择图论及其应用中的重要课题“图的整谱性理 论及其解的计算机搜索”作为研究对象，旨在对图的整谱性理论做深入的研 究，并推广和发展国内外著名图论专家的重要结果为图的整谱性理论的研究 开辟一些新的研究方向，增添新的研究活力同时，探索如何有效地使用高性 能计算机这一强有力的工具，快捷、及时、准确地得到图的谱的整数解 卒论文主要研究了“图的整谱性理论及其解的计算机搜索”，选题属于本 学科前沿，是国内外非常活跃的研究领域其主要研究内容和主要研究成果 如下： 本论文的主要研究内容为： 1 ，主要研究直径为4 ，5 ，6 和8 整树及其解的计算机搜索 2 、主要研究整谱图的几种新的构造方法和一些特定图的整谱性问题 3 、主要研究完全r 部整图及其解的计算祝搜索。 4 、主要研究正则拉普拉斯整图和正则整图及其生成树数目的计算问题 本论文的主要研究成果为： 1 、通过粘接两棵树的中心，构造了几类新的直径为4 的整树k i ，。丁( m ，f ) 和直径为6 的整树k i ，。丁( r ，m ，t ) ，并利用数论知识，以计算机为工具，证 明了这些直径为4 和6 的整树新类都有无穷多个。所得结果与已有文献中所 给出的结果都不相同。这对在此基础上构作直径更大的整树会有所帮助。 2 、给出了一些直径为4 ，6 和8 的整树新类，并利用经典数论，以计算 机为工具，证明了这些整树新类都有无穷多个也证明了寻找这样的整树问题 等价于去求一些特定的不定方程解的问题并用不同的方法独立地证明了p h f c 和r n e d e l a 在1 9 9 8 年首次证明的存在无穷多个直径为8 的平衡整树的 结论，而且我们所给出的直径为8 的整树与他们所给出的完全不同。 3 、从新的角度构造了直径为4 的所有树的一般特征多项式得到了几类 新的直径为4 的整树它们与已有文献中的结果都完全不同。这为彻底解决 直径为4 的整树提供了薪的思路 4 、利用计算机搜索，并分析结果，从而得到了几类新的直径为4 ，6 和 8 的整树这些整树类中绝大多数都有无穷多个这对在此基础上构造别的整 l l l 第i v 页摘要 树会有所帮助 5 、利用连边和粘接的方法构造了直径为5 和6 的整树新类，并利用计 算机，数论知识及其相关的理论得到这些整树新类都有无穷多个这些结果与 已有文献中的结果都不同构造的直径为5 和6 的整树具有新的结构，使在 此基础上构造直径为7 乃至更大直径的整树有可能实现。 6 、用几种新的方法构造了一些整图新类，并证明了这些整图新类有无穷 多个同时证明了寻找这样的整树问题与求解一些特定的不定方程的问题等 价 7 、给出了完全r 部图是整图的一个充分必要条件，并巧用汁算机和数论 知识给出了构造任意多个这样的整图新类的方法并证明了寻找这样的整图 问题与求一些不定方程的解的问题等价这些完全r 部整图的发现是对寻找 这样的整图的一个新的贡献推广了m f ( o i t m a n 关于完全三部整图的结论。 8 、利用矩阵的理论给出了图 峰一 的谱及其特征多项式，同时也得 到了其补图、线图、线图的补图及补图的线图的特征多项式也给出了这些 图的生成树数目的计算公式并证明了这些图不仅是整图而且是拉普拉斯整 图拉普拉斯整谱图是图的整谱性研究方面又一新的研究方向这些结果推 广了国际图论大家f h a r a r y 和a s c h w e n k 的一个重要结果，同时这些整 图的发现是对寻找这样的整图的一个新的贡献。 最后，我们对本论文的结果加以总结，并对进一步的研究给予展望。 关键词：图的谱，整谱图，整谱树，直径，邻接矩阵，拉普拉斯整图，不定方 程，同谱图，生成树数目计算，计算机搜索，特征多项式， 9 - 多项式。 a b s t r a c t a b s t r a c t t h i st h e s i sc o n t r i b u t e st ot h et h e o r yo fi n t e g r a lg r a p h sa n dc o m p u t e r s e a r c h i n go ft h es o l u t i o n sf o rs o m ec h a r a c t e r i s t i cp o l y n o m i a l so fg r a p h sf r o m c h a p t e r2t oc h a p t e r5 ，s o m en e wf a m i l i e so fi n t e g r a lt 【o e sw i t hd i a m e t e t h4 5 ，6a n d8a r ec h a r a c t e r i z e db ym a k i n gu s et h e o r yo fn u m b m a n dc o m p u t e r s e a r c h i n g s o m em e t h o d so fc o s t r u c t i n gi n t e g r a lg r a p h sa r eo b t a i n e di t lc h a p t e r6 i nc h a p t e r7 ，w eg i v eau s e f u ls u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nt o l c o i n p l e t e f - p a i t i t eg r a p h st ob ei n t e g r a l ，f l , o mw h i c hw ec a nc o n s t r u c ti n f i n i t e m a n yn e v vc l a s s e so fs u c hi n t e g r a lg r a p h s i nt h el a s tc h a p t e r ，c h a p t e r8v c e p r o v es o m ec l a s s e so fr e g u l a rg r a p h sa r en o to n l yi n t e g r a lb u ta l s oi a p l a c i a n i n t e g r a l 婚pa l s og i v et h en m r t b e r so fs p a n n i n gt r e e sf o rs u c h9 1a p h s t h et e l m n o l o g ya n dn o t a t i o n sc a nb ef o u n di nt h ef i r s tc h a p t e ra tt h e s a n l et i m e ，w eg i v eab r i e fi n t r o d u c t i o no ft h em a i nr e s u l t so ft h et h e s i s i nc h a p t e r2 ，s o m en e wf a m i l i e so fi n t e g r a lt r e e sw i t hd i a n i e t e r s4a n d6 a r ec o n s t r u c t e db yi d e n t i f y i n gt h ec e n t e r so ft w ot i e e sa l lt h e s ec l a s s e sa r e i n f i n i t e t h e ya i ed i f f e r e n tf r o mt h o s ei ne x i s t i n gl i t e r a t u r e s t h i si san e w c o n f ti h u t i o nt ot h es e a r c ho fi n t e g r a lt r e e s eb e l i e v et h a ti t i su s e f l i if ( ) r c o n s t r u c t i n go t h m i n t e g r a lt r e e s i nc h a p t e r3 ，s o m en e wf a m i l i e so fi n t e g r a lt r e e sw i t hd i a m e t e r s4 ，6a n d 8a r eg i v e n a l lt h e s ec l a s s e sa r ei n f i n i t e t h e ya r ed i f f e r e n tf l o mt h o s ei n e x i s t i n g i t e r a t n r e sw ea l s op r o v et h a tt h ep r o b l e mo ff i n d i n gi n t e g r a lt f e e s o fd i a m e t ers4 6a n d8i se q u i v a l e n tt ot h ep r o b e m ( ) fs o l v i n gd i o p h a n t m e e q u a t i o n s w eb e l i e v et h a ti t i s u s e f u lf o rc o n s t r u c t i n go t h e ri n t e g r a lt r e e s t oo u rk n o w l e d g e ，p h i ca n dr n e d e l ap r o v e df i r s t l yt h a tt h e r ea r ei n f i n i t e l y m a n yb a l a n c e di n t e g r a lt r e e so fd i a m e t e r8i l l 1 9 9 8 i nf a c t w ea l s op r o v e i n d e p e n d e n t l yt h i sr e s u l tb yu s i n gad i f f e r e n tm e t h o d ，a n dt h e s ei n t e g r a lt r e e s o fd i a m e t e r8a r ed i f f e r e n tf r o nt h e i rr e s u l t s i nc h a p t e r4 ，s o n i cu e wf a m i l i e so fi n t e g r a lt r e e sw i t hd i a t n e t e ts 4 ，6a n d 8a r eg i v e nb ym a k i n gu s et h e o r yo fn u m b e ra n dc o m p u t e rs e a r c h i n gm o s to f t h e s ec l a s s e sa r ei n f i n i t e t h e ya r ed i f f e r e n tf r o mt h o s ei ne x i s t i n gl i t e r a t u r e s t h i si san e wc o n t r i b u t i o nt ot h es e a r c ho fi n t e g i a lt r e e s ，w eb e l i e v et h a ti t i s u s e f u lf o rc o n s t r u c t i n gu t h e ri n t e g r a lt l e e s f i n a l l y 、w ep r o p o s es e 、。e r a b a s l e v 第v i 页 a b s t z a c t 一一一 【) p e np r o b l e m so ni n t e g r a lt r e e sf o rf u r t h e rs t u d y i i lc h a p t e r5 s o m en e wf a m i l i e so fi n t e g r a lt t e e sw i t hd i a m e t e r s5a n d6 a r ec o n s t r u c t e db ym a k i n gu s et h e o r yo fn u m b e ra n dc o m p u t e rs c u lt h i n g a l l t 1 e s ec l a s s e sa r ei n f i n i t et h e ya r ed i f f e r 。e n tf r o mt h o s ei ne x i s t i n gl i t e r a t u r e w ea l s op r o v et h a tt h ep r o b l e mo ff i n d i n gi n t e g r a lt r e e so fd i a m e t e r s5a n d 6i s e q u i v a l e n tt ot h ep r o b l e mo fs o l v i n gs o r t i ed i o p h a n t , i n ec , q u a t i o n s t h e d i s c o v e r yo ft h e s ei n t e g r a l t r e e si san e wc o n t r i b u t i o nt ot h es e a r c ho fs u c h t i e e s i nc h a p t e r6 ，s o m en e wc l a s s e so fi n t e g r a lg r a p h sa r eg i v e nb vt w ou e w w a y s w ea l s op r o v et h a tt h ep i o b l e m o ff i n d i n gs u c hi n t e g r a lg r a p h si se q u i v a l e n tt ot h ep r o b l e mo fs o l v i n gd i o p h a n t i n ee q u a t i o n s s o m e c l a s s e sa r ei n f i n i t e t h ed i s c o v e r yo ft h e s ec l a s s e si san e wc o n t r i b u t i o nt ot h es e a r c ho fs u c hi n t e g r a lg r a p h s i nc h a p t e r7 ，w eg i v eau s e f o ls u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rt o n i p l e t er p a r t i t eg r a p h st ob ei n t e g r a l 、f r o mw h i c hw ec a nc o n s t r n c ti n f i n i t em a n y n e wc l a s s e so fs u c hi n t e g r a lg r a p h s t h ed i s c o v e r yo ft h e s ei n t e g r a lc o m p l e t e f - p a r t i t eg r a p h si s an e wc o n t r i b u t i o nt ot i r es e a r c ho fs u c hi n t e g r a lg r a p h s i nf a c t ，mr o i t m a n sr e s u l to nt h ei n t e g r a lc o m p l e t et r i p a r t i t eg r a p h si sg e n e r a l i z e di nt h i sc h a p t e r ( s e ea l s om r o i t m a n ，a ni n f i n i t ef a m i l yo fi n t e g r a l g r a p h s ，d i s c r e t em a t h5 2 ( 2 - 3 ) ( 1 9 8 4 ) ，3 1 3 3 1 5 m r8 6 a ：0 5 0 8 9 ) f i n a l l y ，w e p r o p o s es e v e r a lb a s i co p e np r o b l e m sf o rf l u t h e rs t u d y i nc h a p t m8 ，l e tk v 【一l 】d e n o t et h e ( p 1 ) 一r e g u l a ig r a p hw i t hp ( p 一1 ) v e t 。r i c e s w es h a l lg i v ei t ss p e c t r aa n dc h a r a c t e r i s t i cp o l y n o m i a lh o mt h e t h e o r yo nm a t r i c e s i nf a c t ar e s u l to ff h a r a r ya n da js c h w e n ko i lar e g u l m i n t e g r a lg r a p hi sg e n e r a l i z e di nt h i sc h a p t e r w ed e r i v et h ec h a r a c t mi s t i c p o l y n o m i a l sf o ri t sc o m p l e m e n tg r a p h ，i t sl i n eg r a p h ，t h ec o m p l e m e n tg r a p h o fi t sl i n eg r a p ha n dt h el i n eg r a p ho fi t sc o m p l e m e n tg r a p h w ea l s oo b t a i n t i l en u m b e r so fs p a m f i n gt r e e sf o rs u c hg r a p h s w ea l s op r o v et h e s eg r a p h sa r e n o to n l yi n t e g r a lb u ta l s ol a p l a e i a ni n t e g r a l t h ed i s e o w ! i yo ft h e s ei n t e g r a l g r a p h si san e wc o n t r i b u t i o nt ot h es e a r c ho fi n t e g r a lg r a p h s k e y w o r d s ：g r a p h ss p e c t r u m ，i n t e g r a lg r a p h i n t e g r a lt t e e ，d i a m e t e r ，d i o p a n t i n ee q u a t i o n ，c h a r a c t e r i s t i cp o l y n o m i a l ，c o m p u t e rs e a i t h i n g ，o - 一p o l y n o m i a l ， l a p l a c i a ni n t e g r a l ，a d j a c e n c ym a t r i x 第一章绪论 第一章绪论 1 1 引言 图论属离散数学，是一门充满生机的学科随着现代科学的发展，图 论及其在物理、化学、计算机科学、运筹学、电子学、信息论、系统沧、网络 理论等方面的应用研究都取得了迅速的发展图论在以信息为持征的知识经 济时代有着广泛的实用背景 图论的历史可以追溯到1 7 3 6 年瑞士著名数学家e a l e r 解决k s n i g s b e r g 七桥问题但是在随后的两百年里，图论的发展非常缓慢这一时期，图论主 要研究了如四色问题( 1 5 8 2 年) 和h a m i l t o n 问题( 1 8 5 6 年) 等一些图论难 题；同时出现了以图作为工具去解决其它领域问题的成果，最有代表性的工作 是k i i c h h o f f ( 1 8 4 7 年) 和c a y l e y ( 1 8 5 7 年) 分别用树的概念去研究电网络方 程组问题和有机化合物的分子结构问题。进入二十世纪三十年代，出现了一大 批精彩的图论新理论和结果，如m e n g e r 定理( 1 9 2 7 年) ，k u r a t o w s k i 定理 ( 1 9 3 0 年) 和r a m s e y 定理( 1 9 3 0 年) 等等这些理论和结果为图论的发展奠 定了基础1 9 3 6 年，匈牙利数学家1 3 k s n i g 写出了第一本图沦专著有限图 与无限图的理论图论作为数学的一个新的分支已经基本形成1 9 3 6 年以 后，由于生产管理、军事、交通运输、计算机和通讯网络等领域中许多离散性 问题的出现，大大促进了图论的发展特别是进入2 0 世纪7 0 年代以来，大型 计算机的出现，使得大规模问题的求解成为可能。图论本身及其在物理学、化 学，生物学、地理学、运筹学、计算机科学、信息论、系统论、控制论、网络理 论、社会科学以及经济管理等学科领域中的应用研究都取得了突飞猛进的发 展。如：与电子学有关的大规模集成电路的分析与设计、印刷电路板的设计与 布线、逻辑电路的分析与故障诊断，以及计算机大型应用程序的开发；在系统 控制方面，要用信号流进行分析；在传递网与通讯方面，要用割集理论等等 因此，图论及其应用研究日益受到全世界从事理论研究的科学工作者和从事 应用研究的工程技术人员以及经营管理者的重视。 图论和计算机科学的关系非常密切目前几乎所有的计算机系本科生都 把图论作为离散数学或组合数学的一个重要组成部分来学习，一些学校还为 高年级本科生和研究生开设了专门的图论课程在国外，许多学校都有专门 从事图论及其应用的教学和研究人员同时，计算机科学的研究和发展，向图 论学科提出了新的研究课题、新的概念和新的方法特别是随着计算机科学 l 第2 页 第一章绪论 的长足发展，又给图论等学科注入了新的生机和活力，计算机科学已成为图论 发展的最主要的源动力之一。如我们经常会遇到计算机科学研究中的一些问 题，要求能对其建立图论模型，并探讨其求解方法。例如超大规模并行系统的 拓扑结构是处理器之间的互相连接的一种模式，而拓扑结构通常可以用图来 表示，于是图论为其研究提供了强有力的数学工具这样大大丰富了图论的 研究内容和应用，从而推动了图论学科的发展另一方面，图论是计算机科学 赖以发展的重要数学基础之一，图论的方法在计算机科学的研究中起到非常 关键的作用从大规模集成电路的设计到计算机通讯网络的构造；从计算机软 件的开发与调试到并行计算机拓扑结构的选择，图论理论和方法的应用比比 皆是近十年来，研究工作者就网络优化设计和分析中最关心的问题，如可靠 性、容错性、时间延迟、路由负载、模块化、可扩展性、并行算法的设计和实 现、故障诊断等热门问题，提出了大量的图论问题和图论参数这些问题和参 数的研究和解决，不但丰富了图论的研究内容和应用，而且从理论上为更精 确地度量大规模超级并行计算机系统的性能提供了理论依据，对网络的优化 设计、量化分析和性能评估都起到了重要作用。总之，图论在汁算机科学中， 如网络的优化设计、形式语言、数据结构、分布式系统和操作系统等方面都扮 演着重要的角色 在下面的四节里，我们将依次介绍本论文所用到的一些基本图论概念和 术语熟悉图论基本知识的读者可以跳过这一节直接阅读后面的内容，在需 要的时候再来查阅在本章的第三、四节，我们将介绍本论文所研究的主要问 题、国内外研究进展和在本论文中所得到的主要研究成果在本章的第五节， 介绍本论文的组织 1 2 图论的基本概念和术语 我们在这里介绍的图论概念和术语基本上与文献1 4 ，1 2 ，1 3 1 一致论文 中未加说明的概念和术语也请参见文献 4 1 2 ，1 3 为了便于阅读，在以后各 章中我们可能重复这里介绍的一些概念和术语 1 、图和简单图 一个图g 是指一个有序三元组( 1 ( g ) ，e ( g ) ，妒g ) ，其中g ) 是非空的 顶点集，e ( g ) 是不与v ( c ) 相交的边集，妒g 是关联函数，它使g 的每 条边对应于g 的无序顶点对( 不必相异) 若e 是一条边，而t - 和。是使得 妒g ( e ) = t t , u 的顶点，则称e 连接“和 ；顶点札和w 称为e 的端点。 5 1 2 图论的基本概念和术语第3 页 一条边的端点称为与这条边关联，反之亦然与同一条边关联的两个顶 点称为相邻的，与同一个顶点关联的两条边也称为相邻的。端点重合为一点 的边称为环，端点不相同的边称为连杆 一个图称为有限图，如果它的顶点集和边集都有限只有一个顶点的图 称为平凡图，其他的所有图都称为非平凡图一个图称为简单图，如果它 既没有环也没有两条连杆连接同一对顶点。本论文j l 研究有限无向简单图。 2 、顶点的度 图g 的顶点 的度d c ( v ) 是指g 中与 关联的边的数目，每个环算作 两条边。用6 ( c ) 和( g ) 分别表示g 的顶点的最小度和最大度。图的顶点 数和边数分别用符号v ( c ) 和f ( g ) 来表示在不致引起混淆的情况下，我们 用je ，e ，d ( ) ，5 和来分别代替v ( g ) ，e 【g ) ，一( g ) e ( g ) 、d a ，d ( g ) 和 a ( g ) 3 、正则图 称图g 是k 正则的，如果对所有u v ，都有d g ( , u ) = 每一对不 同的顶点都有条边相连的简单图称为完全图。一个有n 个顶点的完全图记 为 _ 另一方面，空图是指没有任何边的图。一个有礼个顶点的空图记为 e 。 4 、二部图 所渭偶图或二部图是指一个图，它的顶点集可以分成两个( 非空) 子集 x 和y ，使得每条边都有一个端点在x 中，另一个端点在1 7 中；这样一种分 类( x ，y ) 称为图的一个二分类完全二部图是具有二分类( x ：y ) 的简单二 部图，其中x 的每个顶点都与y 的每个顶点相邻；若 xi = m 而lyf = r z ， 则这样的图记为。，。称为星图完全，1 部图。是指将它的 p l + p 2 + + m ( = 几) 个顶点划分为t 1 个非空子集，即v = u u u u u 的图，这里k 表示非空两两不相交的顶点集，即眦i = m ，且l ：n k = a i j ，1s # ，jsr ，使得它的每个顶点与不在同一个子集中的所有顶点均相 连接。 5 、图的相等和同构 两个图g 和日称为相等，如果v ( g ) = y ( h ) ，e ( a ) = e ( h ) 和= o 两个图g 和h 称为同构，如果存在两个一一映射日：v ( g ) _ j 【，) ， 和西：e ( g ) _ e ( h ) ，使得砂g ( c ) = t r y 当且仅当函f ，( 庐( e ) ) = 0 0 0 0 ( , ，) ；这 样的一个映射对( 目，) 称为g 和h 之间的一个同构 第4 页第一章绪论 6 、子图 称图日是图g 的子图( 记为日g ) ，如果v ( h ) i ( g ) ，e ( h ) e ( g ) ，并且砂日是砂g 在e ( h ) 上的限制当日g ，但h g 时，则记 为hcg ，并且日称为g 的真子圈若h 是g 的子图，则g 称为h 的 母图g 的生成子图( 或生成母图) 是指满足v ( 打) = v ( g ) 的子图( 或 母图) h 假设v 是1 7 的非空子集以l “为顶点集，以两端点均在v 。中的边的 全体为边集所组成的子图，称为g 的由v ”导出的子图，记为g g i g 称为g 的顶点导出子图导出子图c v v 7 记为g v “若v = u ，则 把g 一 u 简记为g f 假设e 是e 的非空子集。以e 7 中的边的端点 的全体为顶点集，以e 为边集所组成的子图称为g 的由e 7 导出的子图，记 为g 【e ， ；g z 。】称为g 的边导出子图。边集为z z 的生成子图简记为 g e 7 ；它是从g 中删去e 7 中的边所得到的子图。 7 、补图、并图和联图 图g 的补图召是指和g 有相同顶点集v 的一个简单图，且满足：在百 中两个顶点相邻当且仅当它们在g 中不相邻。设g 和g 2 是g 的子图，若 g l 和g 2 没有公共顶点，则称它们是不相交的；若g 和g 2 没有公共边， 则称它们是边不重的。g 【和g 2 的并图g 、u g 2 是指g 的个子图，其顶 点集为l ( g t ) uv ( g 2 ) ，其边集为e ( g - ) ue ( g 2 ) ；类似地可以定义g t 和 g 2 的交图g ln g 2 且n g 表示7 0 个不相交的图g 的并不相交的两个图 g l 和g 2 的联图g l + g z 是指在g u g 2 中，把g l 的每个顶点和g 2 的每 个顶点连接起来所得到的图 8 、图的积运算 两个图g 。和g 2 的笛卡尔积g t g 2 定义为这样的一个图，其顶点集 为v ( a 1 ) xv ( g 2 ) ，g l g 2 的两个顶点( “l ，t 2 ) 和( u 1 ，u 2 ) 在g l g 2 中 相邻，当且仅当叭= u i 且乱2 和f 2 在g 2 中相邻，或者u 2 = 巩且“l 和”【 在g 。中相邻我们可以用递归的方法定义n 个图g 1 ，g 。，g 。的笛卡尔 积g 1 g 2 g 。k 个垃的笛卡尔积k 2 k 2 x 尬称为维 超立方图，简称为超立方图，记为m 9 、路和连通 g 的一条途径是指一个有限非空序列w = u o c l7 ) i t e 2 u 2 e k u k ，它的项 交替地为顶点和边，使得对1s isk ，e ：的端点是仇一l 和吡。称w 是从 咖到的一条途径，或一条( 1 ：0 ，) 途径顶点v 0 和分别称为w 的起 1 2 图论的基本概念和术语第5 页 点和终点，而u l ，v 2 ，一，啦一称为的内部顶点。整数k 称为的长。 若途径w 的顶点和边均互不相同，则称为路类似地，一条起点为”o ， 终点为”k 的路称为( u o ，”k ) 路 g 的两个顶点u 和u 称为连通的，如果在g 中存在( ，川，) 路连通是 顶点集v ( a ) 上的一个等价关系于是就存在对1 7 ( ( ? ) 一个分类，把g ) 分 成非空子集k ，l ；，圪，使得两个顶点是连通的当且仅当它们属于同一子 集子图a v 1 ，g 】，g 屹 称为g 的连通分支。若g 只有一个连通分 支，则称g 是连通的；否则称g 是不连通的。g 的连通分支数记为“( g ) 1 0 、圈和距离 称一条途径是闭的，如果它有正的长且起点和终点相同。若一条闭途径 的起点和内部顶点各不相同，则称它为圈长为k 的圈称为k 圈，记为g ； 3 圈常称为三角形 若在图g 中顶点u 和u 是连通的，则u 和”之间的距离d 。( “”) 是g 中最短路( u ，w ) 的长；若没有路连接u 和”，则定义如( “，t ，) 为无穷大。 1 1 、关联矩阵、邻接矩阵和拉普拉斯矩阵 对于任意图g ，对应着一个v e 矩阵，称为g 的关联矩阵设 ? j l ，u 2 ，和e 1 c 2 ，e 。分别表示g 的顶点和边，则g 的关联矩阵是指 矩阵m ( g ) = o 】1 其中r r z i j 是和e j 相关联的次数( 0 ，1 或2 ) 。伴随干g 的另一个非常重要的矩阵是邻接矩阵；这是一个v v 矩阵a ( c ) = f a 。1 ， 其中。巧是连接仇和码的边的数目设d ( v 。) = d c ( v 。) 为顶点的度数，简 记为d i ，并设d ( g ) = d i a g d t ，d 2 ，d 。 为图g 的度对角矩阵。则称矩阵 l a p ( g ) = d ( g ) 一a ( g ) 为拉普拉斯( l a p l a c e ) 矩阵 1 2 、直径、树、有根圉和线图 图g 的直径是指图g 的两个顶点之间的最大距离不包含圈的图称为 无圈图，也称为森林连通的无圈图称为树 图g 中有一个顶点u 与图g 的其它顶点相区别，则该顶点“称为图g 的根点或简称为根这个图g ，称为有根图。设图一g 是联结，个图 g 的根点到一个新的顶点础得到的图图k l ，g 是将星图l 、，的中心。 与图g 的根点u 粘接在一起得到的图 一棵树的中心z ( t ) 有两种情形： ( i ) 若树t 的直径是偶数，则树丁 的中心是一个顶点；( i i ) 若树t 的直径屉奇数，则树的中心是一条边如果 到树丁的中心z ( t ) 具有相同距离的所有点都有相同的度数的树，则称树 丁是平衡的显然，一棵平衡树( 没有度为2 的顶点) 的结构被它的直径 第6 页第一章绪论 的奇偶性和一序列( ”，n 。，n ，) 所决定，这里女是树丁的半径，而n ， ( = l ，2 ，k ) 表示树的一个距其中心z ( t ) 为k j 的后继数的总个数。一 般地，k ( i = l ，2 ，) 总代表大干等于2 的整数直径为2 和2 + l 的乎 衡树我们分别用符号丁( ，n t “，n t ) 和t ( 1 ；“女，n 一，n 。) 来