2010-09-19

課本6-25 範例6 第b小題

題目中提到,一個n個頂點的完全無向圖
要導成有向圖會有幾種可能,在這裡對有向圖的定義產生了一些疑慮
所謂的有向圖的邊是規定說一個邊只能描述一個方向嗎,
也就是是否不允許雙箭頭的邊存在呢?
還是若是要描述兩個頂點雙向皆可連通的話,就視為多重圖呢?
當有人問要把無向的完全圖可導出幾個有向圖,每個邊要視為兩種或三種可能才對呢
多重圖也是有有向多重圖的,還是一般都略過不計呢

1 則留言:

線代離散助教(wynne) 提到...

這種圖的轉換並不常見, 所以題目一般應該都會說明圖應該要用甚麼方式來改, 像這題題目中括號裡的那句話就是在說明對於每一個原本的undirected edge, 我們都只要指定一個方向給它即可