強乘積圖的Euler性

陰浩然李峰

(1.青海師范大學計算機學院,青海 西寧 810008;2.青海省藏文信息處理與機器翻譯重點實驗室,青海 西寧 810008;3.藏文信息處理教育部重點實驗室,青海 西寧 810008)

1 引言

圖G=(V(G),E(G)),其中V(G)是G的非空頂點集,E(G)?V(G)×V(G)是G的邊集.|V(G)|是圖G中的頂點數目,稱為圖G的階.對于任意頂點x∈V(G),記圖G中所有與x相鄰的頂點的集合為NG(x),dG(x)=|NG(x)|表示x在G中的度數.本文所考慮的圖都是簡單連通無向圖,未說明的記號和術語可參見文獻[1].

圖G的一條途徑是指一個頂點和邊交替組成的有限非空序列

使得邊ei的端點為vi?1和vi,i=1,2,···,k.其中頂點v0和vk分別稱為途徑R的起點和終點,而v1,v2,···,vk?1稱為R的內部頂點.如果途徑R中的邊e1,e2,···,ek互不相同,那么R稱為跡.經過圖G中每條邊的跡稱為G的Euler跡.起點和終點不同的Euler跡稱為Euler通路.起點和終點相同的Euler跡稱為Euler環游,即Euler環游是閉的 Euler跡.如果一個圖包含 Euler環游,那么這個圖稱為 Euler圖.因為簡單圖中的任意兩頂點之間至多有一條邊,所以途徑v0e1v1e2···vkek由它的頂點序列v0v1···vk所確定,因此簡單圖的途徑可用其頂點序列來表示.

強乘積圖的概念是文獻[2]首先提出的.兩個無向圖

的強乘積是一個無向圖,記為G1?G2.它的頂點集為

任意兩個不同的頂點 (x1,y1)和 (x2,y2)(其中x1,x2∈V(G1),y1,y2∈V(G2))相鄰當且僅當x1=x2且 (y1,y2)∈E(G2),或者y1=y2且 (x1,x2)∈E(G1),或者(x1,x2)∈E(G1)且(y1,y2)∈E(G2).圖G1和G2稱為強乘積圖G1G2的因子.由強乘積構造出來的大圖包含乘積因子圖作為它的子圖,并且保留了因子圖的許多好性質,比如,連通性、點可遷性、可嵌入性等(見文獻[3-5]).更多關于強乘積的知識可見文獻[2-7].

瑞士數學家Euler于1736年發表了一篇論文“哥尼斯堡的七座橋”,不僅解決了著名的“七橋問題”,更開創了數學的一個新分支—圖論.關于一個圖的Euler環游存在性、求解和計數問題引起了許多作者的興趣.1999年,文獻[8]研究了完全圖K2m的 Euler環游構造問題,并且給出了一個求解該類圖Euler環游的算法.2010年,文獻[9]研究了二部圖的Euler環游問題,并對該類圖的Euler環游數目和性質進行了刻畫.更多關于Euler圖的知識可見文獻[10-11].

本文主要是研究強乘積圖中Euler環游和Euler通路的存在性問題.因為強乘積圖G1G2是由乘積因子圖G1和G2構造出來的,所以因子圖G1和G2的拓撲結構必然會影響著強乘積圖G1G2的拓撲結構.研究強乘積圖的Euler跡問題時,也就是研究乘積因子圖的拓撲結構對強乘積圖Euler跡存在性的影響.據此,本文給出了強乘積圖含有Euler環游和Euler通路的一個充分必要條件。

2 主要定理及證明

定理 2.1設G1和G2是兩個非平凡的連通圖.強乘積圖G1G2是Euler圖當且僅當G1和G2中的每個頂點的度數是偶數.

證明設G1和G2中的每個頂點的度數是偶數.由于G1和G2都是非平凡的連通圖,根據強乘積的定義,易知強乘積圖G1G2也是非平凡的連通圖.設T是G1G2的所有跡中最長的一條,并且記為以下形式

可以斷言

如若不然,跡T終止于(xm,yn)(xu,yv).根據跡的定義,跡T的終點(xm,yn)可能作為T的內部頂點出現過多次,并且每出現一次都會關聯強乘積圖G1G2的兩條邊.又因為跡T終止于頂點(xm,yn),所以可以得到頂點(xm,yn)與奇數條邊相關聯.由于頂點xm∈V(G1)和yn∈V(G2)的度數為偶數,根據強乘積圖的定義有

因此頂點(xm,yn)的度數為偶數.更一般地,可以得到強乘積圖G1G2中任意頂點的度數是偶數.由此可知頂點(xm,yn)至少還關聯一條不在跡T中的邊,假設這條邊為((xm,yn),(xm+1,yn+1)).此時,可以得到一條比T更長的跡T+(xm+1,yn+1),這矛盾于T是最長跡.因此強乘積圖G1G2的最長跡T是一條起點和終點相同的跡,即閉跡.設C=T并且記為

C是G1G2的最長跡且是閉跡.如果C包含強乘積圖G1G2的所有邊,那么C是G1G2的一個 Euler環游,即強乘積圖G1G2是 Euler圖.否則,假設C未包含G1G2所有的邊.因為G1G2是連通的,所以一定存在著某條不在C中的邊e=((xb,yd),(xi,yj))與C上的頂點(xb,yd)相關聯.設H=G1G2?E(C),即圖H是由強乘積圖G1G2刪去C中的邊而得到的.取H中包含邊e的連通分支H1,H1是非平凡且連通的.因為閉跡C中的每個頂點關聯G1G2的偶數條邊,所以圖H中的每個頂點度也關聯著偶數條邊,對于連通分支H1亦是如此.現考慮H1中起始于頂點(xb,yd)的一條最長跡.利用上述相似方法,可知這條最長跡必須終止于起點 (xb,yd),記這條閉跡為C′.據此,在閉跡C到達頂點(xb,yd)時,把C′粘到C上,可以得到一個比C更長的閉跡,這導致矛盾.因此,C包含了強乘積圖G1G2所有的邊,從而C是G1G2的一個Euler環游,即強乘積圖G1G2是Euler圖.

反之,設強乘積圖G1G2是Euler圖,C′是G1G2的一個Euler環游,記為

頂點 (xb,yd)是 Euler環游C′的內部頂點 (可能存在 (xb,yd)=(xu,yv)).根據 Euler環游的定義,易知(xb,yd)作為C′的內部頂點每出現一次,就會有強乘積圖G1G2中兩條邊與之關聯.因為Euler環游C′包含了G1G2中所有的邊,所以對于強乘積圖中的頂點 (xb,yd)(xu,yv),有偶數條邊與之相關聯.又因為Euler環游C′是起始并且終止于頂點(xu,yv)的,所以與頂點(xu,yv)相關聯的邊的條數也為偶數.綜合上面的討論,對于強乘積圖G1G2中的任意頂點(xi,yj),與它相關聯的邊的條數為偶數,即G1G2中的任意頂點(xi,yj)的度數是偶數.又因為

因而可以得到G1的任意頂點xi的度數為偶數且G2的任意頂點yj的度數也為偶數,即G1和G2中的每個頂點的度數是偶數.

定理 2.2設G1和G2是兩個連通圖.

(1)如果G1中每個頂點的度數都是偶數且G2恰有兩個度數為奇數的頂點,那么在強乘積圖G1G2中存在k=|V(G1)|條邊不交的跡T1,T2,···,Tk,使得

(2)如果G2中每個頂點的度數都是偶數且G1恰有兩個度數為奇數的頂點,那么在強乘積圖G1G2中存在k=|V(G2)|條邊不交的跡T1,T2,···,Tk,使得

證明僅證明(1),(2)可類似證明.設圖G1的每個頂點的度數都是偶數且G2恰有兩個度數為奇數的頂點.由于圖G1和G2都是連通圖,根據強乘積定義,易知強乘積圖G1G2是連通且非平凡的.令k=|V(G1)|,設G1的頂點為x1,x2,···,xk,G2的兩個度數為奇數的頂點為y1和y2.對于強乘積圖G1G2的任意頂點(x,y),其中x∈V(G1),y∈V(G2),根據強乘積的定義可知

據此,在強乘積圖G1G2中有且僅有如下2k個度數為奇數的頂點:

在G1G2中添加連接頂點 (xi,y1)和 (xi,y2)的新邊ei(i=1,2,···,k),所得到新的連通圖記為 (G1G2)?,即

設T是圖(G1G2)?中最長的跡,記為

可以斷言(xu,yv)=(xm,yn).若不然,跡T終止于(xm,yn)(xu,yv).根據強乘積的定義,頂點(xm,yn)可能作為T的內部頂點已經在終點前出現過,并且每出現一次都有(G1G2)?中的兩條邊與之關聯.又因為T終止于頂點(xm,yn),所以就有奇數條邊與頂點(xm,yn)關聯.根據(G1G2)?的構造方法,可知(G1G2)?中每個頂點的度數都是偶數.由此可知頂點(xm,yn)至少還關聯著一條不在T中的邊,設該邊為e′,那么可以得到 (G1G2)?的一條跡T+e′,這矛盾于T是最長跡.因此圖 (G1G2)?的最長跡T是一條閉跡.這里將證明:圖(G1G2)?的最長閉跡T包含其所有的邊,即T是 (G1G2)?的一個 Euler環游.假設不然,T未包含圖(G1G2)?的所有的邊.因為 (G1G2)?是連通的,所以對于T中的某頂點 (xb,yd),一定存在著一條不在T中的邊e′與它關聯.設H=(G1G2)??E(T),取圖H中包含邊e′的連通分支H1,H1是非平凡且連通的.因為閉跡T中的每個頂點關聯(G1G2)?的偶數條邊,所以圖H的每個頂點的度數為偶數,也說明了連通分支H1的每個頂點度為偶數.現考慮H1中起始于頂點(xb,yd)的一條最長跡,根據上述討論,這條最長跡必須終止于頂點 (xb,yd),記這條閉跡為T′.此時,在跡T到達頂點 (xb,yd)時,把T′粘到T上,從而可獲得(G1G2)?中一個比T更長的跡,這導致矛盾.故圖(G1G2)?的最長閉跡T包含其所有的邊,即T是(G1G2)?的一個Euler環游.接下來,從T中刪除連接 (xi,y1)和 (xi,y2)的邊ei(i=1,2,···,k),即T?e1?e2?···?ek,可以得到強乘積圖G1G2中k=|V(G1)|條邊不交的跡T1,T2,···,Tk,使得

本定理得證.

定理 2.3設G1和G2是兩個連通圖.強乘積圖G1G2含有一條Euler通路當且僅當G1和G2之一是平凡圖,而另一個恰有兩個度數為奇數的頂點.

證明設圖G1和G2之一是平凡圖,而另一個恰有兩個度數為奇數的頂點,根據定理2.2,可知強乘積圖G1G2含有一條Euler通路.

反之,設強乘積圖G1G2的Euler通路為L,記為

頂點(xb,yd)作為L的內部頂點每出現一次,就會有G1G2中的兩條邊與之關聯.因為Euler通路L包含了強乘積圖G1G2中所有的邊,所以對于所有不同于起點和終點的內部頂點,它們的度數為偶數.又因為L起始于頂點 (xu,yv)且終止于頂點(xm,yn),所以起點(xu,yv)和終點(xm,yn)的度數為奇數.根據強乘積的定義,有

因為(xu,yv)的度數為奇數,所以xu和yv中至少有一個頂點度數為奇數.不妨設頂點xu的度數為奇數,那么頂點(xu,yn)的度數也為奇數.因為強乘積圖G1G2僅有起點(xu,yv)和終點(xm,yn)的度數為奇數并且它們是不同的頂點,所以可以得到下面兩種情況:(1)yn=yv且xuxm;(2)xu=xm且ynyv.由于無向圖中度數為奇數的頂點有偶數個,若xu=xm,則在Euler通路L中必然存在著不同于起點和終點且度數為奇數的頂點,導致矛盾.因此可以得到只有(1)成立,即yn=yv且xuxm.對于L中不同于起點和終點的任意內部頂點(xb,yd),可以斷言yd=yn=yv和頂點xb的度數為偶數.如若不然,(xu,yb)和(xm,yb)或者(xb,yd)為L中不同于起點和終點且度數為奇數的內部頂點,導致矛盾.綜上可以得到,G2是平凡圖且G1恰有兩個度數為奇數的頂點.同理,不妨設頂點yn的度數為奇數.利用上述相似方法,可以得到G1是平凡圖且G2恰有兩個度數為奇數的頂點.

3 結論

強乘積是通過若干特定的階數較小的圖來構造大圖的有效方法,也是一種設計大規模互連網絡的重要方法.本文研究強乘積圖的Euler跡問題,給出了強乘積圖是Euler圖的充分必要條件和強乘積圖含有Euler通路的充分必要條件.