※ 引述《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