作者yesa315 (XD)
看板Grad-ProbAsk
標題[理工] [離散]-Tree
時間Sun Sep 27 14:33:50 2009
1. A graph in which there has at most one path between every pair of
vertices is a tree
答案為FALSE 但我覺得好奇怪 {連通 沒cycle e=v-1} 任兩成立 就是tree
以上我覺得任兩點有path 則為連通 路徑惟一 表示沒cycle
則應該是tree阿 還是我想錯了?
2. An acyclic graph with 8 vertices has 7 edges
沒環路且e=v-1的圖 條件明顯成立
但答案為false 更奇怪了...
懇求高手指導
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.127.208.96
推 chenbojyh:第一提好像沒提到"連通"耶 09/27 15:10
→ yesa315:喔 想通了 第一題最多一path 也可以沒path 所以不連通 09/27 16:22
→ ssccg:第二題也許是沒提到simple graph，所以可以有loop 09/27 16:38
→ yesa315:loop算是迴路嗎? 09/27 17:08
→ ssccg:cycle有一種定義是至少3 edge，所以loop不算cycle 09/27 19:17
→ ssccg:總之沒提到simple graph的話都小心一點 09/27 19:17
→ yesa315:嗯嗯 感謝解答 09/27 23:19