→ monkeykej:考場遇到這題我會跳過A小題...感覺畫完就吃虧了 /____\ 03/23 18:54
推 amidofun:高手 感謝 真得很難畫 03/23 19:09
※ 引述《amidofun ()》之銘言：
: Let G1(V1,E1) and G2(V2,E2) be any two graphs.
: Define graph G(V,E) = G1 ×G2 such that:
: vertex set V={(x,y)|x屬於V1 and y屬於V2} and edge set
: E={((x1,y1),(x2,y2))|(x1,x2)屬於E1 or (y1,y2)屬於E2}
: Consider Figure 1.
: ╱╲ ／╲
: ︱ ︱ ｜ ｜
: ｜ ｜ ︱ ︱ 應該是兩個正六邊形
: ╲／ ╲╱
: G1 G2
: (a)Draw G(V,E) = G1 ×G2
: (b)Give |V| and |E|
: (c)Give the diameter of graph G(V,E) = G1 ×G2
(a)
先取個名子好了，比較好講，假設G1的點是a1~a6 G2的點是b1~b6
兩個定義都依照下圖順序
1
2 6
3 5
4
那根據定義G圖的點，就是G1和G2的點集合之Cartesian product
白話來講就是有序對，G圖的點包含(a1,b1)、(a1,b2)、......、(a1,b6)
(a2,b1)、(a2,b2)、......、(a2,b6)
. . .
. . .
. . .
(a6,b1)、(a6,b2)、......、(a6,b6)
每一個( )就是一個點
那edge的定義是什麼咧?
他說E={((x1,y1),(x2,y2))|(x1,x2)屬於E1 or (y1,y2)屬於E2}
所以看上面那個點的集合
第一列中的每一個點 都和第二列中每一個點相連 原因是a1與a2在G1中有相連
也就是說 因為E1中有 (a1,a2) 這個edge
同理第二列跟第三列也是各點完全連
....
第六除了被第五列相連之外，他也跟第一列相連 因為上面我擺的順序定義是這樣
a看完了 再想b也是同理 換言之 各行之間 也是有一模一樣的關係
接下來討論degree，每一個點都與上一列、下一列、左一行、右一行的6個點相連
6*4=24 扣掉重複算的四個斜角 所以degree為20
畫圖時我建議你這樣話
每一行列的點都畫成一個正六邊形
所以有六個正六邊形
按照上面定義之順序 將六個正六邊形擺成大的正六邊形
之後再把剩下的邊補滿
我是這樣畫的，然後就很亂 = =
好吧...你看有沒有其他版友有可以看的很清楚的畫法
B小題 |V|= 6*6 = 36， |E|= 20*36/2 =360
C小題問最遠兩點之間距離為何
意如果依照我的定義 (a1,b1)與(a4,b4)為最遠距離(事實上不唯一)
但是我挑這兩點計算
是因為我相信不會有其他兩點距離比他們更大
而(a1,b1) -> (a2,b4) -> (a3,b4) -> (a4,b4)
可知其距離為3
因為是計算題不是證明題
應該不需要寫到很嚴謹
不然的話，不失一般性由(a1,b1)為起點到(ai,bj)不超過3，應該不難證出
不過既然是計算題就不再贅述
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.160