圖的笛卡爾積及字典式積的連通性.pdf

1、隨著信息網(wǎng)絡(luò)的飛速發(fā)展，許多與之相關(guān)的理論性問題越來越引起人們的重視，其中之一即為網(wǎng)絡(luò)可靠性。通信網(wǎng)絡(luò)的可靠性分析與高可靠性能網(wǎng)絡(luò)的設(shè)計問題是可靠性研究的核心。圖作為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)最有效模型，圖的各種連通性指標(biāo)被先后用來研究網(wǎng)絡(luò)可靠性問題。通常情況下，網(wǎng)絡(luò)是連通的，從而代表它的圖也是連通的，也就是說，圖中任意兩點間都存在一條路。但是，有時網(wǎng)絡(luò)的某個元素被破壞，也就是其對應(yīng)的圖被去掉一些邊和點時。這時我們希望被破壞的網(wǎng)絡(luò)盡可能的連通。圖的經(jīng)

2、典參數(shù)邊連通度λ(G)是指要使得一個圖不連通所需要去掉的最少的邊數(shù)，點連通度k(G)是指要使得一個圖不連通所需要去掉的最少的點數(shù)。邊連通度和點連通度是衡量網(wǎng)絡(luò)可靠性的一個重要參數(shù)。作為經(jīng)典連通度的推廣，人們提出了高階的連通度，例如極大(邊)連通的，上(邊)連通的，超連通的等。另一方面，笛卡爾積和字典式積是從一些較小的圖來構(gòu)造較大的圖的一種有效的方法，從而在設(shè)計網(wǎng)絡(luò)和分析網(wǎng)絡(luò)方面有著重要的作用。在本文中，主要是研究圖的笛卡爾積和字典式積的

3、高階連通性的問題。我們給出了兩個圖的笛卡兒積及字典式的積為max-λ，max-k，supe-λ，super-k及hyper-k的充分條件，同時證明了其中一些條件也是必要的．此外，對這兩種積的局部割集和廣義割集的性質(zhì)也進(jìn)行了考慮．對于兩個圖的笛卡爾積，我們有以下的主要結(jié)果： (1)如果G<,1>和G<,2>是極大邊連通的，則G<,1>×G<,2>是極大邊連通的。 (2)假設(shè)λ<,i>≥2或λ<,1>=1，2≤λ<,2>

4、-1．如果G<,1>和G<,2>是極大邊連通的，則G<,1>×G<,2>是上邊連通的。 (3)如果G<,1>和G<,2>是極大連通的，則G<,1>×G<,2>是極大連通的。 (4)假設(shè)k<,i>≥2或K<,1>=1，2≤K<,2>×G<,2>是上連通的。 (5)假設(shè)k<,i>≥2或k<,1>=1，2≤K<,2>×G<,2>

5、是超連通的。 (6)若G<,1>，G<,2>滿足下列條件之一，則有G<,1>×G<,2>的每一個最小廣義割集都是一個局部割集： (a)G和G是極大連通的，并且δ(G<,1>)≥2和δ(G<,2>)≥2，(b)G<,1>≌K<,2>,2≤δ(G<,2>)≌K<,3>．對于兩個圖的字典式積，我們有以下的主要結(jié)果： (1)如果X和Y是極大邊連通的，則X[Y]是上邊連通的． (2)X[Y]是