什麼是非循環連通無向圖？

Question

我正在經歷最小生成樹的演講，它說我們應該在無向圖中找到連接的非循環子圖。

我的問題是，一個連通的無向圖是怎樣成爲一個無環的，因爲它是連通的，你可以移動到任何頂點的頂點。

誰能告訴我我做錯了什麼？

Answer 1

這實際上只是一個定義問題。見http://en.wikipedia.org/wiki/Cycle_(graph_theory)。文章中稱爲封閉式步行：從頂點到其自身的任何路徑。正如你自己所說，使用該定義，任何連接的無向圖都包含循環。但是，如果您要求從第二個到最後一個頂點的子路徑是簡單路徑（因此簡單週期），即不包含重複頂點的子路徑，則最終會生成許多實際上非循環的連接無向圖，例如樹例如。顯然，路徑還必須包含至少3條邊，否則任何(A,B,A)都將是一個循環。

考慮以下的曲線圖

 A   A 
1)/\ 2)/\ 
    B C  B - C 

2)僅包含簡單週期，因此1)是無環的。