橋(數學概念)

在圖這種數據結構中，設無向圖G=<V,E>,若存在E'⊆E使得p(G-E')>p(G),且對於任意的E''⊂E',均有p(G-E'')=p(G),則稱E'是G的邊割集，或簡稱為割集。若E'={e}，則稱e為割邊或橋。

基本介紹

• 中文名：橋
• 類型：數學概念
• 學科：數學
• 定義：若E'={e}，則稱e為割邊或橋

離散數學定義

在圖這種數據結構中，設無向圖G=<V,E>,若存在E'⊆E使得p(G-E')>p(G),且對於任意的E''⊂E',均有p(G-E'')=p(G),則稱E'是G的邊割集，或簡稱為割集。若E'={e}，則稱e為割邊或橋。

其中P(G)表示圖G的連通分支數