作者gn00618777 (123)
看板Grad-ProbAsk
标题[理工] [离散]-平面图
时间Wed Oct 28 18:06:08 2009
问了那摸多，我想问的东西始终搞不清楚，这次我在问一个终极版的=.=
成大
For a simple connected planar graph G(V,E) with |V|=7 and |E|=15
how many edges does each region of G have?
Ans:令每个region的边数皆为k,N表示所有region边数总和，r表示region个数
则 N=kr=2|E|
又|V|-|E|+r=2
所以r = 10
代回第一式 k=3
我用答案来问好了，每一个区域的边都是3，那麽这个图应该画不出来吧，能符合的
也只有一个三角形
● ●
｜ ＼ ｜＼ 只要在随便多一个region 3(k)*3(r)< 2*6(|E|)
｜ ＼｜ ＼
●-----●----● 更何况上面题目r都可以到10，能符合这个N=kr=2|E|
式子就只能是一个region用3个边围起来的"一个3边行的图"
不可能在多加其他的，可是他的region竟然到10，你只要多加一个
外面的region就变成不只3个边围起来了
不知道表达的好不好~"~
希望大家能看的懂我的问题..
再补充一问 一个四边形 若N表示所有区域所围成得边，那麽r=2，e=4，N=8(?)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.224.220.125
※ 编辑: gn00618777 来自: 61.224.220.125 (10/28 18:09)
※ 编辑: gn00618777 来自: 61.224.220.125 (10/28 18:09)
1F：推 FRAXIS:一个正三角形 三顶点与其内心连线 分成三个小三角型 10/28 18:46
2F：→ FRAXIS:然後每个小三角形的三顶点 与该小三角形的内心连线 10/28 18:47
3F：→ gn00618777:太感谢你了 我以为是我的region观念错，结果只是图画 10/28 19:28
4F：→ gn00618777:画不出来 10/28 19:28