作者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
1F：推 chenbojyh:第一提好像没提到"连通"耶 09/27 15:10
2F：→ yesa315:喔 想通了 第一题最多一path 也可以没path 所以不连通 09/27 16:22
3F：→ ssccg:第二题也许是没提到simple graph，所以可以有loop 09/27 16:38
4F：→ yesa315:loop算是回路吗? 09/27 17:08
5F：→ ssccg:cycle有一种定义是至少3 edge，所以loop不算cycle 09/27 19:17
6F：→ ssccg:总之没提到simple graph的话都小心一点 09/27 19:17
7F：→ yesa315:嗯嗯 感谢解答 09/27 23:19