連接的無向非循環圖與樹

Question

雖然我正在用MIT書籍「算法介紹」研究圖論，但我被提到了關於圖和樹的一些定義。

在麻省理工學院的介紹算法的第3版的書，附錄樹章介紹了我定理B.2，

設G =（V，E）是一個無向圖「的自由樹的屬性」。以下聲明是等同的。

1. G是自由樹 ...
2. G是環狀的，且| E | = | V | - 1.

有沒有一個連接的，無向的，非樹的非循環圖的例子？

理論上，如果存在滿足條件的無向非循環圖| E | =！ | V | - 1，這是否會成爲一個例子？

如果有一個例子滿足這個條件，你能告訴我嗎？

Answer 1

任何連接的非循環圖都是一棵樹。樹有幾種不同的等價定義：

• 它們是連接的非循環圖。
• 它們連接的圖形只有一個節點而不是邊緣。
• 他們最小連通圖（他們連接，但是，消除任何邊緣斷開它們）
• 他們最大非循環圖（他們是環狀的，且添加任何缺失的邊創建一個週期）
• 它們是任何兩個節點之間只有一條簡單路徑的圖形。

所以不，你不能找到一個不是樹的連接非循環圖。 :-)