作者sophialiege (with friends)
看板Math
标题Re: [图论] Hamiltonian的证明
时间Fri Jan 28 23:04:18 2011
※ 引述《mqazz1 (无法显示)》之铭言：
: Let G be a planar Hamiltonian simple graph with n vertices
: Let C be a Hamiltonian cycle in G
: Then with respect to C, prove Σ(k-2)(rk-sk) = 0
: Here rk is the number of faces inside C whose boundary contain exactly k edges
: sk is the number of faces outside C whose boundary contains exactly k edges
: 原始: http://ppt.cc/(6W,
: 请问这题要怎麽证呢?
: 谢谢
Let f_in and f_out be the number of faces inside and outside C (included C),
e_in and e_out be the number of edges inside and outside C (included C),
v_in and v_out be the number of vertices inside and outside C.
Clearly, v_in = v_out = v
\sum (k-2)r_k = (\sum k(r_k)) - 2(\sum r_k)
= (2 e_in - v) - 2 (f_in - 1)
= 2 (e_in - f_in - v) + v + 2
= v-2
Similarly, \sum (k-2)s_k = v-2. QED
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.36.54.5
※ 编辑: sophialiege 来自: 114.36.54.5 (01/28 23:06)