網(wǎng)絡(luò)圖的兩個可靠性參數(shù).pdf

1、圖的條件連通度是除了點連通度之外的另外一種探索網(wǎng)絡(luò)結(jié)構(gòu)的方法，在研究網(wǎng)絡(luò)圖容錯率中有很多應用。對一個連通圖G=（V,E），點集F(C)V記作G的Rk點割如果G-F不連通且V-F中的每一個點在G-F中至少有k個鄰點。我們用κk(G)表示圖G所有的Rk點割中元素最少的集合的大小。
　　凱萊圖在互聯(lián)網(wǎng)絡(luò)中有很好的屬性，如點對稱性、邊對稱性、層次結(jié)構(gòu)可分解、高容錯度等，因此凱萊圖研究在設(shè)計和分析網(wǎng)絡(luò)方面有很多的應用。令Sym(n)是基于{

2、1，2,…，n}的對稱群，T是Sym(n)中的一個置換集，圖G（T）由點集{1，2,…，n}和邊集{ij:（ij）∈T}構(gòu)成。如果G（T）是輪圖，那么我們簡單地將凱萊圖Cay(Sym(n)，T）記作WGn。
　　圖的廣義連通度是圖的連通度的另一種自然推廣，常被用作衡量網(wǎng)絡(luò)G的穩(wěn)定性。給定圖G=（V，E）和頂點數(shù)大于等于2的頂點集合S(C)V，若i≠j且1≤i，j≤r，則圖G中滿足V(Ti)∩ V(Tj)=S的邊不交的樹T1，T2,

3、…，Tr叫做S斯坦納樹，我們用κG(S)表示圖G中S斯坦納樹數(shù)量的極大值。對于滿足2≤k≤n的正整數(shù)k，圖G的廣義k連通度κk(G)定義為κk(G)=min{κG(S)|S(C)V(G)，|S|=k}，也就是說，κk(G)是κG(S)在取遍G中所有的k元頂點子集S后的最小值。
　　本文，我們探索了由輪圖所生成的凱萊圖（記作WGn）的κ1（WGn）和κ2(WGn)值;探索了凱萊圖冒泡星圖（記作BSn）的廣義3連通度κ3(BSn)值，