圖論27電子科大楊春(編輯修改稿)
2025-01-20 14:05 本頁面
【文章內(nèi)容簡介】 (3) 寫出關(guān)于補(bǔ)圖的伴隨多項式 1( , ) n iiih G x r x?? ?15 1 0 x t 0 1 2 ?1 ? 0 1 n (4) 將 代入伴隨多項式中得到 Pk(G)。 []i ixk? 例 3 求下圖 G的色多項式 Pk(G)。 G 解： (1) G的補(bǔ)圖為： G (2) 求出關(guān)于補(bǔ)圖的伴隨多項式系數(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) 寫出關(guān)于補(bǔ)圖的伴隨多項式 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) 將 代入伴隨多項式中得到 Pk(G)。 []i ixk?2 ( 1 ) ( 2) 6 ( 1 ) ( 2) ( 3 )5 ( 1 ) ( 2) ( 3 ) ( 4)( 1 ) ( 2) ( 3 ) ( 4) ( 5 )k k k k k k kk k k k kk k k k k k? ? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ? 可以作如下計算： 12( ) ( ) 0P G P G??3 ) 12PG ? 由此可以斷定： 。最優(yōu)著色方式數(shù)有 12種。 ( ) 3G? ?19 1 0 x t 0 1 2 ?1 ? 0 1 n 使用理想子圖法求色多項式，還可以通過如下定理進(jìn)行改進(jìn)。 定理 3 若 G有 t個分支 H1,H2,…H t,且 Hi的伴隨多項式為h (Hi, x), i=1,2,…,t, 則： 1( , ) ( , )t iih G x h H x?? ? 該定理說明，在求 的伴隨多項式時，可以分別求出它的每個分支的伴隨多項式，然后將它們作乘積。 G 例 4 求下圖 G的色多項式 Pk(G)。 20 1 0 x t 0 1 2 ?1 ? 0 1 n 解 : (1) 畫出 G的補(bǔ)圖 G 2 1 5 4 3 G5 1 4 3 2 H3 H2 H1 (2) 求出補(bǔ)圖中個分支的伴隨多項式 1( , )h H x x?22( , )h H x x x?? 23( , )h H x x x?? (3) 求出補(bǔ)圖的伴隨多項式 2 2 3 4 5( , ) ( ) 2h G x x x x x x x? ? ? ? ?21 1 0 x t 0 1 2 ?1 ? 0 1 n (4) 求出 G的色多項式 ( )
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1