內部不相交路徑

內部不相交路徑 (internally disjoint paths) 是圖論中用來描述連線兩個點的具有特殊性質的路徑。它描述的是連線兩個點的不同路徑所包含的點或邊是否有交集的性質。

基本介紹

• 中文名：內部不相交路徑
• 外文名：internally disjoint paths  
• 所屬學科：數學 、理論計算機科學 
• 適用領域：組合數學、圖論 

定義

記連線兩個點的兩條不同的路徑為。

若，則稱這兩條路徑之間是關於點獨立的 (vertex-independent)，又稱這兩條路徑均為連線的內部點不相交路徑 (internally vertex-disjoint u,v-paths)，有時直接簡稱內部不相交路徑 (internally disjoint u,v-paths)。

若，則稱這兩條路徑之間是關於邊獨立的 (edge-independent)，又稱這兩條路徑均為連線的邊不相交路徑 (edge-disjoint u,v-paths)。

在極值圖論領域，常常討論圖中任意兩點的內部點不相交路徑的最大數量，又記為，以及圖中任意兩點的邊不相交路徑的最大數量，又記為。

性質

兩條內部點不相交路徑一定是邊不相交路徑，兩條邊不相交路徑則不一定是內部點不相交路徑。

套用

內部不相交路徑實際上刻畫了圖的連通性，多用於討論圖的點連通性與邊連通性。其2連通性由惠特尼定理給出，更一般的則由門傑定理 (Menger's theorem) 及其邊版本給出，即