Re: [圖論] Hamiltonian的證明
※ 引述《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)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：