作者chchwy (mat)
看板Prob_Solve
標題[問題] 請問雙色著色問題
時間Wed Oct 27 23:42:00 2010
問題敘述是這樣子的
Prove that the regions (or faces) formed by a planar graph drawing all of
whose vertices have even degree can be colored with two colors such that
any neighboring regions (having an edge in common) are colored differently.
同學問我的一個問題
但是因為我對圖論證明不是很熟悉，所以上來請教各位，有沒有什麼方向可以指點
我目前看到兩個條件
1. even degree : 我會聯想到euler cycle
2. planar graph
但是左看右看就不知道要如何下手
先謝謝了
--
-- P_Mat <無名個人版> bbs.wretch.cc
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.104.123
1F：→ chihungtzeng:hint: dual(G)裡每個cycle長度是偶數 10/28 00:18
2F：→ chihungtzeng:所以 dual(G) 是bipartite graph 10/28 00:19
3F：推 jfurseteidce:咦? 這不就是我們作業? 11/14 02:33
4F：→ chchwy:是作業沒錯 不過我沒修課LOL 我只是純興趣解題 12/04 03:46