-
迴路
(數據結構、圖論中的一個定義)
鎖定
- 中文名
- 迴路
- 外文名
- circuit; cycle
- 別 名
- 迴環,環路,環
迴路定義
迴路相關定理
邊 e 不落在迴路上
邊 e 是一條割邊
證明:
(1)邊 e 不落在迴路上
邊 e 是一條割邊
證其逆否命題:邊 e 不是一條割邊
邊 e 落在迴路上
假設 e 的兩端點為 x 和 y,因為 e 不是一條割邊,所以刪去 e 後圖仍連通,因此 x 與 y 之間存在一條路徑,這條路徑兩端點為 x 和 y,它和原圖中邊 e 構成迴路,因此 e 落在迴路上。
(2)邊 e 是一條割邊
邊 e 不落在迴路上
證其逆否命題:邊 e 落在迴路上
邊 e 不是一條割邊
假設e的兩端點為 x 和 y,e 落在迴路 C 上,則若從圖中刪去 e ,則 x 與 y 之間存在路徑 C-e,原圖連通性不受影響,因此 e 不是割邊。