[理工] 离散着色多项式 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

继续阅读