[问题] 八点八边图 ddtddt PTT批踢踢实业坊

楼主: ddtddt (得) 2014-07-30 11:42:14

证明或反证
任意给一个八点八边图,(规定每个点的degree至少要是一 )
你一定都可以在点中填入三个 1 三个-1 及两个 0
使得所有边的左右两点之积必不为 -1 .(换句话说 1 和 -1不相邻)
ex:
1

作者: walkwall (会走路的墙) 2014-07-30 21:24:00

嗯...如果是9边就有K3,3了 8边似乎是成立

楼主: ddtddt (得) 2014-07-30 22:23:00

谢谢捧场推文没人讨论好可怜@@K3,3很好的点不过这边限制八点都至少degree1

作者: walkwall (会走路的墙) 2014-07-30 22:32:00

喔抱歉忽略掉degree1的部分只是没这条件也似乎成立?另一个角度来看问题是 : 是不是能保证存在两个点去掉之后剩余的连通区域最多三个点?

楼主: ddtddt (得) 2014-07-30 23:13:00

没限制条件也似乎成立没错^^ 只是我觉得最难证的是八点怎么拿掉两点应该是蛮关键的,其实我现在没有漂亮证明不过应该不是连通区域最多三点如果剩 2 2 2的话就不行

作者: walkwall (会走路的墙) 2014-07-30 23:56:00

嗯 222我是漏掉考虑了

楼主: ddtddt (得) 2014-07-31 11:44:00

我目前是有一个蛮长的证明啦:p 想看看大家有没有更聪明法谢谢走墙大

继续阅读