Re: [圖論] planar
※ 引述《mqazz1 (無法顯示)》之銘言：
: 假設 G = (V, E) 有含M個conponent的planar
: |V| = v
: |E| = e
: r表示區域的個數
: 證明 v-e+r = 1+M
: 請問要怎麼證呢?
: 謝謝
首先已知連通圖的 v-e+r = 2
設這M個連通圖的點數,邊數,區域數分別為v1,v2,...,vM 、 e1,e2,...,eM 、r1,...,rM
又 |V| = v1+v2+...+vM
|E| = e1+e2+...+eM
r1,r2,...,rM每個區域都算了一次最外面無窮大的區域一次
故無窮大的區域被算了M次
=> r = r1+r2+...+rM - (M-1)
=> r + (M-1) = r1+r2+...+rM
由每個連通圖知:
v1-e1+r1 = 2
v2-e2+r2 = 2
.
.
.
vM-eM+rM = 2
=> |V| - |E| + r+(M-1) = 2M
=> v-e+r = M+1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.76.214
推
01/28 21:02, , 1F
01/28 21:02, 1F
討論串 (同標題文章)