圖論27電子科大楊春-wenkub.com
2024-12-31 14:05 本頁(yè)面
【正文】 例如：教材上的 Read猜想就是一個(gè)待研究問(wèn)題。但是它們鄰點(diǎn)狀況不相同 :u1有 4個(gè) 2度鄰點(diǎn)。 (2) 不存在以 k43k3+3k2為其色多項(xiàng)式的單圖。e). 由假設(shè)可令 : Pk(Ge)=kn+a1kn1+…+a n1kn1 ，且 a1=m+1。 當(dāng) m=1時(shí)， Pk(G)= Pk(Ge) Pk(G 對(duì)于 Ge來(lái)說(shuō)，由歸納假設(shè)，可設(shè)其色多項(xiàng)式為： 26 1 0 x t 0 1 2 ?1 ? 0 1 n 同樣，可設(shè) G 設(shè) m=k時(shí)，命題結(jié)論成立。當(dāng) i1+i2+…+i t=k時(shí)， M1∪ M2 ∪ … ∪ Mt必是 G的具有 k個(gè)分支的理想子圖。遞推方法是指數(shù)類計(jì)算量，而理想子圖法中主要計(jì)算量是找出所有理想子圖，這也不是多項(xiàng)式時(shí)間算法。 定理 3 若 G有 t個(gè)分支 H1,H2,…H t,且 Hi的伴隨多項(xiàng)式為h (Hi, x), i=1,2,…,t, 則： 1( , ) ( , )t iih G x h H x?? ? 該定理說(shuō)明，在求 的伴隨多項(xiàng)式時(shí)，可以分別求出它的每個(gè)分支的伴隨多項(xiàng)式，然后將它們作乘積。 G 解： (1) G的補(bǔ)圖為： G (2) 求出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式系數(shù) ri (1≦i≦6) 16 1 0 x t 0 1 2 ?1 ? 0 1 n 1) r = 6 66( ) 1r N G??G 2) r = 5 55 ( ) 5r N G 3) r =4 17 1 0 x t 0 1 2 ?1 ? 0 1 n G 4) r = 3 44 ( ) 6r N G?? 5) r =2 33 ( ) 2r N G22 ( ) 0r N G 6) r =1 11( ) 0r N G (3) 寫(xiě)出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式 1( , ) n iiih G x r x?? ?3 4 5 62 6 5x x x x? ? ? ?18 1 0 x t 0 1 2 ?1 ? 0 1 n 3 4 5 6( ) 2 [ ] 6 [ ] 5 [ ] [ ]kP G k k k k? ? ? ? (4) 將 代入伴隨多項(xiàng)式中得到 Pk(G)。稱 1( , ) n iiih G x r x?? ? 為圖 G的伴隨多項(xiàng)式。 1[]r iiGV?G 這說(shuō)明： G的任一 r色劃分必然對(duì)應(yīng) 的一個(gè)理想子圖。 例 2 求 N4(G), N5(G)。 G1 G3 G2 6 1 0 x t 0 1 2 ?1 ? 0 1 n (1) G1 ?321( ) ( 1 ) ( 2) ( 1 ) 2kP G k k k k k k k k? ? ? ? ? ? ? ? 也可由推論： G1 ? 2( 1) ( )kk P K? 322k k k? ? ?7 1 0 x t 0 1 2 ?1 ? 0 1 n (2) G2 22( ) ( 1 ) ( 2) ( 3 ) 2 ( 1 ) ( 2) ( 1 )( 1 ) ( 3 3 )kP G k k k k k k k k kk k k k? ? ? ? ? ? ? ? ?? ? ? ?8 1 0 x t 0 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1