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

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

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

3、高階連通性的問(wèn)題。我們給出了兩個(gè)圖的笛卡兒積及字典式的積為max-λ，max-k，supe-λ，super-k及hyper-k的充分條件，同時(shí)證明了其中一些條件也是必要的．此外，對(duì)這兩種積的局部割集和廣義割集的性質(zhì)也進(jìn)行了考慮．對(duì)于兩個(gè)圖的笛卡爾積，我們有以下的主要結(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>滿(mǎn)足下列條件之一，則有G<,1>×G<,2>的每一個(gè)最小廣義割集都是一個(gè)局部割集： (a)G和G是極大連通的，并且δ(G<,1>)≥2和δ(G<,2>)≥2，(b)G<,1>≌K<,2>,2≤δ(G<,2>)≌K<,3>．對(duì)于兩個(gè)圖的字典式積，我們有以下的主要結(jié)果： (1)如果X和Y是極大邊連通的，則X[Y]是上邊連通的． (2)X[Y]是