複製鏈接
請複製以下鏈接發送給好友

迴路

(數據結構、圖論中的一個定義)

鎖定
一個圖中,起點和終點相同的路徑稱為迴路。
迴路是數據結構圖論中的定義。
中文名
迴路
外文名
circuit; cycle
別    名
迴環,環路,環

目錄

迴路定義

圖中有3個迴路。 圖中有3個迴路。
一個圖中,起點和終點相同的路徑稱為迴路。

迴路相關定理

邊 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 不是割邊。