[理工] 離散著色多項式 zxc2051516 PTT批踢踢實業坊

作者: zxc2051516 (SilverCrow) 2016-09-03 22:17:18

http://i.imgur.com/Gt4LfEx.jpg
忘了這圖是怎麼化減
請求幫忙
P.S圖論好難讀……………

作者: Amagiyome (_(:3」∠)_) 2016-09-03 22:20:00

拿掉一個邊，然後把那兩個點黏起來圖上a,b兩個點有邊e相連，所以兩個一定要不同色把e這個邊拿掉代表a,b可以同色也可以不同色，然後減掉把a,b兩點黏起來代表a,b兩點必同色

作者: darren0831 (達) 2016-09-03 22:37:00

原理是這樣的；原圖上面兩點一定不同顏色，拆成等號左邊兩個圖，一個圖是上面兩點可以同色或不同色另一個是兩點一定同一色（點都連在一起了），所以等號右邊多項式相減就是答案

作者: zxc2051516 (SilverCrow) 2016-09-03 22:40:00

我現在是不知道怎麼拆成4個小圖那

作者: Amagiyome (_(:3」∠)_) 2016-09-03 22:45:00

重複同樣的動作目標把圖拆成剩下3個邊然後暴力法下去解第二行那個你了解的話第三行只是再把第二行的第一個圖拆成兩個假設a下面那個點是c，b下面那個點是d，他把bd那個邊拆掉然後把b點黏到d點

作者: zxc2051516 (SilverCrow) 2016-09-03 23:09:00

謝A大神手，懂了OwO

繼續閱讀