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

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

迴路是數據結構、圖論中的定義。

基本介紹

• 中文名：迴路
• 外文名：circuit; cycle
• 別名：迴環，環路，環

定義

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

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