[理工] 台大電機98 資結第12題

[DiLegend (JOU)]

Any undirected graph with n nodes and n-1 edges,
where n>=1, is a tree

找到的答案是說false
但想半天想不出來是圖長怎樣會出錯

Note:
Graphs
A graph does not contain self-circular edges,
e.g.,(u,u),nor multiple edges between two nodes,
i.e., at most one entry (u,v) in E for each distinct u and v


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.106.241
→ love5566188:若graph為unconnected有兩個components其一為4個點且
→ love5566188:四個邊有cycle另一為孤立點則 |E|=|V|-1 但不為tree
推 bbhands:加上connected的條件才會對
推 dunkjames:因單獨一個點也能視為為無相圖 所以可以畫出:
→ dunkjames:●一●
→ dunkjames: \ /
→ dunkjames:  ●          ●
→ dunkjames:
→ dunkjames:所以N=4   E=3 可是因為無Connected 所以不是tree 同3f
→ DiLegend:原來如此
→ sneak:  ●          https://daxiv.com