作者gn00618777 (123)
看板Grad-ProbAsk
标题[理工] [离散]-平面图
时间Tue Oct 27 19:42:18 2009
假设一个区域由4个边组成，令N=所有区域所围成的边(含重复边)
，此时区域有2个(包含外面)， N=8。
有一题题目:设G=[V,E]是一个平面图，且每一个面皆为3角形，|V|=n,|E|=m
试证 m=3n-6
Ans:依题意每一区域皆为三角形 -> 3r＝2m
又因为是平面图满足 v-e+r=2;n-m+r=2 带入 3r=2m -> m=3n-6
我不太懂3r=2m，应该是说观念不懂！若我一开始最上面说的N=8这个假设成立
也是说如果我一个区域用3个边围成，那麽区域就有2个--> 3*2=2*3 成立
可是！！ 题目说每一个面为3角形，若两个三角形和成一个四边形，也代表每个区域都为3
角形阿 ，这时区域变为3(包含外面的) ，3r=2m ---> 3*3不等於2*5，3r=2m就不成立
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.138.100.126
※ 编辑: gn00618777 来自: 220.138.100.126 (10/27 21:39)
※ 编辑: gn00618777 来自: 220.138.100.126 (10/27 21:41)
1F：推 gn01642884:可能ㄧ开始的假设含重复边要把重复的算进去 10/29 11:05
2F：→ gn01642884:也就是说两个三角形合成ㄧ个四边形的边数依照一开始定 10/29 11:06
3F：→ gn01642884:义是５＋１＝６(１为重复边) 这样的话3r=2m就是对的 10/29 11:07