k-連通圖

k-連通圖（k-connected graph），指的是對於連通圖G，其連通度K(G)＞=k。換言之，對於k-連通圖G，不存在大小為k-1的點集S，使得G-S不連通。

因此，任意一個非平凡連通圖都可被稱為1-連通圖。

基本介紹

• 中文名：k-連通圖
• 外文名：k-connected graph
• 別名：k連通圖

相關性質

連通圖的性質

• 定義1：路徑獨立（internally disjoint）

從x到y的兩條路徑P,Q被稱為獨立的若且唯若這兩條路徑除了x，y以外沒有其他的公共點。

• 定理1：圖G是2-連通圖若且唯若對於任意兩點u,v均存在相互獨立的兩條路徑。

證明：(1)充分性，若任意兩點間均存在兩條獨立的路徑，也就意味著刪除一個點不可能將任意兩點u,v分開，即K(G)＞1，即是2-連通圖。

(2)必要性，採用歸納法證明，對任意兩點u,v間的距離d(u,v)進行歸納。

d(u,v)=1時，uv存在一條直接相連的邊，由於邊連通度K'(G)大於連通度K(G)=2，則刪去一條邊不影響G的連通性，即G-uv是連通圖，意味著u,v兩點之間存在一條路徑P，顯然P與uv獨立。

d(u,v)=k＞1時，設u,v間最短的路徑P0，點w是路徑P0上最靠近v的點，即d(u,w)=k-1，根據歸納假設，u,w兩點間存在兩條獨立的路徑P和Q，若v恰好在P或Q上，則我們就找到了兩條獨立路徑；若v不在P或Q上：

對於G-w，顯然是連通的，設u，v之間存在一條路徑R，如果R與P,Q均沒有任何公共點，我們就找到了獨立路徑;假設R與P,Q有一些公共點，設點z是R上最後一個公共點，則我們就找到了兩條獨立路徑：u---z---v和uQwv。證畢。

定理1證明圖

完全圖的連通度

記K_n為n個點的完全圖，則K(K_n)=n-1。