[問題] 八點八邊圖 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 想看看大家有沒有更聰明法謝謝走牆大

繼續閱讀