（基础数学专业论文）一类含奇圈图的谱确定.pdf

青海师范大学学位论文使用授权声明 青海师范大学、中国科学技术信息研究所、国家图书馆 有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部 或部分内容。论文的公布( 包括刊登) 授权由青海师范大学 研究生部办理。 研究生签名：叩沮 一类含奇圈图的谱确定 摘要 图g 被认为是谱确定的当且仅当任何与它同谱的图日，即满足矽( ，a ) = 咖( g ，a ) ，有g 与日同构本文利用了图的一些不变量构造了参数，同时也给 出了参数的一些性质在i i = 一1 的图族里，找出了一类特殊的含奇圈图，利用参 数的性质和其它一些结果，对这类含奇圈图进行了谱确定 第一章中简单介绍关于谱确定目前已有的一些结果 第二章主要介绍了基本概念和引理，为后面两章准备 第三章引入了参数，给出了参数的定义和性质以及相应的证明 第四章首先给出三个引理的证明，然后再利用这三个引理给出了主要结果的证 明 第五章对本文的内容进行了总结，指出了研究工作中需要进一步研究的问题， 并对未来的工作进行了展望 关键词：谱确定；参数h ；含奇圈图 t h es p e c t r a lc h a r a c t e r i z a t i o no fg r a p h w i t ho d dc i r c u i t s a b s t r a c t a g r a p hg i ss a i dt ob ed e t e r m i n e db yi t ss p e c t r u mi ff o ra n yg r a p hh ，( 日，a ) = 咖( g ，入) i m p l i e st h a th i si s o m o r p h i ct og i nt h i sp a p e r ，w eg i v et h ep a r a m e t e ri i ，w h i c h i sr e l a t e dt os o m eg r a p hi n v a r i a n t s s o m ep r o p e r t i e so f1 10 r eg i v e na l s o i nt h o s eg r a p h s w i t hi i = - 1 ，w ef i n das p e c i a lg r a p hw i t ho d dc i r c u i t s b yt h er e s u l t s ，w es h o wt h a tt h e s p e c i a lg r a p hw i t ho d dc i r c u i t si sd e t e r m i n e db yi t ss p e c t r u m i nc h a p t e r s1 ，w ei n t r o d u c es o m ek n o w nr e s u l t so ns p e c t r a lc h a r a t e r i z a t i o n i nc h a p t e r s2 ，w ei n t r o d u c eb a s i cn o t a t i o n sa n ds o m el e m m a s ，w h i c hp r e p a r ef o r f l l o w i n gt w oc h a p t e r s i nc h a p t e r s3 ，w eg i v et h ed e f i n i t i o na n ds o m ep r o p e r t i e so fp a r a m e t e ri ia n dt h e i r p r o o f i nc h a p t e r s4 ，f i r s t ，w eg i v et h ep r o o fo ft h r e el e m m a s b yt h er e s u l t s ，w eg i v et h e p r o o fo fm a i nr e s u l t w ec o n c l u d ei nc h a p t e r5o ft h et h e s i sb yd i s c u s s i n gs o m ep r o b l e m sf o rf u r t h e r r e s e a c h k e y w o r d s ：s p e c t r a lc h a r a t e r i z a t i o n ；p a r a m e t e r ；ag r a p hw i t ho d dc i r c u i t s 2 1 3 本文内容的安排4 第二章基本概念和引理 2 1 基本概念与术语5 2 2 基本定义与引理5 第三章参数i i 3 1 参数的定义7 3 2 参数的性质7 第四章含奇圈图的谱确定 4 1 主要引理1 3 4 2 主要结果5 7 第五章结束语 5 1 本文研究的主要工作5 9 5 2 可进一步研究的问题5 9 参考文献6 0 致谢：6 2 附录一作者攻读硕士学位期间参加的科研项目6 3 附录二作者攻读硕士学位期间完成和发表的论文6 4 2 合物的骨架结构可用个图来表示，其分子中电子的能级实际上是相应的图的特征 值，而分子的稳定性等化学性质与分子结构图的谱及相应的特征向量密切相关；另 一方面，图的谱包含着大量的有关图的组合结构方面的信息，可以用来研究图论中 的大量问题譬如，谱技术一直是图论中一个非常重要的工具，可以用来对付图论 中很多困难的问题一尽管这些问题表面上可能与谱没有任何关系我们举几个谱技 术的运用起着关键作用的例子：h o f f m a n 和s i n g l c t o n 给出了所有可能的直径为2 和 3 的m o o r 图这惊人的结果；l a v a s z 利用谱方法确定出了长期未解决的五边形侥 的s h a n n o n 熵问题；a l o n 和m i l m a n 则利用图的第二大l a p l a c e 特征值来研究图的 扩展性，这性质在通讯网络中有重要作用；最后一个例子是组合优化中一个问题 一图的最大割问题，熟知其是n p h a r d 问题，但是可以用图的l a p l a c e 特征值为工具 来求近似解 在过去5 0 年里，图的谱理论得到广泛的研究，已有大量的研究论文不断发表， 有关这方面成果可见专著【3 ，2 2 ，2 3 ，2 4 】及其参考文献 1 2 谱确定的发展与现状 图g 被认为是谱确定的当且仅当任何与它同谱的图都与它同构对于谱确定 这方面内容，主要有关于邻接谱确定、拉普拉斯谱确定和无符号拉普拉斯谱确定， 下面罗列的图都已被证明由邻接谱确定： ( 1 ) 路r 和路的补图巧，完全图和正则的完全二部图m 圈q 和圈的 补图乙：，见文献【4 ，5 ，6 】 ( 2 ) 三叉树t ( 1 1 1 2 1 3 ) 指的是一棵树含有一个3 度点口，使得t ( t 1 ，1 2 ，f 3 ) 一口= j p 2 。u 局：u 旦。，其中( 1 l ，1 2 ，1 3 ) ( a ，a ，2 a 一2 ) ，见文献【1 8 ，2 1 ( 3 ) l o l l i p o p 图，它是通过重合圈g ，上一点和路p s 。的一个端点得到，见文献 【2 ，1 0 ( 4 ) 所有谱半径在2 至、2 + 怕的连通图，见文献【7 】 3 ( 5 ) s a n d g l a s s 图，即通过一条路的两个端点连接两个三角形得到，见文献【1 4 】 ( 6 ) p 一图记作o ( i ，j ，后) ，它是通过两定点连接3 条内部不相交的路构成，除了两 端点外，这3 条路的内部点数分别为i ，j ，k 哑铃图记作d ( a ，b ，c ) ，它是由路r + l 的 两端点连接两个不相交的圈q ，q 得到，见文献f 1 9 ，2 0 ，2 5 】 关于这方面内容还要继续研究的问题是对于结构更为复杂的单圈图其谱确定情 况如何这块研究的主要趋势是寻找更多能用拉普拉斯确定或能用无符号拉普拉斯 谱确定的图 1 3 本文内容的安排 第一章中简单介绍了两方面内容，一方面是关于谱确定这块研究的学术背景和 研究意义，另一方面是关于谱确定目前已有的一些结果 第二章主要介绍了基本概念和引理，为后面两章准备 第三章引入了参数，给出了参数的定义和性质以及相应的证明 第四章首先给出三个引理的证明，然后再利用这三个引理给出了一类含奇圈图 的证明 第五章对本文的内容进行了总结，指出了研究工作中需要进一步研究的问题， 并对未来的工作进行了展望 4 第二章基本概念和引理 ，本论文只研究有限简单图文中未加说明的图论术语见文 我们可能经常要用到下面的一些概念和术语 对于一个有佗( g ) 个顶点，m ( c ) 条边的图g ，用v ( g ) 表示图g 顶点的集合， 用e ( c ) 表示图g 边的集合对口y ( g ) ，n g ( v ) = u l u y ( g ) ，u 钉e ( g ) ) 和d g ( t 7 ) 表示顶点v 在g 中的的度对任意v l ，v 2 y ( g ) ，设n g ( v l v 2 ) = n g ( v 1 ) u n g ( v 2 ) 一 v l ，v 2 如果v l v 2 e ( g ) ，则d v ( 口l 睨) = i n g ( v l v 2 ) i 设u y ( g ) ，e e ( g ) 和 c k ，k 3 是g 中的圈令g u ，g e 和g 一仉分别表示由g 删掉顶点口、边e 和圈以上所有点得到的图设日是g 的子图，( h ) e 表示由g 中边集e ( h ) 导 出的子图设两个g 和h ，guh 表示这两个图的不交并对于一个n ( g ) 个顶点， m ( c ) 条边的图g ，它的邻接矩阵a ( g ) 是个礼n 的矩阵，其中第i 行第j 列元 素是1 当且仅当顶点和顶点相邻，否则为0 把a ( g ) ，k ( c ) = d ( g ) 一a ( g ) ，q ( g ) = d ( g ) + a ( c ) 这三个矩阵的特征根集合 分别称做邻接谱，拉普拉斯谱和无符号拉普拉斯谱d ( g ) 表示g 的度矩阵 2 2 基本定义与引理 引理2 2 1 【3 】对图g ，t 口e ( g ) ，则 p a ( g ，入) = 既( g 一删，入) 一心( g t 一u ，入) ， 其中札可是g 的割边 引理2 2 2 【3 】设图g 有k 个分支g 1 ，g 2 ，g k ，则p a ( c ，入) = 坠1 p a ( c ，a ) 引理2 2 3 【3 l 对图g 的任一顶点u ，我们有 ( 1 ) p a ( g ，a ) = 入p a ( g t ，a ) 一伽嘣。p a ( g u 一口，a ) 一2 gp a ( g 一瓯，入) ， ( 2 ) p a ( g ，入) = p a ( g 一札口，入) 一p a ( g u 一 ，入) 一2 g 。p a ( c 一瓯”，入) 引理2 2 4 【3 】设图g 有n 个顶点和p a ( c ，a ) = k o b k a n ，则 ( 1 ) b o = 1 ，b l = 0 ， ( 2 ) 6 2 = 一m ，b 3 = 一2 n o ( k 3 ) ( 3 ) b 4 = n o ( 2 ，2 ) 一2 n c ( c 4 ) ， 。( m 1 ) 一1 蒹，霹- 2 9 v ( c 4 ) 引理2 2 5 【3 】设g 是连通图，日是g 的真子图，则a i ( h ) 1 ，i z + ) 的个数，且k 取图中最 小奇圈的的长度 3 2 参数的性质 定理3 2 1 设图g 和h 满足p a ( a ，a ) = p a ( h ，a ) ，其中k ( k = 2 i + 1 ，i l ，后，i z 十) 是g 和h 中最小奇圈的长度，则 ( g ) = ( 日) 证明因为p a ( g ，a ) = p a ( h ，a ) ，则b 4 ( g ) = b 4 ( h ) ，m ( g ) = m ( 日) ，n ( g ) = 礼( 日) ， g a ( g ) = n h ( c k ) 由定义3 1 ，故( g ) = ( h ) 口 定理3 2 2 设图g 有t 个分支g 1 ，g 2 ，g ：l ，g ，则 ( g ) = h ( g d 证明( 1 ) 当m ( g ) = 0 ，由定义3 1 ，结论显然成立 ( 2 ) 当m ( g ) 0 ，由定义3 1 和引理2 1 4 ，则有 哟h ( 似妒1 ) 一( 州2 。) 刈一 吉霹一2 n c j ( q ) + g ，( 瓯) + m ( c j ) 一n ( q ) n ( c j ) = 2 m ( c j ) 一吉毋一2 n o j ( 瓯) + n 0 3 ( c k ) + m ( g j ) 一几( g j ) 其中1 j t 所以 n ( c d = 2 e m ( c i ) 一去d 2 - 2 n a ；( q ) + n g 。( 仇) + m ( g i ) 一几( g i ) 则有 妾c q ，= e ( m 2 + 1 ) 一( m 2 1 ) + ， 一寺群一2 n c ( c 4 ) + g ( q ) + m ( g ) 一礼( g ) 。r e v ( c ) = n ( c 1 口 定理3 2 3 设g 是有几个点的图，任意边u 口e ( g ) ，则 儿【“) = 儿( “一u v ) 一d c ( u v ) 一z 川1 u 【) 一d l u v ( u s ) + v t u 【u 詹j + z ， 其中t 蚶( q ) ， ( g ) 分别表示含边t u 的c 4 的个数和含边删的长度为k ( k = 2 i + 1 ，i 1 ，i z + ) 的圈的个数 证明已知n ( g ) = n ( c 一伽) ，m ( c 一仳u ) = m ( c ) 一1 由引理2 2 4 ，则有 b 4 ( c - u v ) 2 ( 州弘1 ) 一1 蒜，邪) - 2 ( q ) 2 ( m 笋) 习1 洲乳邪眦( 乳训 + d ：( g 一乱 ) 】一2 n c 一让，( q ) ， 已知d t ( g u u ) = d t l ( g ) 一1 ，也( g t t t ，) = d t ，( g ) 一1 ，g 一伽( c 4 ) = g ( q ) 一0 ( c 4 ) 且当i 譬 仳，影) ，也( g ) = 也( g 一删) ， 又因d e ( u v ) = d t t ( g ) + d t i ( g ) 一帆。( g ) 一2 ，则计算得， 6 4 ( g - u v ) = ( 州之“) _ m ( 午扣蒹，靴( 郴m ( g ) ) + 2 】 一2 ( n c ( q ) 一帆。( q ) ) = b 4 ( g ) 一m ( c ) + d e ( u 钞) + 帆。( 伤) + 1 + 2 帆。( q ) 由定义3 1 ， n ( c u v ) = b 4 ( c 一乱u ) 一( m 写) 一2 ) + n c 一。( q ) + 1 + ( m ( g ) 一1 ) 一佗( g ) 已知g 一删( 吼) = g ( 仇) 一帆。( 瓯) 在n ( c t l u ) 中，用b 4 ( c 一仳t ，) 的表达式 代入n ( c 一伽) ，则可得到 n ( g - u v ) = 6 4 ( g ) 一m ( g ) + d g ( u ) + 帆。( q ) + 1 + 2 帆。( q ) 一( m 鼍一2 ) + g ( q ) 一帆。( q ) + 1 + m ( c ) 一1 一n ( c ) = n ( c ) 一2 + d g ( 札口) + 帆。( 晚) + 2 帆。( q ) 一虬。( 瓯) 口：圈 g l l 口幽幽同 g 1 3g 1 4 g 1 5g a b 凹：凹口凹0 凹u g 1 8 凹。凹口 g 2 0g 2 1 叵一坷 韧 g 2 3 u ” g 2 2 图1 ( n ( c ) = 1 ，0 ，一1 的连通图) 定理3 2 4 设g 是连通图，则 ( 1 ) ( g ) l 等号成立当且仅当g 笺仇( 七= 2 i + l ，i 1 ，i z + ) ( 2 ) h ( c ) = 0 当且仅当g rug q ，c k ) ug aug 4ug 5 ( 3 ) i i ( g ) = - 1 当且仅当g c d 8 is2 3 证明( 1 ) 对m ( c ) 进行归纳假设因为i i ( k t ) = 一1 ，n ( k 2 ) = 0 ，则当m ( c ) 1 ，有 ( 1 ) 式成立 假设m ( g ) 2 取e e ( g ) 使得( g e ) e 是连通的显然，如( e ) 1 假设 n ( c e ) 1 由定理3 2 3 ，则有 n ( c ) = n ( c e ) 一d g ( e ) 一2 e ( c 4 ) 一e ( q ) + e ( 敛) + 2 9 罂谶 需要讨论以下三种情况 情况1 如果e ( 仇) 2 ，因为d a ( e ) 2 e ( q ) + e ( 瓯) + 2 e ( 仇) ， 所以一d g ( e ) 2 e ( q ) 一e ( 岛) + e ( 瓯) + 2s0 ， 由归纳假设，n ( a ) 1 情况2 如果e ( 仇) = 0 ，则 n ( a ) = r i ( a e ) 一d g ( e ) 一2 e ( q ) 一e ( 岛) + 2 子情况2 1 如果d g ( e ) = l ，则e 是g 的一条悬挂边， 则 n ( a ) = n ( a e ) e 一2 e ( q ) 一n e ( c 3 ) ，由归纳假设，n ( a ) 1 子情况2 2 如果e 不是g 的条悬挂边和d g ( e ) 2 ，则 n ( c ) = r i ( c e ) 一d c , ( e ) 一2 n 。( c 4 ) 一n 。( c 3 ) + 2 ，由归纳假设，n ( a ) 1 情况3 如果e ( 吼) = 1 ，则d a ( e ) 22 和 n ( a ) = n ( a e ) 一d g ( e ) 一2 札( q ) 一e ( 伤) + l + 2 子情况3 1 若d g ( e ) = 2 ，则e ( q ) = 0 ，e ( 岛) = 0 ，从而 n ( a ) = n ( a e ) ，由归纳假设，n ( a ) 1 子情况3 2 若d g ( e ) 3 ，则 d g ( e ) 2 e ( q ) + 札( 岛) + 1 ， 一d g ( e ) 一2 e ( a ) 一札( g ) + 3 - 2 e ( q ) 一e ( 岛) 一1 2 n e ( q ) 一e ( g ) + 3 ， 而 一2 e ( q ) 一e ( 伤) 一1 2 e ( 瓯) 一e ( 岛) + 3 = 一4 e ( 瓯) 一2 2 v 。( g ) + 2 ， 因为d g ( e ) 3 ，所以e ( q ) 和e ( 岛) 中至少有一个大于0 故一a n e ( c 4 ) 一2 n 。( c 3 ) + 2 0 ，由归纳假设，n ( c ) 1 ( 2 ) 对m ( a ) 进行归纳假设由i i ( k x ) = - 1 ，u ( k 2 ) = 0 ，如果m ( a ) s1 ，则( 2 ) 成立 假设m ( a ) 22 取e e ( a ) 使得( g e ) z 是连通的由定理3 2 3 ，有 0 = n ( a e ) 一d g ( e ) 一2 e ( q ) 一e ( 岛) + e ( 仉) + 2 ， 已知n ( a ) ( g e ) ，需要讨论以下情况： 情况1n ( a e ) = 1 由( 1 ) 知道g e 是仉，而且d g ( e ) + 2 n 。( c 4 ) + n 。( c 3 ) 一n 。( c k ) 一3 = 0 于是，n , ( c k ) = 0 ，这样，d g ( e ) + 2 e ( q ) + n e ( c 3 ) = 3 1 0 4 ，也不能满足上式，所 2 = 0 子情况2 1 若e ( 伉) = 0 ，则d g ( e ) + 2 e ( c 4 ) + e ( g ) = 2 当d g ( e ) = 2 ，n 。( c 4 ) = n 。( c 3 ) = 0 ，则( g e ) e p n ，故g 垒g ，几3 ，4 ，k 或 g 垒p n 当d g ( e ) = 1 ，e ( 岛) = 1 ，则g e 竺p 3 ，故g 竺岛 子情况2 2 若e ( q ) = 1 ，则d c ( e ) + 2 e ( 瓯) + n 。( c 3 ) = 3 当d g ( e ) = 2 ，e ( c 3 ) = 1 ，这不可能 当d g ( e ) = 3 ，e ( o ) = e ( 岛) = 0 ，由归纳假设( g e ) e g au 尸n 故g 竺g 4 或g 笺g 5 或g 望岛 ( 3 ) 若i i ( c ) = 一1 ，由递推关系， - 1 = n ( c e ) 一d g ( e ) 一2 e ( q ) 一e ( q ) + e ( 瓯) + 2 分以下情况讨论： 情况1 若n ( c e ) = 1 ，则g e 兰g ，而且 d g ( e ) + 2 e ( q ) + e ( 岛) = 4 由于g e 垒瓯，故d g ( e ) 2 当d ；g ( e ) = 2 ，e ( c 4 ) = 1 ，e ( c 3 ) = 0 ，这种情况不成立 当d g ( e ) = 2 ，e ( a ) = 0 ，e ( 岛) = 2 ，这种情况也不成立 当d g ( e ) = 4 ，e ( c 4 ) = e ( c 3 ) = 0 ，这时g 中会出现比瓯更小的奇圈，故不 成立 情况2 若( g e ) = 0 ，则 d g ( e ) + 2 e ( 劬) + e ( a ) 一e ( q ) = 3 当e ( 仉) = 0 ，则d a ( e ) + 2 n 。( c 4 ) + w e ( 仍) = 3 若d g ( e ) = 1 ，e ( c 4 ) = 1 ，e ( g ) = 0 ，这种情况不成立 若d g ( e ) = 2 ，n 。( c 4 ) = 0 ，e ( q ) = 1 ，则( g e ) e 兰p n ，故g g l o 若d g ( e ) = 3 ，n 。( c 4 ) = e ( 仍) = 0 ，则( g e ) e g 2ug ：i ，故g g l ou g l 4u g l 5 当g 。( c k ) = 1 ，贝0 如( e ) + 2 n 。( c 4 ) + n 。( c 3 ) = 4 1 1 若d g ( e ) = 1 ，e ( c 4 ) = 1 ，e ( 岛) = 1 ，这种情况不成立 若d g ( e ) = 1 ，e ( c 4 ) = 0 ，e ( 岛) = 3 ，这种情况也不成立 若d ：g ( e ) = 2 ，e ( c 4 ) = 1 ，e ( 岛) = 0 ，这种情况也不成立 若d g ( e ) = 2 ，e ( c 4 ) = o ，e ( q ) = 2 ，故d g ( e ) 2 ，这种情况不成立 若d g ( e ) = 3 ，札( c 4 ) = 0 ，e ( 岛) = l ，故( g e ) e g 6 ，于是g g 1 4 若如( e ) = 4 ，c ( c 4 ) = e ( c 3 ) = 0 ，故( g e ) e g 2ug 3uc 4u 岛， 于是g g l lug x 2ug 1 6ug 1 7ug 1 9ug 2 0ug 2 2 情况3 若n ( c e ) = 一1 ，则 如( e ) + 2 e ( q ) + e ( 岛) 一e ( 仉) = 2 当e ( 瓯) = o ，则d g ( e ) + 2 e ( q ) + e ( c 3 ) = 2 若d g ( e ) = 1 ，e ( q ) = 0 ，e ( g ) = 1 ，这种情况不成立 若d g ( e ) = 2 ，e ( c 4 ) = e ( g ) = 0 ，故( g e ) e g 1 2 ，于是g g 1 4 通过递推关系计算可得1 1 ( g s ) = n ( c 9 ) = ( g 2 1 ) = 一1 当e ( 吼) = 1 ，则d g ( e ) + 2 e ( q ) + e ( 晚) = 3 若d g ( e ) = 3 ，e ( c 4 ) = e ( 岛) = 0 ，故( g e ) e g 9 ，于是g g 1 3 同理， 若( g e ) e g 1 3 ，则g g x 8 若( g e ) e g 1 8 ，贝g g 2 3 口 1 2 第四章含奇圈图的谱确定 在第三章给出了参数的定义和一些性质，接下来利用参数的性质证明主要的 引理和给出主要的结果及其证明 4 1 主要引理及证明 引理4 1 1 2 1 l 设g = t c t l ，z 2 ，1 3 ) 是一棵三叉树，则2 盯( g ) 当且仅当 ( 1 l ，1 2 ，1 3 ) = ( 2 ，2 ，2 ) ，( 1 ，2 ，5 ) 或( 1 ，3 ，3 ) ，口( g ) 是g 的邻接谱 引理4 1 2r ( 见图2 ) 的同谱图不包含圈分支 证明由的性质，可以从以下两方面寻找r 的同谱图 ( 1 ) 当r 的同谱图是连通图，我们只需要在= 一1 的图族中进行寻找，由引理 2 1 7 ，引理2 1 8 和系数6 4 ，只有种情况就是自身和自身可能同谱 ( 2 ) 当r 的同谱图是非连通图，我们需要在h = 一1 和= 0 的图族中进行寻 找由引理2 1 3 ，我们有 r ( r ) = p a ( c k ) 木p a ( r g ) 一心( p k 一1 ) 木p a ( r g 一口口。+ 1 ) 如( r 一瓯一v a 3 + 1 ) = p a ( 仇) r ( r 一瓯一。+ l 一仉) 一p a ( p k 一1 ) 木p a ( r 一瓯一 v a 3 + l 一瓯一u a l + 1 ) r ( r 一瓯一3 + 1 一仉一v a l + 1 ) = p a ( c k ) 木p a ( r q t ) 口3 + 1 一伉一l + l 一瓯) 一 r ( r 一1 ) 木p a ( r q v a 3 + l 一仇一l + l 一瓯一2 + 1 ) 可以看到，( r 一仉一v a 3 + 1 一瓯一v a l + 1 一q v a 2 + 1 ) 就是图死【见图2 1 【互z ! 毒； 2 ! 【互z o 上一。 a l + 2a l 1 1 1 g 2a 2 + 2 】 三毫 _ r 图2 ( 图f 和图t z ) 由引理4 1 1 ，当 a l ，a 2 ，a 3 ) 是 ( 2 ，2 ，2 ) ，( 1 ，2 ，5 ) ，( 1 ，3 ，3 ) ) 中之一，那么r 的同 谱图就含有圈分支 1 3 由引理2 2 7 ，引理2 2 8 和系数6 4 ，r 的同谱图可能是 g 5ug l s ) 或者是 g 5u g 1 5uq q ( z 5 ，q l ，z ，q z + ) ) 因为 i v ( r ( a l = 2 ，a 2 = 2 ，a 3 = 2 ) ) i ，l y ( r ( n l = 1 ，a 2 = 2 ，a 3 = 5 ) ) l ，l v ( r ( a l = 1 ，口2 = 3 ，a 3 = 3 ) ) i 这些图的点数都是固定的，经计算 和验证，不存在具有相同顶点数的图 g 5u g l 5t j o q ( f 5 ，a 1 ，f ，口z + ) ) 因 此，与r 可能同谱的图是 g sug 1 5 ) ( 日) 【见图3 】，故不含圈 口 1 b l 弋zk 鲁z ：盈 u lv lu 27 2 2 z 二纽k 鲁盈 u ：jr ：； ? 2 4y 4 h 图3 ( 图日) 引理4 1 3 令n = i y ( r ) l = f v ( r ，) i ，当r 和r 7 关于邻接矩阵同谱， 而且 口l + 口2 + n 3 + 3 后+ 4 = n l + 他+ r t 3 + 3 k + 4 = 凡， 则r 和r 7 同构，其中k 是最小奇圈的长度 证明因为a 2 和a 3 对称，n 2 和r t 3 对称，不妨假设a 2 a 3 和n 2 n 3 设 以( r ，入) 和e a ( r 7 ，入) 分别是图r 和r 7 的关于邻接矩阵的特征多项式依次删掉边 v a 3 , 1 , i r a 3 + 2 ，v a 2 + l v a 2 + 2 ，v a 3 1 1 u a 3 + 2 ，u u ，然后反复利用引理2 1 3 ，最后可得到 n ( r 一3 + 1 3 + 2 ，入) = 巳( 瓯) 幸【p a ( 只1 + 1 ) 幸p a ( r 2 + d 3 + 3 ) 一r ( r 1 ) 木p a ( p n 2 + 1 ) 宰 n ( r 。+ 1 ) 】_ p a ( p k 一1 ) 丰【- p a ( p 口。) 幸p a ( p 口：+ 口。+ 3 ) 一n ( r 。一1 ) 木心( p n 。+ 1 ) 木n ( 只。- i - 1 ) | c n ( 仇) 一 p a ( 仇) 木【n ( r 。+ 1 ) 木p a ( r ：+ 0 3 + 2 ) 一死( 只，) * p a ( 只。) 木r ( r 。十1 ) 卜r ( 兄一1 ) 木 f p a ( r 1 ) p a ( r 2 + 口。+ 2 ) 一r ( r 。一1 ) 半p a ( p d 2 ) 牛p a ( 只。+ 1 ) 】) 丰p a ( r 一1 ) 由引理2 1 6 ，把入= t l 2 + t 一1 2 代入上式，利用m a t h e m a t i c a 5 0 运算得到 加( r ，a l ，a 2 ，a 3 ) 同理，可得到( r 7 ，n l ，n 2 ，佗3 ) 假设 c a ( r ，a l ，a 2 ，a 3 ) = 妒a ( f ，佗l n 2 ，n 3 ) “( r ，a l ，a 2 ，a 3 ) 和( r 7 ，n l ，n 2 ，佗3 ) 的公因式和相同项对消后，可分别得到咖( r ) 和妒( r ，) 咖( r ) = 一t 4 + a 1 + 4 t 5 + 0 1 4 萨+ 0 1 一t 4 + d 2 + 4 t 5 + 口2 4 t 6 + n 2 一垆+ 8 l + 口2 + 2 t 7 + 口l + n 2 一 t 4 + a s + 4 t s + a s 一4 t 6 + a s t 6 + a x + a a + 2 t 7 + a 1 + a 3 一t 6 + a 2 + a 3 + 2 t 7 + a 2 + a s 一2 t 3 + a l + k 2 + 1 1 t 4 1 a l + k 2 1 6 t 5 + 口1 + 七2 + 4 t 6 + n l + 知2 2 t a + a 2 + k 2 + 1 i t 4 + a 2 + k 2 1 6 t 5 + n 2 + 2 + 4 垆+ n 2 + 七2 4 t s + a x + a 2 , 1 , k 2 + 1 1 t 6 + a l + a 2 + k 2 4 t 7 + a l + a 2 + k 2 2 t 3 + a s + k 2 + 1 i t 4 1 a 3 + k 2 1 6 t 5 + a 3 + k 2 + 4 t 6 + a 3 + k 2 4 亡5 + 口l + n 3 十七2 + 1 1 庐+ 口l + 口3 + 七2 4 t 7 + a 1 + a s + k 2 4 t 5 + d 2 + 口3 + 七2 + 1 1 芒6 + n 2 + 口3 + 七2 1 4 4 t 7 + a 2 + a a + k 2 + 4 t 3 + a 1 + k l l t 4 + a l + k + 4 t 5 + a 1 + k + 4 t 3 + a 2 + k 一1 1 t 4 + a 2 + k + 4 1 5 + a 2 + k 一 4 t 4 + 口1 + 口2 + + 1 6 t 5 + n 1 + 口2 + 七一1 l t 6 + 口l + n 2 + 七+ 2 t 7 + 口1 + n 2 + 七+ 4 亡3 + 口3 + 七一1 1 t 4 + 口3 + 南+ 4 炉+ 口3 + 七一 4 t 4 + a l + a a + k + 1 6 t 5 + a l + a a + k 一1 i t 6 + a l + a 3 + k + 2 t 7 + a l + a a + k 一4 t 4 + a 2 + a a + k + 1 6 t 5 + a 2 + a a + k 一 1 1 6 + 口2 + 口3 + 七+ 2 7 + 口2 + 口3 + 七一2 t 3 + 0 1 + 3 七2 + 芒4 + o l + 3 凫2 2 t 3 + a 2 + 3 七2 + 4 + 口2 + 3 七2 + 4 4 + 口1 + n 2 + 3 七2 4 f 5 + 口l + n 2 + 3 磨2 + t 6 + 口l + 0 2 + 3 靶2 2 t 3 + c 1 3 + 3 岛2 + p + 口3 + 3 七2 + 4 芒4 + 口1 + n 3 + 3 七2 4 t 5 + 口l + 口3 + 3 七2 十 t f + a t + a a + 3 k 2 + 4 t 4 + a 2 + a 3 + 3 k 2 4 5 5 + a 2 + a a + 3 k 2 + t 6 + a 2 + a a + 3 k 2 v ( r 7 ) = 一t 4 + n l + 4 t 5 + n 1 4 t 6 + n t t 4 + n 2 + 4 t 5 + n 2 4 t 6 + n 2 一t 6 + n 1 _ + n 2 + 2 t 7 + m + n 2 一t 4 + m + 4 t s + n a 一4 t 6 + n a t 6 + n x + n 3 + 2 t 7 + n l + n a t 6 + n 2 + n a + 2 t 7 + n 2 + n a 一2 t 3 + n l + k 2 + l l t 4 + m + k 2 1 6 t 5 + n 1 + k 2 + 4 t 6 + n 1 + 七2 2 亡3 + 7 1 2 + 南2 + 1 l t 4 + n 2 + 七2 1 6 t 5 + n 2 + 七2 + 4 芒6 + n 2 + ：2 4 t 5 + n 1 + n 2 + 七2 + l l t 6 + n t + n 2 + k 2 4 t t + m + n 2 + k 2 2 t 3 + n 3 + k 2 + l l t 4 + n 3 + k 2 1 6 t s + n a + k 2 + 4 t 6 + n 3 + k 2 4 f 5 + n 1 + n 3 + 七2 + 1 1 护+ n l + n 3 + 七2 4 t 7 + n l + n 3 + k 2 4 2 5 + n 2 + n 3 + 七2 + 1 1 t 6 + n 2 + n 3 + 七2 4 t 7 + t 1 2 + n 3 + 七2 + 4 t 3 + n * + k l l t 4 + n l + k + 4 t s + n l + k + 4 t 3 + n 2 + k 一1 1 t 4 + n 2 + k + 4 t 5 + n 2 + k 一4 t 4 + n l + n 2 + k + 1 6 t s + m + n 2 + k 一1 l t 6 + n 1 + t 1 2 十七十2 t 7 + n l 十n 2 + 七+ 4 矿+ n 3 + 七一1 1 亡4 + ，1 3 十七+ 4 t 5 + n 3 + 一4 t 4 + n l + n a + k + 1 6 t s + n i + n 3 + k 一1 1 t 6 + n l - t - h a q - k + 2 t 7 + n l + n s - l - k 一4 t 4 + n 2 + h a + k + 1 6 t s + n 2 + n a + k l l t 6 + n 2 + n 3 + k + 2 t 7 + n 2 + n 3 + k 一2 t 3 + n 1 + 3 k 2 + t 4 + m + 3 k 2 2 t 3 + n 2 + 3 k 2 + t 4 + n 2 + 3 k 2 + 4 t 4 + m + n 2 + 3 k 2 4 t 5 + n 1 + ，1 2 + 3 七2 + 护+ ，1 1 + n 2 + 3 七2 2 t 3 + n 3 + 3 k 2 + t 4 + n a + 3 k 2 + 4 t 4 + n l + h a + 3 k 2 4 t 5 十n 1 + n 3 + 3 k 2 + t 6 + n l + n a + 3 k 2 + 4 t 4 + n z + n z + 3 k 2 4 t s + n 2 + n a + 3 k 2 + t 6 + n 2 - l - n 3 + 3 k 2 我们利用a l 和a 2 ，a 3 的关系找出咖( r ) 的最小指数项和利用r t l 和r t 2 ，r t 3 的关 系找出妒( r 7 ) 的最小指数项 对于( r ) ，我们考虑以下情况： 情况p 1 如果a l = a 2 a 3 ，则r l = 一2 t 4 + a 1 情况局如果a 2 = a 3 a 1 ，则7 1 = 一2 t 4 + a 2 情况b 如果a 1 d 2 a 3 ，则7 1 = 一t 4 札1 情况只如果a l a 2 = 6 3 则r 1 = 一t 4 + 们 情况p 5 如果a 2 a 3 a l ，则r l = 一t 4 + a 2 情况r 如果a 2 a l a 3 ，则r l = 一矿却2 情况尸7 如果a 2 a 3 = a l ，则r l = 一t 4 + ” 情况恳如果a l = a 2 = a 3 ，则r l = 一3 t 4 怕1 对于妒( r ，) ，我们考虑以下情况： 情况9 1 如果几l = n 2 几3 ，则r 1 = 一2 t 4 + n 1 1 5 情况q 2 如果n 2 = n 3 n l ，则r 1 = 一2 t 4 栅2 情况驰如果礼1 仃2 n 3 ，则r x = 一t 4 + n 1 情况口4 如果佗1 n 2 = n 3 ，则r x = 一t 4 + n 1 情况q 5 如果1 7 , 2 n 3 n 1 ，则r i = 一t 4 + n 2 情况9 6 如果礼2 n l 竹3 ，则r 1 = 一t 4 + 忭2 情况们如果几2 n 3 = 佗1 ，则r i = _ t 4 + m 情况口8 如果n l = n 2 = n 3 ，则r i = - 3 t 4 + n 1 因为( r ) = 妒( r ，) ，所以r 1 = r 1 于是，我们有以下情形讨论 情形1 如果情况p 1 和情况 9 1 ，q 2 ) 之一成立， 则a l = t 1 , 1 或铆= n 2 情形2 如果情况恳和情况 9 1 ，9 2 之一成立， 则a 2 = n 2 情形3 如果情况b 和情况 q 3 ，口4 ，q 5 ，