（应用数学专业论文）图的多项式唯一性.pdf

摘要 摘要 多年来，图多项式一直是一个活跃的研究课题，它在图论与传统代数之间 架起了桥梁。因为图多项式的系数包含了丰富的组合信息，所以图多项式的研 究为我们了解图的复杂结构与参数提供了新的途径。一个很自然的问题就是什 么类型的图能被它们的多项式唯一确定? 特别地，什么类型的图，它的结构可 以被一个图多项式完全刻画? 换句话来说，我们是否可以找到一类图使得他们 可以被一个给定的多项式所确定? 本文主要研究这些问题。 图论中有三个重要的多项式：色多项式、t u t t e 多项式以及流多项式。这三 个多项式有很密切的关系，其中色多项式与流多项式在某种意义上具有“对偶 性 ，并且它们都是t u t t e 多项式的特殊形式。色多项式以及能够由色多项式唯 一确定的图等问题已得到深入研究，近些年，更多研究关注于t u t t e 多项式以及 能够由t u t t e 多项式唯一决定的图。然而，关于流多项式，这方面的成果还屈指 可数。另外，关于能被色多项式与流多项式所共同确定的图方面的研究还是空 白。本论文首次对这些问题进行了研究。 论文结果包括两个方面的内容。第一部分主要是对流多项式的研究以及能 被色多项式与流多项式共同确定的图的研究；第二部分主要涉及能被t u t t e 多项 式所唯一确定的图的研究。 论文的第一部分包括第二章和第三章。在第二章中，我们主要关注图的流 多项式。我们研究了流多项式的系数，并且证明：若两个连通的对偶简单图 有相同的流多项式，那么他们有相同的点数、边数、边连通度以及相同数目 的最小边割。利用这些信息，我们得出了广义曰一图的对偶图、5 个顶点的完全 图蚝以及六个顶点的完全二部图k 8 是可以被它们的流多项式所唯一确定的。 在第三章中，我们综合运用包含, 3 在色多项式与流多项式中的信息，证明了 梯子、m s b i u s 梯子以及圈平方图可以被它的色多项式和流多项式所共同决定。 而这几类图，d em i e r 和n o y 曾证明它们是能被t u t t e 多项式所唯一确定的，这个 结果可以看作是我们结论的推论。 第二部分即第四章。在这一章中，我们研究了两类图：第一类图我们称作 是“曲轮 ，记作w k ，膏2 ( 见图4 2 ) ，第二类图与曲轮有着相似的结构，我们 称之为“双半轮”w h ( k l ，k 2 ) ( 见图4 3 ( b ) ) 。为简化这两类图的结构，我们 摘要 首次引入了“三角一图 的概念，这个概念的思想与线图有一定的相似之处。我 们通过综合运用包含在t u t t e 多项式中的信息证明了这两类图是可以被t u t t e 多 项式所唯一确定的。 关键字：t u t t e 多：项式，流多项式，p 唯一，流一唯一，( p ，q ) 一唯一。 l l a b s t r a c t a b s t r a c t t h es t u d yo fg r a p hp o l y n o m i a l sh a sb e e na na c t i v er e s e a r c ht o p i cf o rm a n y y e a r s i ts e r v e sa sab r i d g eb e t w e e ng r a p ht h e o r ya n dt r a d i t i o n a la l g e b r a s i n c e t h ec o e 伍c i e n t so fp o l y n o m i a l so f t e nc o n t a i nr i c hc o m b i n a t o r i a li n f o r m a t i o n t h e s t u d yo fg r a p hp o l y n o m i a l sp r o v i d e sn e wa v e n u e st ou n d e r s t a n dt h ec o m p l i c a t e d s t r u c t u r e so fg r a p h sa n dg r a p h i cp a r a m e t e r s i ti sn a t u r a lt oa s kw h a tk i n do f g r a p h sa r ed e t e r m i n e db yt h e i rp o l y n o m i a l s i np a r t i c u l a r ，w h a tk i n do fg r a p h s h a v et h e i rs t r u c t u r e se n t i r e l ye n c o d e di na g r a p hp o l y n o m i a l ? i no t h e rw o r d s ，c a n w ef i n df a m i l i e so fg r a p h st h a ta r eu n i q u e l yd e t e r m i n e db ya g i v e np o l y n o m i a l ? i nt h i st h e s i s ，w em a i n l yc o n s i d e rt h e s ep r o b l e m s t h e r ea x et h r e ei m p o r t a n tg r a p hp o l y n o m i a l si ng r a p ht h e o r y , t h e yh a v ea c l o s er e l a t i o n s h i pw i t he a c ho t h e r ：c h r o m a t i cp o l y n o m i a l ，t u t t ep o l y n o m i a la n d f l o wp o l y n o m i a l t h ef l o wp o l y n o m i a lc a nb ec o n s i d e r e da st h ed u a lo ft h e6 h r 争 m a t i cp o l y n o m i a l ，a n db o t ho ft h e ma r ee v a l u a t i o n so ft h et u t t ep o l y n o m i a l t h e r ei se x t e n s i v er e s e a r c ho ng r a p h su n i q u e l yd e t e r m i n e db yt h e i rc h r o m a t i c p o l y n o m i a l sa n dm o r er e c e n t l yo nt h e kt u t t ep o l y n o m i a l s ，b u tr a t h e rs p o t t y r e s e a r c ho ng r a p h su n i q u e l yd e t e r m i n e db yt h e i rf l o wp o l y n o m i a l so rt h ec o i l ：l - b i n a t i o no fb o t h 出r o m a t i ca n df l o wp o l y n o m i a l s t h i st h e s i si sa ni n i t i a t i o no f i n v e s t i g a t i o ni nt h i sa r e a t h et h e s i sc o n s i s t so ft w op a r t s t h ef i r s tp a r tc o n t r i b u t e st of l o wp o l y n o m i - a l so fg r a p h sa n dg r a p h su n i q u e l yd e t e r m i n e db yc h r o m a t i ca n df l o wp o l y n o m i a l s t o g e t h e r ，w h i c hi sa ni n i t i a t i o no fi n v e s t i g a t i o ni nt h i sd i r e c t i o n ；t h es e c o n dp a r t i sd e v o t e dt og r a p h sd e t e r m i n e de n t i r e l yb yt h e kt u t t ep o l y n o m i a l s t h ef i r s tp a r to ft h i st h e s i sc o n s i s t so fc h a p t e r s2a n d3 i nc h a p t e r2 w ef o c u so nt h ef l o wp o l y n o m i a l so fg r a p h s w es t u d yt h ec o e f f i c i e n t so ff l o w p o l y n o m i a la n dp r o v et h a ti ft w oc o n n e c t e dc o s i m p l eg r a p h sh a v et h es a m ef l o w p o l y n o m i a l ，t h e nt h e yh a v et h es a m en u m b e ro fv e r t i c e sa n de d g e s ，t h es a m ee d g e - c o n n e c t i v i t ya n dt h es a m en u m b e ro fm i n i m u mb o n d s u s i n gt h ei n f o r m a t i o n c o n t a i n e di nf l o wp o l y n o m i a lo fg r a p h s ，w ep r o v et h a tt h ed u a lo fg e n e r a l i z e d & g r a p h ，k 5a n dk 3 ，3c a nb ee n t i r e l yd e t e r m i n e db yt h e kf l o wp o l y n o m i a l s i nc h a p t e r3 ，w es h o wt h a tt h el a d d e r s ，m s b i u sl a d d e r sa n d s q u a r eo fc y c l e s a b s t r a c t a r ed e t e r m i n e db yt h e i rc h r o m a t i cp o l y n o m i a la n df l o wp o l y n o m i a lt o g e t h e r a d i r e c tc o n s e q u e n c eo fo u rt h e o r e m si sar e s u l t o fd em i e ra n dn o yt h a tt h e s e c l a s s e so fg r a p h sa r ed e t e r m i n e db yt h e i rt u t t ep o l y n o m i a l s t h es e c o n dp a r ti sc h a p t e r4 w h i c hi sc o n c e r n e da b o u tt h er e s e a r c ho n t w oc l a s s e so fg r a p h s ：o n ei st h et w i s t e dw h e e l 帆i ，知2 ( s e ef i g u r e4 2 ) a n dt h e o t h e rc l a s so fg r a p h si sc a l l e dt h ed o u b l eh a l f - w h e e lw h ( k ：，k 2 ) ( s e ef i g u r e4 3 ( b ) ) t os i m p l i f yt h es t r u c t u r eo ft h eg r a p h s ，w ei n t r o d u c eac o n c e p t o ft r i a n g l e - g r a p hw h o s ei d e ai ss i m i l a rt ol i n e - g r a p h u s i n gt h ei n f o r m a t i o nc o n t a i n e di n t u t t ep o l y n o m i a lo fg r a p h s ，w es h o wt h a tb o t ho ft w oc l a s s e so fg r a p h sc a nb e d e t e r m i n e db yt h e i rt u t t ep o l y n o m i a l s k e yw o r d s ：t u t t ep o l y n o m i a l ，f l o wp o l y n o m i a l ，t - u n i q u e ，f l o w - u n i q u e ， u m q u e a m ss u b j e c tc l a s s i f i c a t i o n ( 2 0 0 0 ) ：0 5 c 6 0 1 v ( p ，q ) 一 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：段募、华 抛罗年多月罗日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： r “ 一 ：内部5 年( 最长5 年，可少于5 年) i ! 秘密1 0 年( 最长1 0 年，可少于1 0 年) i 机密2 0 年( 最长2 0 年，可少于2 0 年) i 一。，。一。一一。，i 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个入和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：脚 1 年歹月夕日 南开大学学位论文电子版授权使用协议 ( 请将此协议书装订于论文首页) 论文系本人在 南开大学工作和学习期间创作完成的作品，并己通过论文答辩。 本人系本作品的唯一作者( 第一作者) ，即著作权人。现本人同意将本作品收 录于“南开大学博硕士学位论文全文数据库 。本人承诺：已提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解直珏太堂图盘焦差王堡在! 焦旦堂僮诠塞的筻堡盘洼滏! 同意 南开大学图书馆在下述范围内免费使用本人作品的电子版： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上允 许读者浏览并下载全文。 注：本协议书对于“非公开学位论文”在保密期限过后同样适用。 院系所名称： 作者签名： 学号： 日期：年月日 c h a p t e r1 i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n 1 1n o t a t i o na n dt e r m i n o l o g y i nt h i st h e s i s ，w eu s es t a n d a r dn o t a t i o n si ng r a p ht h e o r y ( s e e 【2 6 】a n d 【2 6 ) i fg i sa g r a p h ，e ( g ) a n dv ( g ) w i l ld e n o t ee d g e - s e ta n dv e r t e x - s e to fg ， r e s p e c t i v e l y i fg c o n t a i n sn oe d g e t h e ngi sa ne m p t y g r a p h t h ep a t ha n dc y c l e o fkv e r t i c e sa r ec a l l e dk - p a t ha n dk - c y c l e ，d e n o t e da sp ka n d 瓯，r e s p e c t i v e l y t h el e n g t ho ft h es h o r t e s tc y c l eo fgi sc a l l e dt h eg i r t ho fg ，d e n o t e da s9 ( g ) a g r a p hi sa c y c 玩ci fi tc o n t a i n sn oc y c l e t h es e to fn e i g h b o r so fav e r t e xz g i s d e n o t e db y ( z ) ，a n dt h ec a r d i n a l i t yo f ( z ) ，t h a ti s ，t h ed e g r e eo fzi sd e n o t e d b yd ( z ) g i v e nav e r t e xs u b s e tuo fg ，n c ( 纱) d e n o t e st h es e to fv e r t i c e so fg a d j a c e n tt oa v e r t e xo fu i fei sa s e t ，i e id e n o t e si t sc a r d i n a l i t y i f ，e ( g ) ， w es i m p l yu s eg 一，t od e n o t eg 一 ， l e tsb eas u b s e to fe ，t h e ng 司d e n o t e s t h es p a n n i n gs u b g r a p hi n d u c e db ysi ng l e teb ea ne d g eo fg r a p hg ，t h e n g ed e n o t e st h eg r a p ho b t a i n e df r o mgb yd e l e t i n ge ，a n dg | ei st h eg r a p h o b t a i n e df r o mgb yc o n t r a c t i n gt h et w ov e r t i c e si n c i d e n tw i t hea n dr e m o v i n g a l lb u to n eo ft h em u l t i p l ee d g e s ，i ft h e ya r i s e s u p p o s ega n dha r et w og r a p h s w i t hd i s j o i n tv e r t e xs e t s ，t h e ng hd e n o t e sa g r a p ho b t a i n e db yi d e n t i f y i n ga v e r t e xo fgw i t hav e r t e xo fh ( a o p e r a t i o nk n o w na sv e r t e xi d e n t i f i c a t i o n ) a n d guhd e n o t e st h eg r a p hc o n t a i n sga n d 日a sc o m p o n e n t s w eu s e 七( g ) ，x ( a ) a n d 入( g ) t od e n o t et h en u m b e ro fc o m p o n e n t s ，c h r o m a t i c n u m b e ra n de d g e - c o n n e c t i v i t yo fg ，r e s p e c t i v e l y t h er a n ko fas u b s e tso fei s d e f i n e da st h en u m b e ro fe d g e si nt h es p a n n i n gf o r e s to ft h es u b g r a p hi n d u c e d b ysi ng ，i e ，r ( s ) = i y ( g ) i 一七( g s 】) a n dt h ec o - r a n ko fsi sd e n o t e da s n ( s ) = le ( s ) i 一7 ( j 5 ，) ab o n do fag r a p hi sam i n i m a le d g e - c u t t w og r a p h s 皿= ( ，日) a n d 凰= ( k ，易) a r e2 - i s o m o r p h i ci ft h e r ei sab i j e c t i o n 矽：局_ 易s u c ht h a tt h ee d g es e t 蜀冬且i sac y c l ei n 玩i fa n d o n l yi f 砂( 眉) i sac y c l e i n 凰 f o rt h en o t a t i o no fm a t r o i d s ，w ef o l l o wo x l e y 3 2 f o re x a m p l e ，w eu s e m ( g ) t od e n o t et h ec y c l em a t r o i da s s o c i a t e dw i t ht h eg r a p hg c l e a r l y , a n y g r a p hg = ( ke ) d e t e r m i n e sau n i q u em a t r o i dw i t hg r o u n ds e te ( g 1 m a t r o i d s o ft h i sk i n da r ec a l l e dg r a p h i cm a t r o i d s ab a s eo fm ( a ) i sa s p a n n i n gf o r e s ta n d ac i r c u i tc o r r e s p o n d st oac y c l ei ng f o ram a t r o i dm ，w e u s em + t od e n o t et h e d u a lm a t r o i do fm ag r a p hgi sc o s i m p l ei fm + ( g ) i s s i m p l e 1 2o np o l y n o m i a l so fg r a p h s 1 2 1c h r o m a t i cp o l y n o m i a lo f g r a p h s b a s i cd e f i n i t i o na n db a c k g r o u n d t h e c o l o r i n gp r o b l e m so fg r a p h sa r ec e n t r a li nc o m b i n a t o r i c sa n daf i r mp a r t o fe a r l yg r a p ht h e o r yw a sd e v e l o p e di no r d e rt os o l v et h ef o u r - c o l o r p r o b l e m c h r o m a t i cp o l y n o m i a lw a si n t r o d u c e db yb i r k h o f ff 3 p r e c i s e l yi na na t t e m p tt o s o l v et h i sp r o b l e m a k - c o l o r i n go fgi sam a p p i n gc ：yh _ 1 ，2 ，k s u c ht h a tc ( z ) c ( y ) i fx yi sa ne d g eo fg t h ec h r o m a t i cp o l y n o m i a lo fa g r a p hg i sd e f i n e da s p g ( z ) = t h en u m b e ro fx - c o l o r i n go g i ti se a s yt os e et h a tp g ( 。) i si n d e e da p o l y n o m i a l l e tp tb et h en u m b e ro f 2 c h a p t e r1 i n t r o d u c t i o n p a r t i t i o n so fv i n t oe x a c t l yii n d e p e n d e n ts e t s ，t h e n 忍( z ) 竹 = p i x ( x 一1 ) ( z i + 1 ) i = 1 s oi t i sc l e a rt h a tt h ef o u r - c o l o rt h e o r e mi se q u i v a l e n tt ot h ef a c tt h a tf o r e v e r yp l a n a rg r a p hg ，尼( 4 ) 0 a sw ek n o w ，t h es o l u t i o no ft h ep r o b l e mu l t i - m a t e l yf o l l o w e da d i f f e r e n tr o u t e ，h o w e v e r ，t h ei n t e r e s ti nc h r o m a t i cp o l y n o m i a l s h a si n c r e a s e de v e rs i n c e f u n d a m e n t a lr e s u l t so nc h r o m a t i cp o l y n o m i a l s i nt h ef o l l o w i n g ，w ew i l ll i s ts o m ef u n d a m e n t a lr e s u l t sw h i c ha r ev e r yu s e - f u li ns t u d y i n gc h r o m a t i cp o l y n o m i a l w eb e g i nw i t hw h i t n e y sf u n d a m e n t a l r e d u c t i o nt h e o r e m 【4 6 t h e o r e m1 1 ( w h i t n e y , 4 6 】) l e tgb eag r a p ha n deb ea ne d g e 锄g t h e n p c ( x ) = p a 一。( z ) 一2 ，g e ( z ) i n1 9 3 2 ，w h i t n e y 【4 6 】c h a r a c t e r i z e dt h ec o e f f i c i e n t so fc h r o m a t i cp o l y n o m i a l p g ( z ) i nt e r m so fc e r t a i ns p a n n i n gs u b g r a p h so fg t os i m p l i f yt h ec o u n t i n go f t h e s es u b g r a p h s ，h ei n t r o d u c e dt h ec o n c e p to fb r o k e nc y c l e l e tgb eac o n n e c t e dg r a p hw i t hnv e r t i c e sa n dm e d g e sa n dl a b e lt h ee d g e s o fgw i t hi n t e g e r sl ，2 ，m t h e ngi sa ne d g e - l a b e l l e dg r a p h l e tcb ea c y c l eo fga n deb et h ee d g eo fca s s i g n e dw i t ht h el a r g e s ti n t e g e r t h ep a t h p = c ei sc a l l e dt h eb r o k e nc y c l ea s s o c i a t e dw i t hc t h ef o l l o w i n gi sa w e l l - k n o w nt h e o r e m ，o f t e nr e f e r r e da sb r o k e nc y c l et h e o r e m t h e o r e m1 2 ( w h i t n e y , 【4 6 】) l e tgb ea ne d g e - l a b e l l e dg r a p hw i t hnv e r t i c e s a n dme d g e s t h e n 竹一l p c ( x ) = ( 一1 ) m t 扩， i = 0 w h e r e ? t f l ii st h en u m b e r0 i - s u b s e t so e ( g 、t h a tc o n t a i nn ob r o k e nc y c l eo g t h ec o e f f i c i e n t sa n ds t r u c t u r eo fc h r o m a t i cp o l y n o m i a lh a v eb e e ne x t e n s i v e l y s t u d i e d t h ef o l l o w i n gr e s u l tr e l a t i n gt h ec o e f f i c i e n t sc a nb ef o u n di n 【2 1 3 t h e o r e m1 3 ( k o ha n dt e o ，【2 1 1 ) l e tgb eag r a p ho fo r d e r 几a n ds i z em ， t h e np g ( z ) i sap o l y n o m i a ld ，d e g r e en s u p p o s et h a tp a ( x ) = 墨o a i x 加，t h e n t 1 a l la i 台a r ei n t e g e r sa n da l t e r n a t ei ns i g n ； i i ) a n = 0 i i i i ) a o = 1 ： i 口) a l = 一m i 口) 6 2 = ( m 2 ) - t l ( a ) ； v i ) a 3 = 一( 饥) + ( 仇一2 ) t l ( g ) + t z ( g ) 一2 t 3 ( g ) ， w h e r eh ( g ) i st h en u m b e ro f 蚝i ng ，t 2 ( a ) 诂t h en u m b e ro y4 - c y c l e sw i t h o u t c h o r d sa n dt 3 ( c ) i st h en u m b e ro y1 ( 4i ng ) ( - u n i q u e n e s so fg r a p h s i ti se a s yt os e et h a tp c ( z ) c o n t a i n ss i g n i f i c a n ti n f o r m a t i o no fg i n1 9 7 8 c h a oa n dw h i t e h e a db e g a nt os t u d yw h i c hg r a p hc a l lb ed e t e r m i n e db yi t sc h r o - m a t i cp o l y n o m i a l t h e yi n t r o d u c e dt h en o t i o no fx - u n i q u eg r a p h ag r a p hgi s x u n i q u ei fa n yg r a p hhh a v i n gt h es a m ec h r o m a t i cp o l y n o m i a lw i t hgi m p l i e s t h a th 竺g w es a yt h a thi s ) ( - e q u i v a l e n tt og i f 尸hx ) = p a ( z ) i np r o v i n g x - u n i q u e n e s s ，t h em a i nt o o li st h ef o l l o w i n gt h e o r e m t h e o r e m1 4 ( k o ha n dt e o ，【2 1 】) l e tga n d 日b et w os i m p l eg r a p h ss u c h t h a tp a ( z ) = 岛( z ) t h e n z ) i y ( g ) j = l y ( 日) la n df e ( g ) i = f e ( 日) f ? i i ) ga n dhh a v et h es a m eg i r t h ，i e ，g ( g ) = 9 ( 日) f u r t h e r m o r e ，t h e yh a v e t h es a m en u m b e ro yt h es h o r t e s tc y c l e s ； i i i ) t l ( g ) = t l ( h ) a n dt 2 ( g ) 一2 t 3 ( g ) = t 2 ( h ) 一2 t 3 ( h ) ，w h e r et l ( g ) ， a n dt 3 ( a ) d e n o t et h en u m b e ro ic 3 ，qa n d 段o i g ，r e s p e c t i v e l y ； 4 t 2 ( a ) c h a p t e r1 i n t r o d u c t i o n 锄) gi sc o n n e c t e d 矿a n do n l yi fh i sc o n n e c t e d ； ) gi s2 - c o n n e c t e di fa n do n l yi fh i se - c o n n e c t e d ； 优) ga n d hh a v et h es a m ec h r o m a t i cn u m b e r , t e x ( a ) = x ( 日) s e v e r a lc l a s s e so fg r a p h sh a v eb e e ns h o w nt ob ex - u n i q u e ，f o re x a m p l e ， c o m p l e t eg r a p h s ，c y c l e sg a n dc o m p l e t eb i p a r t i t eg r a p h s ，gf o rp ，口22 ( s e e 【2 0 ， 21 ，【2 2 】， 2 5 】a n d 3 6 】f o rd e t a i l so nx - u n i q u eg r a p h s ) 1 2 2t u t t ep o l y n o m i a lo fg r a p h s t u t t ep o l y n o m i a li sb r o u g h tf o r w a r di n1 9 5 4b yt u t t ew i t ht h ei n i t i a ln a l t l e d i c h r o m a t ep o l y n o m i a l ( s e e 4 1 】) i ti sa ni m p o r t a n tt o o li ng r a p ht h e o r ya n d m a n yo t h e rf i e l d ss u c ha sk n o tt h e o r yo rs t a t i s t i c a lp h y s i c s t h ed e f i n i t i o no ft u t t ep o l y n o m i a l t h e r ea r em a n yw a y st od e f i n et u t t ep o l y n o m i a l w em e n t i o nt w oo ft h e m f i r s t l y , w es h a l lg i v et u t t e so r i g i n a ld e f i n i t i o no fh i sp o l y n o m i a l 1 t u t t e so r i g i n a ld e f i n i t i o n l e tgb eag r a p hw i t h 佗v e r t i c e sa n dme d g e sa n dtb eas p a n n i n gt r e eo f g w el a b e la l lt h ee d g e so fgw i t h1 ，2 ，ma r b i t r a r i l y 1 ) t h ed e l e t i n go fa ne d g eio ftd e c o m p o s e st i n t ot w oc o m p o n e n t sx a n d t h ee d g eii si n t e r n a l l ya c t i v ei nti fi rf o ra l le d g e srt h a th a v eo n e e n di nka n dt h eo t h e ri nk t h ei n t e r n a la c t i v i t yo lti st h en u m b e ro fi n t e r n a l l ya c t i v ee d g e si nt 2 ) l e tt + = g tb et h ec o t r e eo ft ，a n dl e tjb ea ne d g eo ft t h e n t h e r ei sau n i q u ec y c l ezi nt u 歹t h ee d g eji se x t e r n a l l ya c t i v ei nti f j 8 f o ra l le d g e s8i nz t h ee x t e r n a la c t i v i t yo ti st h en u m b e ro fe x t e r n a l l ya c t i v ee d g e si nt 5 c h a p t e r1 i n t r o d u c t i o n d e f i n i t i o n1 - 1 t h ed i c h r o m a t e o rt u t t ep o l y n o m i a lo lgi st h ef u n c