競(jìng)賽圖的超生成連通性

張?jiān)葡迹?張　博， 楊衛(wèi)華

(1. 山西省財(cái)政稅務(wù)專科學(xué)校 公共課教學(xué)部， 山西 太原 030024； 2. 太原理工大學(xué) 數(shù)學(xué)學(xué)院， 山西 太原 030024)

0　引　言

本文未明確介紹的術(shù)語(yǔ), 見參考文獻(xiàn)[1-2]. 一個(gè)有向圖D是由頂點(diǎn)集V(D)和弧集A(D)構(gòu)成, 如果xy是D的一條弧, 則稱x控制(指向)y. 如果A和B是頂點(diǎn)集V(D)的子集合且A中的每個(gè)頂點(diǎn)控制(指向)B中的每個(gè)頂點(diǎn), 則稱A控制(指向)B. 在有向圖中, 一條有向路P是一條點(diǎn)序列v1,v2,…,vk, 其中vivi+1是對(duì)所有i=1,2,…,k-1 的弧 (本節(jié)所有的路均指有向路). 頂點(diǎn)v1被稱為路P的起點(diǎn), 頂點(diǎn)vk被稱為路P的終點(diǎn). 路P的長(zhǎng)度等于路中弧的數(shù)目, 即|P|-1. 頂點(diǎn)v2,v3,…,vk-1被稱為路P的內(nèi)部點(diǎn)或中間點(diǎn). 如果兩條路的內(nèi)部頂點(diǎn)不相同， 稱之為內(nèi)部不相交的兩條路. 如果x和y是D的兩個(gè)頂點(diǎn),P是從x到y(tǒng)的一條有向路, 稱P是一條(x,y)-路.如果uv∈A(D)且P是一條長(zhǎng)度為k≥2的(u,v)-路, 則P被稱為弧uv的k-支路(即k-bypass).

競(jìng)賽圖T是任意兩點(diǎn)之間恰有一條弧的有向圖. 競(jìng)賽圖T的一條哈密爾頓路(resp. 圈)是一條包含T中所有頂點(diǎn)的路(resp. 圈). 如果在有向圖D中任意兩個(gè)頂點(diǎn)x和y之間, 有從x到y(tǒng)的哈密爾頓路或者從y到x的哈密爾頓路, 則稱D是弱哈密爾頓連通的; 如果在有向圖D中任意兩個(gè)頂點(diǎn)x和y之間, 都有從x到y(tǒng)的哈密爾頓路和從y到x的哈密爾頓路, 則稱D是強(qiáng)哈密爾頓連通的.

在有向圖D中, 任意兩點(diǎn)x和y之間都存在一條(x,y)-路和一條(y,x)-路， 則稱D是強(qiáng)連通的(或稱為強(qiáng)的). 如果在有向圖D中任意刪除少于k個(gè)頂點(diǎn)的點(diǎn)集后, 有向圖仍是強(qiáng)連通的, 則稱D是k-強(qiáng)連通的(或稱為k-強(qiáng)的). 在圖論中, 連通性是最基本的內(nèi)容之一, 許多重要的理論都與它相關(guān), 其中就有重要的Menger’s定理[3](點(diǎn)連通性)： 有向圖D是k-強(qiáng)連通的(或稱為k-強(qiáng)的)當(dāng)且僅當(dāng)對(duì)于D中任意兩個(gè)頂點(diǎn)x和y, 都有k條內(nèi)部不相交的路從x到y(tǒng)且有k條內(nèi)部不相交的路從y到x.

在無(wú)向圖G中,u和v之間的一個(gè)k-container,C(u,v)是u和v之間k條內(nèi)部不相交的路的集合. 圖中container的概念是由Hsu[4]提出的, 并用于評(píng)估互連網(wǎng)絡(luò)的通信性能. 如果k-container,C(u,v)包含了G中所有的頂點(diǎn), 則稱它是一個(gè)k*-container. 如果G的任意兩個(gè)不同頂點(diǎn)之間存在一個(gè)k*-container, 則圖G是k*-連通的. 由Albert[5]等人提出的全局3*-連通圖是對(duì)k*-連通圖的研究. 顯然, 圖中的生成連通性也是哈密爾頓連通性的推廣.

許多學(xué)者已對(duì)無(wú)向圖的生成連通性進(jìn)行了研究. 例如, Lin[6]等證明了餅圖Pn是w*-連通的當(dāng)且僅當(dāng)n≥3, 其中1≤w≤n-1. Lin[7]等人還給出了圖是r*-連通的充分條件， 他們證明了對(duì)于圖G中任何兩個(gè)不相鄰的頂點(diǎn)u和v, 如果dG(u)+dG(v)≥|V|+k, 則G是r*-連通的， 其中r∈{1,2,…,k+2} (k是正整數(shù)). 文獻(xiàn)[8-9]分別討論了無(wú)向圖的生成連通性和無(wú)向圖的生成扇形連通性. 文獻(xiàn)[10-11]分別討論了線圖的生成連通性和圖的勢(shì)的生成連通性. 文獻(xiàn)[12]討論了排列圖的生成連通性. 文獻(xiàn)[13-15]還討論了生成連通性的一些廣泛性質(zhì).

有關(guān)有向圖的生成連通性方面， Thomassen[16]研究了競(jìng)賽圖的弱哈密爾頓連通性和競(jìng)賽圖的強(qiáng)哈密爾頓連通性. 同時(shí)， 人們已經(jīng)在弱哈密爾頓連通性的基礎(chǔ)上推廣并定義了有向圖的生成連通性. 本文將在強(qiáng)哈密爾頓連通性的基礎(chǔ)上推廣并定義有向圖的超生成連通性.

令D是一個(gè)有向圖,u和v是D中任意兩個(gè)頂點(diǎn). 在有向圖D中,u和v之間的一個(gè)k-container是u和v之間有k條內(nèi)部不相交的路的集合， 如圖 1 所示.

圖 1　u和v之間的k-containerFig.1　k-container between u and v

如果k-container包含D中所有的點(diǎn)， 則它被稱為k*-container. 如果從u到v有k條內(nèi)部不相交的且方向相同的路的集合, 并且它們包含D中所有的頂點(diǎn), 則k-container是從u到v的強(qiáng)k*-container， 如圖 2 所示.

圖 2　從u到v的強(qiáng)k*-containerFig.2　Strong k*-container from u to v

1　預(yù)備知識(shí)

定理1[3]令D是有向圖且x和y分別是D的任意兩個(gè)頂點(diǎn), 則D是k-強(qiáng)連通的(或者稱為k-強(qiáng)的)當(dāng)且僅當(dāng)D既包含k條從x到y(tǒng)的內(nèi)部不相交的路, 同時(shí)也包含k條從y到x的內(nèi)部不相交的路.

引理1[16]令T是競(jìng)賽圖,x和y分別是D的任意兩個(gè)頂點(diǎn). 如果T有三條內(nèi)部不相交且長(zhǎng)度至少為2的(x,y)-路, 則T有一條哈密爾頓(x,y)-路.

引理2[16]如果e是 3-強(qiáng)競(jìng)賽圖T的一條弧, 則e被包含在的哈密爾頓圈中.

Thomassen[16]已經(jīng)證明4-強(qiáng)連通競(jìng)賽圖的每條弧都有一個(gè)哈密爾頓支路 (即: 4-強(qiáng)連通競(jìng)賽圖的任何兩點(diǎn)x,y之間, 都既有一條哈密爾頓路從x到y(tǒng), 又有一條哈密爾頓路從y到x). 根據(jù)該結(jié)果, 可以得到下面的結(jié)論.

引理3[16]4-強(qiáng)的競(jìng)賽圖是超強(qiáng)1*-連通的.

引理44-強(qiáng)的競(jìng)賽圖是超強(qiáng)2*-連通的.

證明令T是4-強(qiáng)連通競(jìng)賽圖,x和y分別是T的任意兩個(gè)頂點(diǎn). 不失一般性, 假設(shè)xy∈A(T), 則根據(jù)引理3, 弧xy有一條哈密爾頓支路, 即x從y到有一個(gè)強(qiáng)的2*-container. 下面只需證明y從x到有一個(gè)強(qiáng)的2*-container.

T-{x,y}的點(diǎn)可以被劃分成4個(gè)集合A,B,C,D, 它們滿足以下條件:

1)x和y都控制集合A中的每個(gè)點(diǎn);

2)x和y都被集合B中的每個(gè)點(diǎn)控制;

3)x控制集合C中的每個(gè)點(diǎn)且集合C中的每個(gè)點(diǎn)控制y;

4)y控制集合D中的每個(gè)點(diǎn)且集合D中的每個(gè)點(diǎn)控制x.

下面考慮兩種情形.

情形1|D|=φ. 由于T是4-強(qiáng)連通競(jìng)賽圖, 根據(jù)定理1, 至少有4條弧從集合A指向集合B且這些弧兩兩不相交. 用u1v1,u2v2,u3v3和u4v4來(lái)表示這4條弧, 其中ui∈A,vi∈B且i∈{1,2,3,4}, 則x和y之間至少有4條長(zhǎng)為3的(y,x)-路. 刪除(y,x) -路中的內(nèi)部頂點(diǎn)u1和v1, 則刪除點(diǎn)后得到的競(jìng)賽圖是2-強(qiáng)連通的且有3條內(nèi)部不相交且長(zhǎng)度為3的(y,x)-路. 根據(jù)引理1, 這個(gè)競(jìng)賽圖有一條哈密爾頓(y,x)-路. 再加上路yu1v1x, 則從y到x有一個(gè)強(qiáng)的2*-container.

情形2|D|≥1. 在T中至少有一條長(zhǎng)為2的(y,x)-路, 刪除(y,x)-路中的內(nèi)部頂點(diǎn), 則得到的競(jìng)賽圖是3-強(qiáng)連通的. 由于x控制(指向)y, 根據(jù)引理2, 這個(gè)競(jìng)賽圖有一條哈密爾頓(y,x)-路. 再加上長(zhǎng)為2的(y,x)-路, 則y從x到有一個(gè)強(qiáng)的2*-container.

因此, 競(jìng)賽圖T從x到y(tǒng)和從y到x都有一個(gè)強(qiáng)的2*-container, 所以,T是超強(qiáng)2*-連通的. 證畢.

2　主要結(jié)果

下面給出本文的主要結(jié)論：

定理2對(duì)于所有的k≥2, 一個(gè)2k-強(qiáng)連通的競(jìng)賽圖是r*-強(qiáng)連通的 (1≤r≤k).

證明當(dāng)k=2時(shí), 根據(jù)引理3和引理4,T是超強(qiáng)1*-連通的和超強(qiáng)2*-連通的. 下面考慮k≥3 的情況. 令T是2k-強(qiáng)連通競(jìng)賽圖,x和y分別是T中任意兩個(gè)頂點(diǎn).T-{x,y} 的點(diǎn)可以被劃分成4個(gè)集合A,B,C,D, 它們滿足以下條件:

1)x和y都控制集合A中的每個(gè)點(diǎn);

2)x和y都被集合B中的每個(gè)點(diǎn)控制;

3)x控制集合C中的每個(gè)點(diǎn)且集合C中的每個(gè)點(diǎn)控制y;

4)y控制集合D中的每個(gè)點(diǎn)且集合D中的每個(gè)點(diǎn)控制x.

假設(shè)min{|C|,|D|}=m， 則T有m條內(nèi)部不相交的長(zhǎng)為2的(x,y)-路和m條內(nèi)部不相交的長(zhǎng)為2的(y,x)-路. 下面考慮兩種情形.

情形30≤m≤k-1. 由于T是2k-強(qiáng)連通競(jìng)賽圖, 根據(jù)定理1, 至少有2k-1-m條弧從集合A指向集合B且這些弧兩兩不相交, 則x和y之間至少有2k-1-m條內(nèi)部不相交的長(zhǎng)為3的(x,y)-路 (也有2k-1-m條內(nèi)部不相交的長(zhǎng)為3的(y,x)-路). 從中選取s(1≤s≤k-2-m)條長(zhǎng)為3的內(nèi)部不相交的(x,y)-路, 令{P1,P2,…,Ps}表示這s條內(nèi)部不相交的長(zhǎng)為3的(x,y)-路, {Q1,Q2,…,Qm}(0≤m≤k-3)表示這m條內(nèi)部不相交的長(zhǎng)為2的(x,y)-路. 刪除(x,y)-路中這2s個(gè)內(nèi)部頂點(diǎn)且刪除C中這m個(gè)內(nèi)部頂點(diǎn), 則得到的競(jìng)賽圖(2k-2s-m)是-強(qiáng)連通的 (它至少是4-強(qiáng)連通的). 根據(jù)引理4, 這個(gè)競(jìng)賽圖是超強(qiáng)2*-連通的. 因此, 從x到y(tǒng)有強(qiáng)的2*-container. 令{R1,R2}表示這兩條內(nèi)部不相交的(x,y)-路, 則{P1,P2,…,Ps,Q1,Q2,…,Qm,R1,R2}構(gòu)成了從x到y(tǒng)的一個(gè)強(qiáng)的(s+m+2)*-container. 因?yàn)?≤s+m+2≤k, 則有從x到y(tǒng)的一個(gè)強(qiáng)的r*-container, 其中r∈{3,4,…,k}. 用相同的方法, 也可以得到y(tǒng)從x到的一個(gè)強(qiáng)的r*-container, 其中r∈{3,4,…,k}.

情形4m≥k-2. 在T中至少有k-2條長(zhǎng)為2的內(nèi)部不相交的(x,y)-路, 也至少有k-2條長(zhǎng)為2的內(nèi)部不相交的(y,x)-路, 從中選取s(1≤s≤k-2)條長(zhǎng)為2的內(nèi)部不相交的(x,y)-路, 令{P1,P2,…,Ps}表示這s條內(nèi)部不相交的長(zhǎng)為2的(x,y)-路. 刪除長(zhǎng)為2的(x,y)-路中的s個(gè)內(nèi)部頂點(diǎn), 得到的競(jìng)賽圖是(2k-s)-強(qiáng)連通的 (它至少是4-強(qiáng)連通的). 根據(jù)引理4, 這個(gè)競(jìng)賽圖是超強(qiáng)2*-連通的. 因此, 從x到y(tǒng)有強(qiáng)的2*-container. 令{R1,R2}表示這兩條內(nèi)部不相交的(x,y)-路, 則{P1,P2,…,Ps,R1,R2}構(gòu)成了從x到y(tǒng)的一個(gè)強(qiáng)的(s+2)*-container. 因?yàn)?≤s+2≤k, 則有從x到y(tǒng)的一個(gè)強(qiáng)的r*-container, 其中r∈{3,4,…,k}. 用相同的方法, 也可以得到從y到x的一個(gè)強(qiáng)的r*-container, 其中r∈{3,4,…,k}.

因此,T有從x到y(tǒng)的一個(gè)強(qiáng)的r*-container和從y到x的一個(gè)強(qiáng)的r*-container, 則T是超強(qiáng)r*-連通的, 其中r∈{1,2,3,4,…,k}. 證畢.

由定理2, 有如下推論:

2018年 第39卷 第4期中 北 大 學(xué) 學(xué) 報(bào)(自然科學(xué)版)Vol.39 No.4 2018(總第180期)JOURNAL OF NORTH UNIVERSITY OF CHINA(NATURAL SCIENCE EDITION)(Sum No.180)