（运筹学与控制论专业论文）有关树的能量的探究.pdf

硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 公蝴￥四 日期：6 孑年 ：hi 这一概念由g u t m a n 引进，由于它具有可以用来粗略估计一个分子的7 r 一电子能 虽的性质而在化学中被广泛研究对于更多的有关e ( g ) 的详细研究可参阅【3 ， 4 ，5 ，6 对图g ，令m ( g ，尼) 为图g 中肛匹配的数目，这里尼1 定义 m ( g ，0 ) = 1 ，而且，当后 m ( g 2 ，j ) ，那么我们把它记为 g 1 - g 2 因此， g 1 g 2 号e ( g 1 ) e ( g 2 ) 若既没有g 15g 2 ，又没有g 25g l 成立，那么g 1 和g 2 被称为不可比的这 一有趣性质被用来对很多某一类图的极值能量进行研究例如，g u t m a i l 6 对 能量最小，第二小，第三小，第四小的树进行了刻画；文献 3 3 】分别对具有完美 匹配的极小能量树和极大能量树进行了研究；文献【1 6 】和文献【1 5 】分别确定了具 8 巧譬、 硕士学位论文 m a s t e r st h e s i s 有给定数目的完美匹配的极小能量和所有反圈图的极小能量；文献 3 5 和【3 6 】确 定了所有六角形的链中的极大能量和极小能量；文献f 2 9 刻画了所有几个顶点， 至少有l 旦菩1 个悬挂点的树中的极大能量；文献【2 4 】确定了所有阶为n ，最大度 为( 3 礼一2 ) 的极大能量和所有阶为n ，最大度为( i 孚l n 一2 ) 的树的极小能量；文献【3 1 】刻画了具有角个叶子的树的极小能量在这方面比较 前沿的结论可参阅文献【4 0 一4 3 】 米并壮 z 9 图1 弱，碥，磊，和 令r 代表阶为佗的路，在这里顶点1 ，2 ，凡被标号，使得顶点1 和仃为 终点，而且顶点j 和j + 1 相邻( 歹= 1 ，2 ，n 一1 ) 令r ( i ) m 代表由连接p m 的终点和r 的第i 个顶点所得到的图，在这里1 i 方便起见，我们把 r ( i ) m 简记为凡( i ) m 令磊为所有n 个顶点的树构成的集合g u t m a n 【6 】证 明了 e ( ) e ( k ) e ( 磊) e ( w 么) e ( t ) e ( r ) ( 见图2 ) 同时，他们也证明了中的 图2 图风，r ，k 和螈 第三小能量树要么是k 要么是 死( 见图2 ) 而且，厶和 厶是不可比较的 在这篇文章中，作为【3 3 】的继续，利用拟序一 - _ p 2 ku 最一2 k - p 2 + lub 一2 七一1 - p 2 一1u b 一2 七+ l - - rur 一1 ，在这里f = 4 七+ r ，0 r 3 引理5 ( 【6 ) 若r 是具有n 个而j 占、的树，且丁k ，k ，磊，眠，r 一2 ( 3 ) 2 ，r ， 则e ( ) e ( k ) e ( 互乙) e ( 1 ) e ( 丁) e ( r 一2 ( 3 ) 2 ) e ( r ) 而且， _ k _ 磊 巩 z - g 7 j 第三章顶点数目扎充分大时的第五小，第六小，第七小，第三大能量树，以及 h o s o y a 拓扑指标不等式 3 5 n 个顶点的极小能量树 在这一部分，我们确定了玩中的第五小，第六小，以及第七小能量树 令g 1 = ( ，局) 和g 2 = ( k ，e 2 ) 为两个图，且n = 0 若g 由在g 1 的顶点u 和g 。的顶点u 之问连一条边而成，我们把所得图记为g = g 1 仳：u g 2 ， 即：g = ( ve ) ，其中y = kuk 且e = j e 7 1u 易u 札u ) 我们把n 个顶点的 星图记为甄。一l ，把图g 中顶点u 的度记为如( 钞) 若e 是图g 中的一条边，我 们记之为e g 令丁是一颗树，e t ，则，t e = zu 碍，这里z 和譬 是t e 的两个分支令i i z i l = 口。而且l l 贮= 6 。不失一般性，我们不妨假设 o e 6 e ，e = t 正u ，让而且 掣。 定理7 在所有具有n ( 礼6 ) 个顶点的树中，第五小能量的树为以，在这里 d n = 甄n 一5 u ：口硒3 ；见图3 1 1 硕士学位论丈 m a s t e r st h e s i s 证明由引理2 ，可知 m ( d 。，忌) = m ( d 。一札 ，尼) + 仇( d 。一u 一 ，七一1 ) = m ( 髓，。一5uk 1 ，3 ，后) + m ( ( n 一2 ) 只，毙一1 ) = m ( k 1 ，醇5u 量，1 3 ，是) 。 所以，m ( d 。，1 ) = n 一1 ，m ( d 。，2 ) = 3 n 一1 5 ，而且，当尼3 时，m ( d 。，七) = o 类似地，我们有 m ( ，1 ) = 几一1 ，m ( 巩，2 ) = 2 n 一7 ，m ( ，3 ) = 仃一5 ，若尼4 ，则m ( 既，七) = 0 ， ( 3 3 ) 在这里风= 五；一2 u ：秒尸2 ( 见图3 ) 首先我们证明如果丁，k ，磊，d 风， 那么要么e ( t ) e ( d 。) ，要么e ( 丁) e ( 月1 ) 接着，我们将比较d 。和风的 能量现在我们将分下面三种情况来证明本定理 3 图3d 。和巩 3i 一i j 情形i 存在一条边e 丁使得6 e 3 注意到n 。+ 6 e = n 一2 对于所有的 e r 都成立，而且中的每一条边和跫中的每一条边构成了t 的一个2 匹 配则， m ( 丁，2 ) 3 ( n 一5 ) = 3 n 一1 5 = m ( d n ，2 ) 因为丁d 。，若m ( 丁，2 ) = m ( d ，2 ) ，则要么z k 1 p 5 ，要么掣k 1 ，3 所 以，我们有m ( z3 ) m ( 上k ，3 ) 因此，显然有丁 三k ，所以e ( 丁) e ( 口；) ，且 e ( t ) = e ( d n ) 当且仅当t = d 竹 情形2 存在一条边e = u u t 使得6 c = 2 ，即，掣= b 我们可以通过证 明下面这两种子情况来证明定理在这一情况下成立。 1 2 硕士学位论文 m a s t e r st h e s i s 定理1 1 在所有具有n ( n 1 4 ) 个顶点的树中，具有第七小能量的树要么是q n 要么是q ：，这里q 。= k 1 川o 札：口k l ，4 ，q ：= k l ，5 “：t j 只；见图4 而且，q 。 和q ：是不可比较的 证明：很容易可看到m ( q 。，1 ) = 礼一1 ，仇( q 。，2 ) = 乱一2 4 而且如果七3 ， 则m ( q 。，七) = 0 由( 3 4 ) ，我们有q 。和q 幺是不可比较的对任意的t 矗而且 t ，磊，眠，d 。，巩，“，我们分下面三种情况来证明此结论成立 情形j 存在一条边e t 使得6 e 4 类似于定理7 中的情形1 ，我们有e ( t ) e ( q 。) ， 而且 e ( 丁) = e ( q 。) t = q 。 情形2 存在一条边e t 使得6 。= 3 由定理8 中的情形3 可知，e ( t ) e ( q 。) ， e ( r ) = e ( q 。) 亭t = q 。， 或者e ( r ) e ( q 乞) ，而且 e ( t ) = e ( q ：) 兮t = q 二 t ? _ 一 图5q 。和q ：i 情形只存在一条边e t 使得b 。2 由定理8 中的情形1 和情形2 ，我们有 e ( t ) e ( q ：i ) 最后我们必须证明，e ( q 。) e ( 风) 而且e ( q 0 ) e ( 上k ) 事实上，q 。的谱通过计算 可得，因此，e ( q 。) = 2 0 i j 葺i 丽注意到这一点，立即可推出e ( q 。) e ( 凰) 另 一方面，由等式3 3 和3 4 ，我们有e ( q 幺) e ( 皿。) 因此，定理最终成立 3 6 n 个顶点的树中的第三大能量 在这一部分，我们确定了磊中的第三大能量的树 1 9 硕士学位论文 m a s t e r st h e s i s 然而， m ( 死，七) = m ( 死一一5 口，七) + m ( 死一一5 一 ，七一1 ) = m ( n 一3 ( 3 ) 2 ，忌) + m ，( p 2u ( n 一6 ( 3 ) 2 ) ，七一1 ) = m ( n 一3 ( 3 ) 2 ，七) + m ( n 一6 ( 3 ) 2 ，后一1 ) + m ( n 一6 ( 3 ) 2 ，七一2 ) ( 3 7 ) 注意到几一7 ( 5 ) 2 是n 一6 ( 3 ) 2 的真子图由引理6 ，n 一7 ( 3 ) 2 几一6 ( 3 ) 2 ，因此我们有， m ( 孔，忌) 仇( 乃，七) 故，乃 死另一方面， m ( 死，七) = 仇( 乃一 2 3 ，七) + m ( 忍一 2 一t 1 3 ，后一1 ) = 仇( p 2 u ( n 一4 ( 3 ) 2 ) ，七) + m ( n 一5 ( 2 ) 2 ，七) = 仇( 几一4 ( 3 ) 2 ，忌) + m ( n 一4 ( 3 ) 2 ，七一1 ) + m ( n 一5 ( 2 ) 2 ，七一1 ) = m ( 礼一4 ( 3 ) 2 ，后) + 仇( n 一4 ( 3 ) 2 ，墨一1 0 + 7 n ( 7 。一6 ( 2 ) 2 ，七一1 ) + 仇( 凡一7 ( 2 ) 2 ，克一2 ) 由等式3 7 ，我们有 m ( 死，后) = 仇( n 一4 ( 3 ) 2 ，七) + 仇( n 一5 ( 3 ) 2 ，七一1 ) + m 一6 ( 3 ) 2 ，七一1 ) + 仇( n 一6 ( 3 ) 2 ，七一2 ) = 仇( 凡一4 ( 3 ) 2 ，j c ) + m ( n 一4 ( 3 ) 2 ，知一1 ) + m ( n 一6 ( 3 ) 2 ，七一1 ) = 仇( n 一4 ( 3 ) 2 ，后) + m ( 竹一4 ( 3 ) 2 ，七一1 ) + m ( 几一7 ( 2 ) 2 ，七一1 ) + 仇( r 一8 ，奄一2 ) 由引理6 ，我们有礼一7 ( 2 ) 2 n 一6 ( 2 ) 2 而且r 一8 一 n 一7 ( 2 ) 2 因此死 8 且t ，是t 的叶子，这里r r ，死一2 ( 3 ) 2 ，n 一2 ( 5 ) 2 ，而且t v = 凡一3 ( 3 ) 2 则t5 佗一2 ( 5 ) 2 ，同时有e ( t ) = e ( 几一2 ( 5 ) 2 ) 争丁= 几一2 ( 5 ) 2 证明：我们通过对f r i 进行归纳来证明令t u ：= 五一口若礼= 8 ，9 ，可通过对t 和 礼一2 ( 5 ) 2 的特征多项式进行比较来检验该结论假设结论对9 例 n 的情况成立，我们 下面考虑情形l t l = n 注意到r 亿一2 ( 3 ) 2 则u 和顶点一3 不相邻接，因此一3 是t 的一度顶点由引理2 ，我们有 m ( 瓦七) = m ( t 一 。一3 ，南) + m ( t 一 。一3 一 。一4 ，七一1 ) ， m ( n 一2 ( 5 ) 2 ，) = m ( n 一3 ( 5 ) 2 ，忌) + m ( 扎一4 ( 5 ) 2 ，七一1 ) 情形j t 一 。一3 = n 一3 ( 3 ) 2 在这一情形下，t = 乃；见图6 则有引理1 3 ，我们有 t n 一2 ( 5 ) 2 2 1 硕士学位论文 m a s t e r ：st h e s i s 乃 口1吨珊瑚坞啦 图7 乃，死和死 ( i ) t 一口。一4 = n 一3 ( 3 ) 2 在这一情形下， n = 1 0 而且t = 乃；见图7 由引理1 5 ， t n 一2 ( 5 ) 2 ( i i ) t 一 。一4 一u 。一5 = n 一4 ( 3 ) 2 在这一情形下，n = 1 1 而且t = 死；见图7 由引理 1 5 ，t _ t 令u 是丁的一 个与叫相邻接的一度顶点由引理2 ，我们有 m ( 正南) = m ( t 一 ，七) + m ( t 一 一伽，岛一1 ) ， 7 n ( n 一2 ( 5 ) 2 ，七) = m ( n 一3 ( 5 ) 2 ，七) + l ( n 一4 ( 5 ) 2 ，后一1 ) 1 若t t ，= r 一1 ，即，t = n 一1 ( i ) 1 ，这里t 1 ，n 一1 ，则有引理1 2 可知，t - t 若t 一口一伽= n 一4 ( 5 ) 2 ，由引理1 6 ，我们有t 仃一2 ( 5 ) 2 因此我们假 设t t ，一锄r 一2 ，n 一4 ( 5 ) 2 注意到丁一 一叫的阶是n 一2 ，则由数学归纳法可知， 麓 、 硕士学位论文 m a s t e r s1 h e s i s t it 2t 3t 4 十啤手比j 卜 卜卜+料 + t 1 4t 1 5 图8z 7 ，z ，瑙 t 2 0 定理2 2 当n 5 时，没有第六，j 、的能量树当n = 6 ，n = 7 ，n = 1 0 时，第六小的能量树分 别是巧7 ，砖7 ，和露p 图占所示，j 当n = 1 l 时，“和q 。是同谱的，因此，巩1 和q 1 1 占据了第六小和第七小的位置当n = 8 ，n = 9 ，和n 1 2 时，第六小的能量树是以， 定理2 3 当几6 时，没有第七小的能量树当n = 7 ，n = 8 ，n = 9 ，和n = 1 0 时，第七小的 能量树分别是掣，媸，死7 和2 似a 图8 所示，像在定理2 2 中提到的那样，当n = 1 l 时， m 1 和q 1 1 占据了第六小和第七小的位置当n21 2 时，第七小的能量树是q 。 上 矗 硕士学位论文 m a s t e r st h e s i s 定理2 4 当礼3 时，没有第二大的能量树当礼= 4 ，仃= 5 时， 和墨! 似。图8 所示夕当7 2 之6 时，第二大能量树是r 一2 ( 3 ) 2 ， 定理2 5 当靠s4 时，没有第三大的能量树当n = 5 ，佗= 6 时， 和z 洳图8 所示j 当礼27 时，第三大能量树是p n 一2 ( 5 ) 2 第二大能量树分别是q i 第三大能量树分别是足 猜想2 6 当凡5 时，没有第四大能量树当n = 6 ，几= 7 ，7 l = 8 ，和几= l l 时，第四大能 量树分别是足：，q ：，t f ；和巧：当礼= 9 时，两个同谱的图，q 和写6 占据了第四大和 第五大的位置当n = 1 0 和n 1 2 时，第四大能量树是r 一2 ( 7 ) 2 注该猜想已被解决，见【s l i ，x “，o nt h ef o r t hm a x i m a le n e r g yo fa c y c l i cg r a p h i e s ，a c o 印t e d b ym a t ch 】 2 6 硕士学位论丈 m a s t e r st h e s i s 第四章对给定直径的n 个顶点及小能量树的再次阐释 4 9 磊d 中的极小能量树 首先回忆一下本节中要用到的一些主要结论 引理2 7 ( 【6 】) 令伽是图g 中的一条边，则m ( g ，j | c ) = m ( g u u ，尼) + m ( g u 一口，忌一1 ) 对所有的角均成立 引理2 8 ( 【6 】) 对任意的n 个顶点的树丁k l ，。一1 ，t ( n ，3 ；o ，n 4 ) ，我们有e ( k 1 ，。一1 ) - g 7 j 为了确定，d 中的最小能量树，我们需要一些基本结论下面这一运算由文献【3 1 】引进 令p = u o ，( 角1 ) 是树t 中的一条路若曲) 3 ，西( ) 之3 而且d t ( 仇) = 2 ( 0 i 南) ，我们称路p 为树丁的内部路若d r ( t ，o ) 23 ，曲( ) = 1 而且如( 优) = 2 ( 0 i e ( ? ，) 若i = d 一1 ，则运算是运算i 的特殊情形，因此由引理3 0 ，有e ( 丁7 ) - ；而且e ( b 。) e ( 雌) 结合等式( 4 3 ) ，我们有e 口) e ( b 。) e ( w 喜) 故，最终 结论成立 注意到m ( ，七) = ( 嚣) + ( 詈一1 ) ( m 二；) + ( 詈一3 ) ( z j ) + ( ：j ) 结合等式( 4 1 ) ，我们有 靠 厶，故，e ( 磊) e ( 厶) 很容易即可看到e ( 三。) e ( 睢) 因此，总结引理4 2 和4 3 ， 有下述结论成立： 定理4 4 令空。代表几个顶点的具有完美匹配的树的集合 ( i ) 若k 是峻中的第三小能量树，则九中的第四小能量树要么是地要么是吩 ( i i ) 若地是磊中的第三小能量树，则靠中的第四小能量树要么是乞。要么是厶 讨论事实上，引理4 2 和4 3 ，我们能够推出吼中的第三小，第四小能量树分别是 l n ， 厶：厶，；) ， 但不幸的是，我们不能具体确定 厶， 靠，厶? ；) 中的哪一个是第三小，哪个是第四小所 以这仍然是一个开放性的问题，等待着一个满意的答案 硕士学位论文 m a s t e r st h e s i s 参考文献 1 】 d b a b i i g u t m a n ， i o r el o w e r b o u n d sf o rt h et o t a l7 r e l e c t r o ne 1 1 e r g ) ro fa i t e r n a n th y d r o c a l b o n s ： m 气t c hc o m m u n ，m a t h ，c o m p u t c h e m 3 2 ( 1 9 9 5 ) 7 - 1 7 【2 1j a b o n d y ，u s r m u 哪，g r a p ht h e o r y 诵t ha p p l i c a t i o n s ，m a c m i l l a n ，n e wy o r k ，1 9 7 6 【3 】a c h e n ，a c h a n g ，w c s h i u ，e n e r 鲥o r d e r i i l go fu n i c y c l i cg r 印l l s ，m a t c hc o m m u n m a t h c o m p u t c h e m 5 5 ( 2 0 0 6 ) 9 5 1 0 2 【4 】d c v e t k o v i ，m d o o b ，h s a c h s ，s p e c t r ao fg r a p l l s t h e o r ya i l da p p l i c a t i o i l s ，a c a u d e m i cp r e s s ， n e w1 y b r k 1 9 8 0 【5 】i g u t m a n ，b o u n d sf o rt o t a l 丌- e l e c t r o ne n e r 甄c h e m p h y 8 l e t t 2 4 ( 1 9 7 4 ) 2 8 3 - 2 8 5 【6 】i g u t m a n ：a c y c l i cs y s t e m sw i t he x t r e m a l h 证c k e l1 r - e 1 e c t r o ne 耻e r g mt h e o r e t c h j m a c t a 1 4 5 ( 1 9 7 7 ) 7 9 8 7 【7 】i g u t m a n ，b o i l n d sf o rt o t a l7 r - e l e c t m ne n e r g yo fp o l y m e t h i n e 8 ，c h e m p h y s l e t t 5 0 ( 1 9 7 7 ) 4 8 8 4 9 0 【8 li g u t m a n ，m c c l e l l a n d - t y p el o w e r b o u n df o rt o t a l 丌一e l t r o ne n e r 斟，j c h e m s o c f k a d a yt r a n s 8 6 ( 1 9 9 0 ) 3 3 7 孓3 3 7 5 【9 】i g u t m a j l ，t o t a l ，r e l e c t r o ne n e r 斟0 fb e n 2 e n o i dh y d r o h a b o n s ，t o p i c sc hr r c h e m 1 6 2 ( 1 9 9 2 ) 2 乳6 3 1 0 】i g u t m a n ，t h ee n e r g yo fag r a p h ：o l da n dn e wr e s u l t s ，i n ：a b e t t e n ，a k o h n e r t ，r l a u e ：a 、缸s e r m a n n ( e d s ) ，a l g e b r a i cc o m b i n a t o r 妇a n da p p l i 僦i o i l s ，s p r i n g e r - v e r l a g ，b e r l i n ，2 0 0 1 ，p p 1 9 6 _ 2 1 1 【1 l 】i g u t m a n ，o e p o l a l l s k y ，m a t h a t i c a ic o n c e p t sj no r g a n i cc h e m i 8 t ms p r i n g e r ，b e r l i n ，1 9 8 6 i g u t m a n ，a v d o r o v i 6 ，l n e d e l j k o v i ，t o p l o g i c a lp r o p e r t i 鹊o f b z e n o i ds y s t 锄s b o u n d 8 a n da p p 咖劬a t ef o 咖u i af o rt o t a i7 r e l e c t r o ne n e r 既t h e o r c h i m a c t a6 5 ( 1 9 8 4 ) 2 孓3 1 i g u t m a n ，l t 证r k e r ，j r d i 鹄，a n o t h e ru p p e rb o u n d 矗盯t o t a i 开e l e c t 潮e n 媚7o fa 】t e r n a n t h y d r o c a r b o n s ，m a t c hc o m 咖n m a t h c 0 m p u t c h e m 1 9 ( 1 9 8 6 ) 1 4 7 - 1 6 1 i g u t m a i l ，b z h o u ，l a p l a c i a ne n e r 鲥o fag r 印h ，l i n e 盯a l g e b r aa p p l 4 1 4 ( 2 0 0 6 ) 2 9 3 7 y h o u ，u i c y c l i cg r 印h sw i t hm i n i m a le n e r g y ，j m a t h c h 锄。2 9 ( 2 0 0 1 ) 1 6 3 1 6 8 。 【1 6 】y h o u ，0 nt r e 鹤w i t ht h el e te n e r 酣a n dag i v e ns i z eo fm a t c l l i n g ，j s y s t s c i m a t h s c i 2 3 ( 2 0 0 3 ) 4 9 1 4 9 4 ，( i nc h i n e ) 【1 刀h h 0 8 0 y a ，r o p o l o g i c a l i n d e x ap r o p o s e dq u a n t i t yc h a r a c t e r i z m gt h et o p o l g i c a ln a t u r eo fs t r u c 168。【16】yhou，0ntre鹤withtheletener酣andagivensizeofmatclling，jsystscimathsci23 硕士学位论文 m a s t e r st h e s i s 【1 8 】g i n d u l a l ，a v 幻a y a k u m a r ，o nap a i ro fe q u i e n e r g e t i cg r a p l l 8 ，m a t c hc o i 砌u n m a t h c o m p u t c h e m 5 5 ( 2 0 0 6 ) 8 3 - 9 0 ( 1 9 】j h k o o l e n ，v m o u l t o n ，m “i m a le n e r g yg r a p h s ，a d v a p p i m a t h ，2 6 ( 2 0 0 1 ) 4 7 5 2 【测j h k 0 0 1 e n ，v m o u l t o n ，m “蛳a le n e r 斟b i p a r t i t e 口a p l l s ，g r 印1 1 sc 砌b h l 1 9 ( 2 0 0 3 ) 1 3 1 1 3 5 f 2 l jj h k o o k n ，v m o u l t o n ，i ，g u t m a n ，i m p r o v i n gt h em c c e l l 明di n e q u a l i t yf o rt o t a l7 r e l e c t r o n e n e r 斟，c h e m p h y s ，l e t t 3 2 0 ( 2 0 0 0 ) 2 1 3 _ 2 1 6 2 2 1f l i ，b z h o u ，m i n j m a le n e r 留o fb i p a r t i t eu n i c y c l i cg r a p h so fa 西v e nb i p a r t i t i o n ，m a t c h c o m m u n m a t h ，c o m p u t c h 咖5 4 ( 2 0 0 5 ) 3 7 9 3 8 8 【2 3 】n “，s l i ，m i n i m a le n e r g i e so nt w o c l a l s s e so ft r e 鸥，p r e p r i n t 【2 4 1w l i n ，x g u o ，h l i ，o nt h ee x t r e m a le n e r 西e so ft r e e sw i t hag i v e nm “j m u 脚d e g r e e ，m a t c h c o m m u n m a t h c o m p u t c h e m 5 4 ( 2 0 0 5 ) 3 6 3 3 7 8 【2 5 】h q l i u ，m l u ，f t i a n ，s o m eu p p e r b o u n d sf o rt h e 印e r g ) ，o f 舒印h s ，j m a t h c h e m ，t o a p p e a r 【2 6 】a j s c l l w e n k ，c o m p u t i n gt h ec h a r a c t e r 瓯i cp 0 1 y n o m i a lo fag r a p h ，g r a p l l s 卸dc ( 胁b i l l a t o r i c s ， i n ：r a b a r i ，f h a r a 呵( e d s ) ，l e c t l l r en o t 够i 1 1m a t h e m a t i ，v 0 1 4 0 6 ，s p r i n g e r v b r l a g ，n e w y o r k ，1 9 7 4 ，p p 1 5 3 _ 1 7 3 【2 7 】i s h p 缸l i n 8 k i ，o nt h ee n e r 鲥o fs o m ec i r c u l a n tg r a p h 8 ，l i n e a ra l g e b r aa p p l 4 1 4 ( 2 0 0 6 ) 3 7 3 8 2 f 2 8 】w g y 彻，l z y e ，o nt h em i n i m a je n e r 斟o ft r e 鼯w i t hag i v e nd i 啪e t e r ，a pp 1 m a t h l e t t 1 8 ( 2 0 0 5 ) 1 0 4 6 - 1 0 5 2 【2 9 1w g 1 ，a n ，l z y e ，o nt h em a x i m a le n e r 盱a i l dt h eh o s o y ai i l d e xo fa t y p eo ft r e e sw i t hm a n y p e n d a n tv e r t i c 髑，m a - t c hc o m m u n m a t h c o m p u t c h e m 5 3 ( 2 0 0 5 ) 4 4 9 - 4 5 9 【3 0 1a m y u ，m l u ，f t i a n ，n e wu p p e rb o u n 出f o rt h ee n e r 时o fg r 印l l s ，m a t c hc o m m u n m a t h c o m p u t c h e m 5 3 ( 2 0 0 5 ) 4 4 1 - 4 4 8 f 3 l 】a 。m y u ，x z l v ，m i l l 沥u me n e r 斟o nt r e 鹤w i t h 船p e n d a l l tv e r t i c e s ，l i i l e a ra l g e b r aa p p l4 1 4 ( 2 0 0 6 ) 6 2 5 - 6 3 3 1 3 2 】a m y u ，x z l v ，t h em e r r i f j e i d s i m m o n 8i n d i c 瞄明dh 0 s o y ai 1 1 d i c 髓o ft r 啷w i t h 七p e n d 觚t v e r t i c ，j 。m 8 t h c h e m 。，i np r e 蹈。 【3 3 】f j z h