作者jameschou (DOG)
看板Math
标题Re: [图论] planar
时间Thu Jan 27 22:19:31 2011
※ 引述《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
1F：推 mqazz1 :谢谢! 原来还要考虑无限区域 01/28 21:02