[理工] [離散]-平面圖
問了那摸多,我想問的東西始終搞不清楚,這次我在問一個終極版的=.=
成大
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)
推
10/28 18:46, , 1F
10/28 18:46, 1F
→
10/28 18:47, , 2F
10/28 18:47, 2F
→
10/28 19:28, , 3F
10/28 19:28, 3F
→
10/28 19:28, , 4F
10/28 19:28, 4F
討論串 (同標題文章)