作者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