[理工] [離散] 圖論

[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

  any??然後又consider Figure 1   我真不知要畫啥

  我猜畫一個正六邊形

(b)Give |V| and |E|

  |V|=min{|V1|,|V2|}  |E|=|V|

(c)Give the diameter of graph G(V,E) = G1 ×G2

   diameter?直徑?難道是圓?



請高手解救  謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.32.102.8
→ assassin88:寫一下題目出處 你打得好亂看不懂= =
→ amidofun:東海98離散第三題
推 assassin88:怎麼線上考古題都只有學士班的= ="
→ amidofun:我是去資工系網頁找到的
推 assassin88:98離散第三題是 1~200取101個術耶...
→ monkeykej:G是一個36個degree為20的vretices所成的圖，不是六邊形
→ monkeykej:B題你這樣寫是題目對|V|的定義嗎?是的話不就是6...??
→ amidofun:ass 要連結我有
→ monkeykej:C題diameter指圖中最遠兩點間的距離 是3 它不是圓
→ amidofun:mon 你的G好深澳阿
→ amidofun:http://www.csie.thu.edu.tw/?q=questioned/master
→ amidofun:V={(x,y)|x屬於V1 and y屬於V2}  兩點算V的一點  不是嗎?
→ amidofun:XD我的想法好單純好天真
→ monkeykej:我看過題目了...B題|V|就是20 |E|= 20*36/2 = 360
推 lationmore:來806有專人教你
→ assassin88:我看法跟他不同 感覺 |V|=36 |E|=180 ..
→ monkeykej:呃?
→ amidofun:806?
→ kennykobe:806是旅館房間號碼嗎?
→ kuso787y:如果是旅館房間號碼，有8樓的旅館應該都蠻貴的...