點割集、邊割集、割點、橋、連通度、雙連通分支.doc

《點割集、邊割集、割點、橋、連通度、雙連通分支.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、對于一個無向圖G：定義一：刪除一個點v是指刪除點v以及所有與點v關(guān)聯(lián)的邊。定義二：刪除一條邊e是指刪除這條邊，但是保留e的兩個頂點。點割集：V是一些頂點的集合，如果刪除V中的所有頂點之后，G不在連通，但是對于V的任何真子集V1，刪除V1后G仍然連通，則稱V是點割集。割點：如果點割集里只有一個頂點，那么這個頂點叫做割點。點連通度：最小的點割集的大小。邊割集：E是一些邊的集合，如果刪除E里的所有邊之后G不在連通，但是對于E的任何真子集E1,刪除E1之后G仍然連通，則稱E是邊割集。橋：如果邊割集里只有一條邊，該

2、邊稱為橋。邊連通度：最小的邊割集的大小。雙連通：如果一個圖沒有割點，那么這個圖稱為2-連通的，或者雙連通的。一個圖的極大雙連通子圖稱為雙連通分量。注意是極大而不是最大，即意味雙連通子圖不一定只有一個。