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