(長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023) (湖北省洪湖市第一高級中學(xué)，湖北 洪湖 433200)

筆者討論的圖均為沒有重邊的簡單圖。對圖G，用|V(G)|和|E(G)|分別表示圖G的頂點(diǎn)數(shù)和邊數(shù)。一條從x0到xk的路徑P表示為P=x0x1…xk，其中Pxi=x0…xi,xiP=xi…xk。用Pk表示圖中包含k個頂點(diǎn)的路徑，其長度為k-1。如果圖G的邊集E(G)可以分解為若干邊不重合的子圖H時，就稱G有H分解，若H={P1,P2,…,Pk}，則稱圖G有路分解，令p(G)=min{||:是G的一個路分解}，即圖G的路分解的最小條數(shù)，設(shè)是G的一個路分解，若||=p(G)，則稱是圖G的一個最小路分解。設(shè)v是圖G的一個點(diǎn)，dG(v)表示圖G中與點(diǎn)v相關(guān)聯(lián)的邊的條數(shù)，稱為點(diǎn)v的度。一個連通且沒有圈的圖稱為樹，通常用字母T來表示樹。其中僅有一個點(diǎn)構(gòu)成的樹稱為平凡樹，否則稱為非平凡樹。樹T中度為1的點(diǎn)稱為懸掛點(diǎn)(葉子)，通常用L(T)表示樹T中葉子的集合，與它相關(guān)聯(lián)的邊稱為懸掛邊。設(shè)x是任意的實(shí)數(shù)，[x]表示不超過x的最大整數(shù)，┌x┐表示不小于x的最小整數(shù)。所涉及的相關(guān)符號見參考文獻(xiàn)[1] 。

1 相關(guān)引理

圖1 dT(v)為偶數(shù) 圖2 dT(v)為奇數(shù)

引理2設(shè)是樹T的一個最小路分解，?v∈V(T)。若dT(v)為偶數(shù)，則在中不存在以點(diǎn)v為端點(diǎn)的路徑；若dT(v)為奇數(shù)，則在中必存在以點(diǎn)v為端點(diǎn)的路徑。

另一方面，當(dāng)dT(v)為奇數(shù)時，假設(shè)中不存在以v為端點(diǎn)的路徑，那么過v點(diǎn)的每條路都會經(jīng)過與v相關(guān)聯(lián)的2條邊，從而與v相關(guān)聯(lián)的邊數(shù)為偶數(shù)，這與dT(v)為奇數(shù)相矛盾。

引理3設(shè)T是一個樹，且T′=T-{u}，其中u∈L(T)，則有p(T)≥p(T′)。

p(T′)≤t-1=p(T)-1

p(T′)≤t=p(T)

綜上所述p(T)≥p(T′)。

2 主要結(jié)論

證明T是非平凡的，故|T|≥2。用數(shù)學(xué)歸納法證明。

當(dāng)|T|=k時，不妨取u∈L(T)，點(diǎn)u在T中的鄰點(diǎn)記為v。令T′=T-{u}，則有|T′|=|T|-|{u}|=k-1

1)當(dāng)dT′(v)為奇數(shù)時，由引理2，在T′的最小路分解中，必有一條路P∈是以v為端點(diǎn)，此時構(gòu)造一條路徑P′使得P′=P+vu，則′=-P+P′是T的路分解。故有：

p(T)≤|′|

2)當(dāng)dT′(v)為偶數(shù)時，由引理2知，在T′的最小路分解中，不存在以v點(diǎn)為端點(diǎn)的路徑。設(shè)P∈是一條通過v的路徑，不妨令P={…wvt…}，由P及u構(gòu)造2條路徑則為T的路分解。可得：

p(T)≤|′|

由引理3知，p(T)≥p(T′)，當(dāng)dT′(v)為偶數(shù)時，即dT(v)為奇數(shù)，則取等號不成立。

綜上即有：

p(T′)

故：

3 應(yīng)用

例1某個樹T的結(jié)構(gòu)如圖3，求樹T的最小路分解數(shù)。

由定理1易知在度為1和2的點(diǎn)上結(jié)果為0，故現(xiàn)只討論度大于2的點(diǎn)的情況。

=1+1+2+1+1+1+1=8

圖3 最小路分解數(shù)為8的樹

注1一個樹最小路分解的數(shù)目與該樹的葉子數(shù)無關(guān)。

不難看出,圖4和圖5中其葉子數(shù)目都是6，但是在圖4中最少分解路為4，而在圖5卻為3。由此得出，結(jié)論樹最小路分解的數(shù)目與該樹的葉子數(shù)無關(guān)。

圖4 最小路分解數(shù)為4的樹 圖5 最小路分解數(shù)為3的樹

4 結(jié)語

研究了樹可分解路的最小條數(shù)，這一結(jié)論為一般連通圖中的路徑的研究奠定基礎(chǔ)，在圖論的結(jié)構(gòu)理論研究中有著重要的意義。由樹的路分解，進(jìn)一步可以研究樹的路因子理論，這將是以后的重點(diǎn)研究對象。