圖的連通度和分離度的研究.pdf

1、量化一個(gè)圖或網(wǎng)絡(luò)的脆弱程度，始于圖的連通性研究和Menger，Whitney等人的理論，他們提出很多衡量圖或網(wǎng)絡(luò)脆弱性的參數(shù)。與連通度和邊連通度不同，這些參數(shù)不僅考慮了破壞網(wǎng)絡(luò)的難易程度，還考慮了網(wǎng)絡(luò)遭受破壞的程度，在整體上能刻畫網(wǎng)絡(luò)與圖的連通性，但也在不同程度上存在不足，使得提出更為細(xì)致的參數(shù)成為必要。 本文在前人工作的基礎(chǔ)上，主要研究一個(gè)新的衡量圖或網(wǎng)絡(luò)的脆弱性的參數(shù)—圖的分離度(separativity)。1988年Jia

2、 Xiao_feng提出一個(gè)相當(dāng)廣泛的圖類—處處h-可斷圖，其中出現(xiàn)了分離集的概念，以此為背景提出了圖的分離度的概念。這里S是G的割集，ω(G-S)是圖G-S的連通分支數(shù)，m(G-S)是圖G-S的最大連通分支的階數(shù)。這里S是G的邊割集，ω(G-S)是圖G-S的連通分支數(shù)，m(G-S)是圖G-S的最大連通分支的階數(shù)。主要內(nèi)容為： 第一部分，介紹了圖的連通度和分離度的研究現(xiàn)狀及進(jìn)展，指出本文的選題背景及意義。 第二部分，主要