關于l-路和圖的超歐拉性

李曉璞，劉 娟

(新疆師范大學 數學科學學院，烏魯木齊 830017)

0 引 言

本文只考慮無向圖中沒有自環和重邊的簡單圖，除非特別說明，其他未給出的術語和定義可以參考文獻[1]和[2]。令圖G=VG,EG其中圖的點集為VG,圖的邊集為EG。在這篇文章中，我們用符號xy表示圖G中連接點x和點y的一條邊。符號a,b表示從a到b之間的所有整數。圖G中的道是一個交替序列W=v0e1v1e2…vl-1elvl，對于每一個i∈0,l,其中vi為點，ei為邊使得ei=vivi+1。如果v0=vl，則稱W是一個閉道，否則是開道。當W的邊在上下文中已知時，可以記W為v0v1…vl。如果v0≠vl，則v0和vl是W的兩個端點，道的長度是道中所含邊的條數。圖G中的一個跡是一個所有邊都不同的道。一個路是一個所有點都不同的道。路的長度是路中所含邊的條數，長度為l的路叫做l-路，它包含l+1個點。如果W中v0v1…vl是不同的點，l≥2，并且v0=vl，則稱W是一個圈。如果對于圖G中每對不同的點x，y都存在連接x和y的路，則稱G是連通圖。令G1和G2是兩個圖，如果VG1∩VG2=?,則稱G1和G2是點不交的圖。如果EG1∩EG2=?,則稱G1和G2是邊不交的圖。如果VH?VG,EH?EG并且EH中的每一條邊的兩個端點都在VH中，則稱H是G的一個子圖。如果VH=VG，則稱H是G的一個生成子圖。對于G中任意一個點v，用G-v表示從圖G中刪去點v及其所關聯的邊所得到的G的子圖，稱為G的點刪除子圖。對于G中任意一條邊e，用G-e表示從圖G中刪去邊e所得到的G的子圖，稱為G的邊刪除子圖。如果一個圖G包含一條閉跡使得EW=EG,則稱G是歐拉圖。如果一個圖G包含一條閉跡使得VW=VG,或包含一個生成歐拉子圖，則稱G是超歐拉圖。

定義1 在圖G中，如果對于每一個點v∈VG，滿足點刪除子圖G-v是超歐拉圖，那么G稱為D-超歐拉圖。

定義2 在超歐拉圖G中，如果對于每一個點v∈VG，滿足點刪除子圖G-v是超歐拉圖，那么G稱為T-超歐拉圖。

Boesch,Suffel和Tindell[3]在1977年提出了超歐拉問題，他們致力于刻畫出包含生成歐拉子圖的無向圖，與此同時，他們表示這個問題是極其困難的。Pulleyblank[4]在1979年證明了判定一個無向圖(甚至包含平面無向圖)是否是超歐拉的是NP-完全的。Catlin[5]在1988年提出了超歐拉圖的約化方法，是研究此類問題的重要工具。關于超歐拉問題的研究方法，研究進展及其應用，參見文獻[6-9]。

在文獻[10]中，我們知道兩個超歐拉有向圖的2-和不一定是超歐拉有向圖。在文獻[11]中，介紹了有向圖中l-路和的概念，并且給出了一些兩個有向圖的l-路和是超歐拉圖的充分條件。由這些結論，自然而然地想到了在無向圖中有關超歐拉圖的2-和與l-路和問題。在本文中，我們將介紹兩個無向圖的2-和與l-路和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些充分條件。

1 主要結論

首先，我們討論兩個無向圖的l-路和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些充分條件。

定理1 設G1和G2是兩個點不交的超歐拉圖。在G1⊕l+1G2中，如果Gi有一個生成歐拉子圖Sii=1,2，使得ES1∩ES2=?。那么G1⊕l+1G2是超歐拉圖。

定理2 設G1和G2是兩個點不交的D-超歐拉圖。對于任意的點vi∈VGi，在G1⊕l+1G2中，如果Gi-vi有一個生成歐拉子圖SGi-vii=1,2，使得ESG1-v1∩ESG2-v2=?。那么G1⊕l+1G2是D-超歐拉圖。

情形1v=vj，?j∈0,l

如果v=vj，由D-超歐拉圖的定義，可知G1-vj是超歐拉圖，所以G1-vj有一個生成歐拉子圖，記作SG1-vj；同樣的，G2-vj是超歐拉圖，所以G2-vj有一個生成歐拉子圖，記作SG2-vj，并且ESG1-vj∩ESG2-vj=?，那么SG1-vj∪SG2-vj是G1⊕l+1G2-vj的一個生成歐拉子圖。即G1⊕l+1G2是D-超歐拉圖。

情形2v∈VG1⊕l+1G2vj,?j∈0,l

如果v∈VG1vj，由D-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個生成歐拉子圖，記作SG1-v；同樣的，G2-v0是超歐拉圖，所以G2-v0有一個生成歐拉子圖，記作SG2-v0，并且ESG1-v∩ESG2-v0=?，那么SG1-v∪SG2-v0是G1⊕l+1G2-v的一個生成歐拉子圖。如果v∈VG2vj,由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個生成歐拉子圖，記作SG2-v；同樣的，G1-v0是超歐拉圖，所以G1-v0有一個生成歐拉子圖，記作SG1-v0，并且ESG2-v∩ESG1-v0=?，那么SG2-v∪SG1-v0是G1⊕l+1G2-v的一個生成歐拉子圖。即G1⊕l+1G2是D-超歐拉圖。

定理3 設G1和G2是兩個點不交的圖。G1是一個T-超歐拉圖，G2是一個D-超歐拉圖。在G1⊕l+1G2中，如果G1有一個生成歐拉子圖SG1，對于任意點v2∈VG2，G2-v2有一個生成歐拉子圖SG2-v2，使得ESG1∩ESG2-v2=?。那么G1⊕l+1G2是T-超歐拉圖。

由T-超歐拉的定義，可知G1是超歐拉圖，所以G1有一個生成歐拉子圖，記作SG1。由D-超歐拉的定義，可知G2-v0是超歐拉圖，所以G2-v0有一個生成歐拉子圖，記作SG2-v0。并且ESG1∩ESG2-v0=?，所以SG1∪SG2-v0是G1⊕l+1G2的一個生成歐拉子圖，即G1⊕l+1G2是超歐拉圖。

對于任意點v∈VG1⊕l+1G2，需證明任意點刪除子圖G1⊕l+1G2-v是超歐拉圖，我們分以下兩種情形討論：

情形1v=vj，?j∈0,l

如果v=vj，由T-超歐拉圖的定義，可知G1-vj是超歐拉圖，所以G1-vj有一個生成歐拉子圖，記作SG1-vj；由D-超歐拉圖的定義，可知G2-vj是超歐拉圖，所以G2-vj有一個生成歐拉子圖，記作SG2-vj，并且ESG1-vj∩ESG2-vj=?，那么SG1-vj∪SG2-vj是G1⊕l+1G2-vj的一個生成歐拉子圖。即G1⊕l+1G2是T-超歐拉圖。

情形2v∈VG1⊕l+1G2vj，?j∈0,l

如果v∈VG1vj，由T-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個生成歐拉子圖，記作SG1-v；由D-超歐拉圖的定義，可知G2-v0是超歐拉圖，所以G2-v0有一個生成歐拉子圖，記作SG2-v0，并且ESG1-v∩ESG2-v0=?，那么SG1-v∪SG2-v0是G1⊕l+1G2-v的一個生成歐拉子圖。如果v∈VG2vj，由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個生成歐拉子圖，記作SG2-v；由T-超歐拉圖的定義，可知G1是超歐拉圖，所以G1有一個生成歐拉子圖，記作SG1，并且ESG1∩ESG2-v=?，那么SG1∪SG2-v是G1⊕l+1G2-v的一個生成歐拉子圖。即G1⊕l+1G2是T-超歐拉圖。

以上我們討論了兩個無向圖的l-路和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些充分條件。

特別的，以下我們將討論兩個無向圖的2-和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些更優的充分條件。

定理4 設G1和G2是兩個點不交的超歐拉圖，那么G1⊕2G2是超歐拉圖。

證明因為G1和G2是超歐拉圖，即Gi有一個生成歐拉子圖Sii=1,2。由G1⊕2G2的定義可知，如果ES1∩ES2≠?,令ES1∩ES2=e，那么S1∪S2-e是G1⊕2G2的一個生成歐拉子圖；如果ES1∩ES2=?，那么S1∪S2是G1⊕2G2的一個生成歐拉子圖，即G1⊕2G2是超歐拉圖。

定理5 設G1和G2是兩個點不交的D-超歐拉圖，那么G1⊕2G2是D-超歐拉圖。

證明設e1=v11v12∈EG1和e2=v21v22∈EG2是兩條不相交的邊。由G1⊕2G2的定義，令v11=v21=v1，v12=v22=v2。對于任意點v∈VG1⊕2G2，需證明任意點刪除子圖G1⊕2G2-v是超歐拉圖，我們分以下兩種情形討論：

情形1v=v1或v=v2

如果v=v1，由D-超歐拉圖的定義，可知G1-v1是超歐拉圖，所以G1-v1有一個生成歐拉子圖，記作SG1-v1；同樣的，G2-v1是超歐拉圖，所以G2-v1有一個生成歐拉子圖，記作SG2-v1，那么SG1-v1∪SG2-v1是G1⊕2G2-v1的一個生成歐拉子圖。如果v=v2，由D-超歐拉圖的定義，可知G1-v2是超歐拉圖，所以G1-v2有一個生成歐拉子圖，記作SG1-v2；同樣的，G2-v2是超歐拉圖，所以G2-v2有一個生成歐拉子圖，記作SG2-v2，那么SG1-v2∪SG2-v2是G1⊕2G2-v2的一個生成歐拉子圖。即G1⊕2G2是D-超歐拉圖。

情形2v∈VG1⊕2G2v1,v2

如果v∈VG1v1,v2，由D-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個生成歐拉子圖，記作SG1-v；同樣的，G2-v1是超歐拉圖，所以G2-v1有一個生成歐拉子圖，記作SG2-v1，那么SG1-v∪SG2-v1是G1⊕2G2-v的一個生成歐拉子圖。如果v∈VG2v1,v2，由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個生成歐拉子圖，記作SG2-v；同樣的，G1-v1是超歐拉圖，所以G1-v1有一個生成歐拉子圖，記作SG1-v1，那么SG2-v∪SG1-v1是G1⊕2G2-v的一個生成歐拉子圖。即G1⊕2G2是D-超歐拉圖。

定理6 設G1和G2是兩個點不交的圖。G1是一個T-超歐拉圖，G2是一個D-超歐拉圖。那么G1⊕2G2是T-超歐拉圖。

證明設e1=v11v12∈EG1和e2=v21v22∈EG2是兩條不相交的邊。由G1⊕2G2的定義，令v11=v21=v1，v12=v22=v2。

由T-超歐拉的定義，可知G1是超歐拉圖，所以G1有一個生成歐拉子圖，記作SG1。由D-超歐拉的定義，可知G2-v1是超歐拉圖，所以G2-v1有一個生成歐拉子圖，記作SG2-v1，所以SG1∪SG2-v1是G1⊕2G2的一個生成歐拉子圖，即G1⊕2G2是超歐拉圖。

對于任意點v∈VG1⊕2G2，需證明任意點刪除子圖G1⊕2G2-v是超歐拉圖，我們分以下兩種情形討論：

情形1v=v1或v=v2

如果v=v1，由T-超歐拉圖的定義，可知G1-v1是超歐拉圖，所以G1-v1有一個生成歐拉子圖，記作SG1-v1；由D-超歐拉圖的定義，可知G2-v1是超歐拉圖，所以G2-v1有一個生成歐拉子圖，記作SG2-v1，那么SG1-v1∪SG2-v1是G1⊕2G2-v1的一個生成歐拉子圖。如果v=v2，由T-超歐拉圖的定義，可知G1-v2是超歐拉圖，所以G1-v2有一個生成歐拉子圖，記作SG1-v2；由D-超歐拉圖的定義，可知G2-v2是超歐拉圖，所以G2-v2有一個生成歐拉子圖，記作SG2-v2，那么SG1-v2∪SG2-v2是G1⊕2G2-v2的一個生成歐拉子圖。即G1⊕2G2是T-超歐拉圖。

情形2v∈VG1⊕2G2v1,v2

如果v∈VG1v1,v2，由T-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個生成歐拉子圖，記作SG1-v；由D-超歐拉圖的定義，可知G2-v1是超歐拉圖，所以G2-v1有一個生成歐拉子圖，記作SG2-v1，那么SG1-v∪SG2-v1是G1⊕2G2-v的一個生成歐拉子圖。如果v∈VG2v1,v2，由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個生成歐拉子圖，記作SG2-v；由T-超歐拉圖的定義，可知G1是超歐拉圖，所以G1有一個生成歐拉子圖，記作SG1，那么SG2-v∪SG1是G1⊕2G2-v的一個生成歐拉子圖。即G1⊕2G2是T-超歐拉圖。

2 總 結

超歐拉問題的研究是一個比較新的研究領域，具有很廣闊的研究前景。本文類比出了無向圖中l-路和及2-和的概念，并且給出了在無向圖中D-超歐拉圖和T-超歐拉圖的定義，通過進行運算及討論探究得到了一系列關于超歐拉的充分條件。本文是從無向圖的角度，探究關于超歐拉圖的l-路和及2-和運算之后的結論。我們還可以從有向圖的角度可慮這個問題，看看在有向圖的條件下，是否可以探究出關于超歐拉有向圖的一些結論。也可以考慮在無向、有向的條件下，對于D-超歐拉圖和T-超歐拉圖進行其它的運算，能否得到一些結論，這些都是值得我們繼續討論和探究的問題。