圖論27電子科大楊春(參考版)
2025-01-04 14:05本頁面
【正文】 30 1 0 x t 0 1 2 ?1 ? 0 1 n 作業(yè) P187190 習題 7 ： 28 ， 31， 32， 33 31 1 0 x t 0 1 2 ?1 ? 0 1 n Thank You ! 32 1 0 x t 0 1 2 ?1 ? 0 1 n 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH 。 通過直接計算得： Pk(G1)=Pk(G2)=10[k]3 +5[k]4 + [k]5 對于圖的色多項式，還有許多結(jié)論和進一步研究的問題。而 v1只有兩個 2度鄰點。 G1 G2 u1 v1 證明：因為 G1和 G2中分別有一個唯一的 4度頂點： u1與v1。 事實上，一方面，如果它是某單圖的色多項式，則由多項式本身可以得到點色數(shù)為 1； 另一方面，由 (1)和多項式本身，如果多項式是某單圖的色多項式，則 m(G)=3,于是點色數(shù)至少為 2. 上面推導導出了矛盾！ 注 : (2) 同構(gòu)的圖具有相同的色多項式，但逆不真。 28 1 0 x t 0 1 2 ?1 ? 0 1 n 所以： Pk(G)= kn+(a1+1)kn1+(a2+b1)kn2+…+ b n2kn2 所以， a1+1=m。 Pk(G考慮單圖 G=(n ,m). 由遞推公式： Pk(G)= Pk(Ge) Pk(Ge)= ，結(jié)論成立。 證明： (1) 采用對邊數(shù)進行數(shù)學歸納證明。e的色多項式為： 1 2 11 2 1( ) ... ( 1 ) , 0n n n nk n iP G e k a k a k a k a? ? ? ?? ? ? ? ? ? ? ?1 2 3 21 2 2( ) ... ( 1 ) , 0n n n nk n iP G e k b k b k b k b? ? ? ? ?? ? ? ? ? ? ? 由色多項式遞推公式得： ( ) ( ) ( )k k kP G P G e P G e? ? ?1 2 11 2 2 1 2( 1 ) ( ) ... ( 1 ) ( )n n n n nnk a k a b k a b k? ? ? ??? ? ? ? ? ? ? ? ? 注 : (1) 定理的逆不成立 ! 27 1 0 x t 0 1 2 ?1 ? 0 1 n 例 5 (1) 用遞推公式證明：設 G=(n ,m)是單圖，則在其色多項式 Pk(G)中 kn1的系數(shù)是 m。e。 考慮 m=k+1的單圖 G。 當 m=0時， Pk(G)=kn, 命題結(jié)論成立。 24 1 0 x t 0 1 2 ?1 ? 0 1 n 在給定的 i1,i2,…,i t且 i1+i2+…+i t=k情形下，對應的 G的具有 k個分支的理想子圖個數(shù)為： 12 12( ) ( ) ( )ti i i tN H N H N H 所以， G的具有 k個分支的理想子圖的總個數(shù)為： 121212( ) ( ) ( ) ( )ttk i i i ti i i kN G N H N H N H? ? ?? ?121212 tti i tii i i ka a a? ? ?
教學課件相關推薦
鄂ICP備17016276號-1