Re: [請益] 請教一個遊戲的解法...（連接水火電）
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者killyou (xxx)時間20年前 (2005/12/23 00:09)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/2 (看更多)
※ 引述《tkks (tkks)》之銘言：
: 就是現在有三個水跟三個田
: ○ ○ ○
: 田 田 田
: 每個水都要接三個田，可是線跟線不可以重疊也不行田接田和水接水
: 共要畫出九條線!!
: 請問有人知道這個題目的答案嗎?
: 解很久了還是都會差一條線，所以想請知道答案的板友可否解答這題的答案。謝謝!!
這是planar graph 的問題, K3,3 不是planar的!
所謂planar graph就是可以畫在平面上,經適當的伸縮彎曲線,可以完全無交錯
於是有個定理 Kuratowski[1930]
一個圖是平面的 if and only if 不含 K5 or K3,3的分割.
分割是指在線上加點
K5 是五點兩兩互連, K3,3 是一邊各三點,與另一邊都連.
所以一定至少有一個交錯處.
╭○─●─○.
││..│..│.
│●─○─●
╰────╯
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.50.234
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
puzzle 近期熱門文章
5
21
PTT遊戲區 即時熱門文章