李瑞娟,曹艷琴

(山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,山西 太原 030006)

0 引言

本文中的有向圖是無(wú)環(huán)、無(wú)平行弧的簡(jiǎn)單有向圖。路、跡和圈指的是有向路,有向跡和有向圈。本文中的術(shù)語(yǔ)可參看文獻(xiàn)[1]。

設(shè)D是一個(gè)有向圖,用V(D)和A(D)分別表示D的頂點(diǎn)集和弧集。對(duì)于任意的頂點(diǎn)x,y,z∈V(D),如果x,y間有弧,則稱x,y相鄰。如果(x,y)∈A(D)且(y,x)∈A(D),則稱弧(x,y)是對(duì)稱的,反之稱為非對(duì)稱的。對(duì)于一個(gè)非空頂點(diǎn)子集S?V(D),D的由S誘導(dǎo)的子圖指的是以S為頂點(diǎn)集,以A(D)中兩個(gè)端點(diǎn)都在S中的弧為弧集的有向圖,記為D[S].如果S滿足:(1)S中任意兩點(diǎn)在D中都不相鄰;(2)對(duì)于任意的z∈V(D)-S,存在一點(diǎn)v∈S,使得(z,v)∈A(D),則稱S是有向圖D的核。如果一個(gè)有向圖D的任何導(dǎo)出子圖都有核,則稱D是核完美有向圖。

一個(gè)有向圖D的弧著色指的是一個(gè)映射C∶A(D)→N,C(x,y)=i表示弧(x,y)著顏色i.如果D有一個(gè)弧著色,則稱D是弧著色有向圖,它的所有弧的顏色構(gòu)成的集合記為C(D).若C(D)=m,稱D為m-弧著色有向圖。如果弧著色有向圖D中所有弧的顏色都不同,稱D是彩虹圖。設(shè)P=(v0,v1,…,vk)是弧著色有向圖D中的一條(v0,vk)有向路。P的長(zhǎng)度記為l(P)=|V(P)|-1=k.對(duì)于i,j∈{1,2,…,k},P中從vi到vj的有向路記為(vi,P,vj).如果P中所有弧的顏色都不同,稱P是彩虹(v0,vk)路。P中所有弧的顏色構(gòu)成的集合記為C(P),C(vi,P,vj)表示P中從vi到vj的有向路中所有弧的顏色的集合。設(shè)C=v0v1…vkv0是弧著色有向圖D中的一個(gè)有向圈。圈C的長(zhǎng)度記為l(C)=|V(C)|=k+1.如果C中所有弧的顏色都不同,則稱C是彩虹圈。設(shè)S?V(D)是一個(gè)非空子集滿足:(1)S中任意兩點(diǎn)之間在D中都沒(méi)有彩虹路;(2)對(duì)于任意的z∈V(D)-S,D中都有從z到S的彩虹路,則稱S是弧著色有向圖D的彩虹路的核。

設(shè)D是一個(gè)m-弧著色有向圖,D的閉包c(diǎn)(D)是一個(gè)有向圖滿足:

V(c(D))=V(D),

A(c(D))=A(D)∪{(u,v)|D中有彩虹(u,v)路P}.

顯然,c(D)的一個(gè)核是D的一個(gè)彩虹路的核。如圖1是一個(gè)6個(gè)頂點(diǎn)的5-弧著色的二部競(jìng)賽圖和它的閉包。

Fig.1 A 5-arc-coloured bipartite tournament on 6 vertices and its closure圖1 6個(gè)頂點(diǎn)的5-弧著色二部競(jìng)賽圖和它的閉包

如果一個(gè)有向圖D的頂點(diǎn)集V(D)可以劃分成兩個(gè)非空的子集V1和V2,使得A(D)中的每條弧的兩個(gè)端點(diǎn)分別在V1和V2中,則稱D是二部有向圖。如果V1中的每個(gè)頂點(diǎn)都與V2中的每個(gè)頂點(diǎn)相鄰,稱D為二部競(jìng)賽圖。顯然二部競(jìng)賽圖不含有奇圈。如果4個(gè)頂點(diǎn)的二部競(jìng)賽圖滿足它的頂點(diǎn)集為{u,v,w,x},弧集為{(u,v),(v,w),(w,x),(u,x)},則將這樣的二部競(jìng)賽圖記為TB4.如果5個(gè)頂點(diǎn)二部競(jìng)賽圖滿足它的頂點(diǎn)集為{u,v,w,x,y},弧集為{(u,v),(v,w),(w,x),(x,y),(x,u),(y,v)},則將這樣的二部競(jìng)賽圖記為CB5.

1982年,Sands等在文獻(xiàn)[2]中提出了單色路的核的概念,并且還證明了在每個(gè)2-弧著色的有向圖D中都有單色路的核。1988年,Shen在文獻(xiàn)[3]中證明了在m-弧著色的競(jìng)賽圖中,如果所有3階子競(jìng)賽圖滿足至多有一條弧與其他弧的顏色不同,其余弧的顏色都相同(稱為擬單色的),則T存在單色路的核。1996年,Galeana-Snchez在文獻(xiàn)[4]中證明了在m-弧著色的競(jìng)賽圖T中,如果每個(gè)長(zhǎng)至多為4的圈都是擬單色的,則T存在單色路的核。2004年,Galeana-Snchez和Rojas-Monroy在文獻(xiàn)[5]中證明了在弧著色的二部競(jìng)賽圖D中,如果每個(gè)長(zhǎng)為4的圈都是單色的,則D存在單色路的核。2009年,Galeana-Snchez和Rojas-Monroy在文獻(xiàn)[6]中證明了在弧著色的二部競(jìng)賽圖D中,如果每個(gè)長(zhǎng)為4的圈和每個(gè)階為4的傳遞子二部競(jìng)賽圖T4都是擬單色的,則D存在單色路的核。2015年,Contreras-Balbuena,Galeana-Snchez和Rojas-Monro在文獻(xiàn)[7]中證明了弧著色有向圖D(可能有無(wú)窮多個(gè)點(diǎn))中,如果每個(gè)有向圈和每個(gè)無(wú)限長(zhǎng)的外向路中存在兩個(gè)連續(xù)的點(diǎn)xi和xi+1滿足弧著色有向圖D中有(xi,xi+1)單色路,則D中有單色路的核。2016年,Galeana-Snchez和Snchez-López在文獻(xiàn)[8]中證明了對(duì)于一個(gè)弧著色有向圖D和它的單色路的閉包c(diǎn)(D),如果c(D)的頂點(diǎn)集存在一個(gè)劃分{V1,V2,…,Vp}滿足:(1)對(duì)于任意的i,c(D)[Vi]是單色的;(2)任意的i≠j,如果(Vi,Vj)中有一條弧是c(D)的弧,則(Vi,Vj)?A(c(D)),那么D中存在單色路的核，更多單色路的核的結(jié)論見(jiàn)參考文獻(xiàn)[9-13]。

2009年，Delgado-Escalante和Galeana-Snchez在文獻(xiàn)[14]中提出了正常著色路的核的概念。2018年,Bai等在文獻(xiàn)[15]中提出了如果一個(gè)弧著色有向圖D的所有圈都是正常著色的,則D中有正常著色路的核的猜想,他們證明了這一猜想在弧著色的無(wú)圈有向圖,半完全有向圖和二部競(jìng)賽圖中的正確性。特別地,他們定義了弧著色有向圖中彩虹路的核,并證明了對(duì)于一個(gè)給定的弧著色有向圖,判斷是否存在彩虹路的核是NP-Hard問(wèn)題。2018年,Delgado-Escalante和Galeana-Snchez在文獻(xiàn)[16]中給出了在弧著色的競(jìng)賽圖、準(zhǔn)傳遞有向圖和k-部競(jìng)賽圖中存在正常著色路的核的充分條件。2018年，Bai,Li和Zhang在文獻(xiàn)[17]中給出了弧著色競(jìng)賽圖有彩虹路的核的充分條件。本文研究弧著色二部競(jìng)賽圖中彩虹路的核的存在性,給出了弧著色二部競(jìng)賽圖中存在彩虹路的核的充分條件。為了證明主要結(jié)論,我們將用到下面關(guān)于核完美有向圖的結(jié)論。

定理1[18]設(shè)D是一個(gè)有向圖,如果D中每個(gè)有向圈都至少有一條對(duì)稱弧,則D是核完美有向圖。

1 主要結(jié)論

引理1[4]設(shè)H=(V1,V2)是二部競(jìng)賽圖,C=(v0,v1,…,vn)是H中的有向途徑。對(duì)于任意的i,j∈{0,1,2,…,n},如果vi與vj相鄰,當(dāng)且僅當(dāng)j-i≡1(mod 2).

引理2 設(shè)H=(V1,V2)是二部競(jìng)賽圖,則H中每個(gè)長(zhǎng)至多為6的有向閉途徑是一個(gè)有向圈,每個(gè)長(zhǎng)至多為3的有向跡是一條有向路。

證明設(shè)C是H中的有向閉途徑,且l(C)≤6.因?yàn)镠是二部競(jìng)賽圖,所以l(C)≠2.若l(C)=4,設(shè)C=u0u1u2u3u0.因?yàn)?u0,u1)∈A(H),(u1,u2)∈A(H),且H是二部競(jìng)賽圖,所以u(píng)0≠u2.同理u1≠u3.因此C是H中的有向圈。若l(C)=6,設(shè)C=u0u1u2u3u4u5u0.由于H=(V1,V2)是二部競(jìng)賽圖,所以對(duì)于任意的i∈{0,2,4},j∈{1,3,5},有ui≠uj.又因?yàn)閧(ui,ui+1),(ui+1,ui+2)}?A(H)(下標(biāo)mod 6),所以對(duì)于任意的i∈{0,1,…,5},ui≠ui+2,因此C是H中的有向圈。

設(shè)T是H中的有向跡,且l(T)≤3.若l(T)=1,結(jié)論顯然成立。若l(T)=2.設(shè)T=(u0,u1,u2),由于H是二部競(jìng)賽圖,所以u(píng)0≠u2,則T是H中的有向路。若l(T)=3,設(shè)T=(u0,u1,u2,u3),同理由于H是二部競(jìng)賽圖,因此對(duì)于任意的i∈{0,2},j∈{1,3},ui≠uj,即T是H中的有向路。

引理3 設(shè)H=(V1,V2)是m-弧著色的二部競(jìng)賽圖,若H中的每個(gè)圈都是彩虹圈且每個(gè)子二部競(jìng)賽圖TB4和CB5都是彩虹的,對(duì)于任意的u,v∈V(H),H中有彩虹(u,v)路但沒(méi)有彩虹(v,u)路,則下列結(jié)論至少有一個(gè)成立:

(1)(u,v)∈A(H);

(2)H中存在長(zhǎng)為2的(u,v)有向路。

證明設(shè)P是H中的彩虹(u,v)路,對(duì)P的長(zhǎng)度l(P)作數(shù)學(xué)歸納。當(dāng)l(P)=1時(shí),即(u,v)∈A(H).當(dāng)l(P)=2時(shí),即H中存在長(zhǎng)為2的彩虹(u,v)路,結(jié)論顯然成立。

假設(shè)當(dāng)l(P)=n時(shí),結(jié)論成立。當(dāng)l(P)=n+1≥3時(shí),設(shè)H中的彩虹(u,v)路為P=(u=u0,u1,…,un+1=v).當(dāng)n+1為奇數(shù)時(shí),由引理1可知,un+1與u0相鄰。事實(shí)上,(u0,un+1)∈A(H).因?yàn)槿绻?un+1,u0)∈A(H),則(un+1,u0)是H中的彩虹(v,u)路,矛盾。因此,只需考慮當(dāng)n+1為偶數(shù)時(shí),H中有長(zhǎng)為2的(u,v)有向路。

當(dāng)n+1=4時(shí),設(shè)P=(u=u0,u1,u2,u3,u4=v)是H中的彩虹(u,v)路,若(u0,u3)∈A(H),則(u=u0,u3,u4=v)是H中長(zhǎng)為2的(u,v)有向路,結(jié)論成立。若(u1,u4)∈A(H),則(u=u0,u1,u4=v)是H中長(zhǎng)為2的(u,v)有向路,結(jié)論成立。若(u3,u0)∈A(H)且(u4,u1)∈A(H),則H[u0,u1,u2,u3,u4]是H中的CB5,又因?yàn)镠中的CB5都是彩虹的,所以(v=u4,u1,u2,u3,u0=u)是H中的彩虹(v,u)路,矛盾。

當(dāng)n+1=6時(shí),設(shè)P=(u=u0,u1,u2,u3,u4,u5,u6=v)是H中的彩虹(u,v)路。若(u0,u5)∈A(H),則(u=u0,u5,u6=v)是H中長(zhǎng)為2的(u,v)有向路,結(jié)論成立。若(u1,u6)∈A(H),則(u=u0,u1,u6=v)是H中長(zhǎng)為2的(u,v)有向路,結(jié)論成立。故假設(shè)(u5,u0)∈A(H)且(u6,u1)∈A(H),因?yàn)閡0Pu5u0是H中的彩虹圈,所以C(u5,u0)?C(u1,P,u5).同理因?yàn)閡1Pu6u1是彩虹圈,所以C(u6,u1)?C(u1,P,u5).若C(u5,u0)≠C(u6,u1),則(v=u6,u1,P,u5,u0=u)是H中的彩虹(v,u)路,矛盾。因此設(shè)C(u5,u0)=C(u6,u1)=α.顯然α?C(P),因?yàn)槿籀痢蔆(P),則u0Pu5u0和u1Pu6u1中至少有一個(gè)不是彩虹圈,矛盾。當(dāng)(u3,u6)∈A(H)時(shí),若(u0,u3)∈A(H),則(u=u0,u3,u6=v)是H中長(zhǎng)為2的(u,v)有向路,結(jié)論成立;若(u3,u0)∈A(H),則u0u1u2u3u0是H中的有向圈且H[u3,u4,u5,u0]是H中的TB4,由引理3的條件可知,C(u3,u0)?{C(u1,P,u3)∪α},因此(v=u6,u1,u2,u3,u0=u)是H中的彩虹(v,u)路,矛盾。當(dāng)(u6,u3)∈A(H)時(shí),由于u3u4u5u6u3是H中的圈且H[u1,u2,u3,u6]是TB4,由引理3的條件可知,C(u6,u3)?{C(u3,P,u5)∪α},因此(v=u6,u3,u4,u5,u0=u)是H中的彩虹(v,u)路,矛盾。

當(dāng)n+1≥8時(shí),因?yàn)閚≡1(mod 2),由引理1可知,u0與un相鄰,u1與un+1相鄰。若(u0,un)∈A(H),則(u=u0,un,un+1=v)是H中長(zhǎng)為2的(u,v)有向路,結(jié)論成立。若(u1,un+1)∈A(H),則(u=u0,u1,un+1=v)是H中長(zhǎng)為2的(u,v)有向路,結(jié)論成立。因此假設(shè)(un,u0)∈A(H)且(un+1,u1)∈A(H).因?yàn)閡0Punu0是彩虹圈,所以C(un,u0)?C(u1,P,un).同理因?yàn)閡1Pun+1u1是彩虹圈,所以C(un+1,u1)?C(u1,P,un).若C(un,u0)≠C(un+1,u1),則(v=un+1,u1,P,un,u0=u)是H中的彩虹(v,u)路,矛盾。因此考慮C(un,u0)=C(un+1,u1)=α的情形。顯然α?C(P),因?yàn)槿籀痢蔆(P),則u0Punu0和u1Pun+1u1中至少有一個(gè)不是彩虹圈,矛盾。

斷言1 若存在i,j∈{1,2,…,n},j-i≥3,使得(ui,uj)∈A(H),則H中有長(zhǎng)為2的(u,v)有向路。

證明 由定理的條件,u0PuiujPunu0和u1PuiujPun+1u1是H中的彩虹圈,所以C(ui,uj)?C(u0,P,ui)∪C(uj,P,un+1),則P′=(u=u0,P,ui,uj,P,un,un+1=v)是H中的彩虹(u,v)路,且l(P′)

當(dāng)i=1時(shí),即(un+1,u3)∈A(H),又因?yàn)?un+1,u1)∈A(H),所以H[un+1,u1,u2,u3]是H中的TB4,又因?yàn)镠中的TB4是彩虹的,所以C(un+1,u3)≠C(un+1,u1)=α.又u3Pun+1u3是H中彩虹圈,所以C(un+1,u3)?C(u3,P,un),即(v=un+1,u3,P,un,u0=u)是H中的彩虹(v,u)路,矛盾。

定理2 設(shè)H=(V1,V2)是m-弧著色的二部競(jìng)賽圖,若H中的每個(gè)圈都是彩虹圈且每個(gè)TB4和CB5都是彩虹的,則c(H)是核完美有向圖。

證明反證法。假設(shè)c(H)不是核完美有向圖,由定理1可設(shè)C=u0u1…unu0是c(H)中沒(méi)有對(duì)稱弧的圈。

斷言3 對(duì)于任意的i∈{0,1,…,n},或者(ui,ui+1)∈A(H),或者H中有長(zhǎng)為2的(ui,ui+1)有向路。

證明 由假設(shè)C是c(H)中沒(méi)有對(duì)稱弧的圈,所以對(duì)于任意的i∈{0,1,2,…,n},有(ui,ui+1)∈A(c(H))且(ui+1,ui)?A(c(H)),由c(H)的定義可知,對(duì)于任意的i∈{0,1,2,…,n},H中有彩虹(ui,ui+1)路且沒(méi)有彩虹(ui+1,ui)路,由引理2可知,或者(ui,ui+1)∈A(H),或者H中有長(zhǎng)為2的(ui,ui+1)有向路,結(jié)論成立。

下面對(duì)n進(jìn)行討論。

當(dāng)n=2時(shí),即C=u0u1u2u0,由于H是二部競(jìng)賽圖,所以存在i∈{0,1,2},使得(ui,ui+1)?A(H)(下標(biāo)mod 3).不妨設(shè)(u0,u1)?A(H),由斷言3,H中存在長(zhǎng)為2的(u0,u1)有向路,不妨設(shè)為(u0,v0,u1)。

若{(u1,u2),(u2,u0)}?A(H),由定理2的條件可知,u0v0u1u2u0是H中的彩虹圈,則(u1,u2,u0)是H中的彩虹(u1,u0)路。由c(H)的定義可得,(u1,u0)∈A(c(H))是C中弧(u0,u1)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。

若(u1,u2)∈A(H),(u2,u0)?A(H),由斷言3,H中存在長(zhǎng)為2的(u2,u0)有向路,不妨設(shè)為(u2,v2,u0),則C′=u0v0u1u2v2u0是H中一個(gè)長(zhǎng)為5的閉途徑,由引理2可知,C′是H中的一個(gè)長(zhǎng)為5的圈,與H是二部競(jìng)賽圖矛盾。同理若(u2,u0)∈A(H),(u1,u2)?A(H),由斷言3,H中存在長(zhǎng)為2的(u1,u2)有向路,不妨設(shè)為(u1,v1,u2),則C′=u0v0u1v1u2u0是H中一個(gè)長(zhǎng)為5的閉途徑,由引理2可知,C′是H中的一個(gè)長(zhǎng)為5的圈,與H是二部競(jìng)賽圖矛盾。

若(u1,u2)?A(H)且(u2,u0)?A(H),由斷言3,對(duì)于任意的i∈{0,1,2},H中存在長(zhǎng)為2的(ui,ui+1)有向路,不妨設(shè)為(ui,vi,ui+1),則C′=u0v0u1v1u2v2u0是H中的長(zhǎng)為6的閉途徑。由引理2和定理2的條件得,C′是H中的彩虹圈,因此(u1,v1,u2,v2,u0)是H中的彩虹(u1,u0)路。由c(H)的定義可得(u1,u0)∈A(c(H))是C中弧(u0,u1)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。

當(dāng)n≥3時(shí),由斷言3可令

情形1 (z3,z0)∈A(H).由引理2和定理2的條件可知,z0z1z2z3z0是H中的彩虹圈,由C′的定義可知,u1=z1或u1=z2.若u1=z1,則(u1=z1,z2,z3,z0=u0)是H中的彩虹(u1,u0)路,所以(u1,u0)∈A(c(H))是C中弧(u0,u1)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。若u1=z2,則(u1=z2,z3,z0=u0)是H中的彩虹(u1,u0)路,所以(u1,u0)∈A(c(H))是C中弧(u0,u1)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。

情形2 (z0,zk-2)∈A(H).由引理2和定理2的條件可知,z0zk-2zk-1zkz0是H的彩虹圈,由C′的定義,un=zk-1或un=zk.若un=zk-1,則(u0=z0,zk-2,zk-1=un)是H中的彩虹(u0,un)路,由c(H)的定義,(u0,un)∈A(c(H))是C中弧(un,u0)的對(duì)稱弧,與C是c(H)中無(wú)對(duì)稱弧的圈矛盾。若un=zk,(u0=z0,zk-2,zk-1,zk=un)是H中的彩虹(u0,un)路,由c(H)的定義,(u0,un)∈A(c(H))是C中弧(un,u0)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。

則(z0,z2j0+1)∈A(H),(z2j0+3,z0)∈A(H),由定理2的條件,z0z2j0+1z2j0+2z2j0+3z0是H中的彩虹圈。

當(dāng)φ(2j0+1)=z2j0+1時(shí),令z2j0+1=uj.由C′的定義,uj+1=z2j0+2或uj+1=z2j0+3.若uj+1=z2j0+2,則(uj+1=z2j0+2,z2j0+3,z0,z2j0+1=uj)是H中的彩虹(uj+1,uj)路,由c(H)的定義,(uj+1,uj)∈A(c(H))是C中弧(uj,uj+1)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。若uj+1=z2j0+3,則(uj+1=z2j0+3,z0,z2j0+1=uj)是H中的彩虹(uj+1,uj)路,由c(H)的定義,(uj+1,uj)∈A(c(H))是C中弧(uj,uj+1)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。

當(dāng)φ(2j0+1)≠z2j0+1時(shí),由φ的定義,φ(2j0+1)=z2j0=φ(2j0).由C′的構(gòu)造可得,φ(2j0+2)=z2j0+2,令z2j0+2=uj(2≤j≤n-1),則z2j0=uj-1.由于(2j0+3)-2j0≡1(mod 2),由引理1,z2j0與z2j0+3相鄰。

若(z2j0+3,z2j0)∈A(H),由定理2的條件,z2j0z2j0+1z2j0+2z2j0+3z2j0是H中的彩虹圈,則(uj=z2j0+2,z2j0+3,z2j0=uj-1)是H中的彩虹(uj,uj-1)路,由c(H)的定義可知,(uj,uj-1)∈A(c(H))是C中弧(uj-1,uj)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。

若(z2j0,z2j0+3)∈A(H),由于2j0-1≡1(mod 2),由引理1,z0與z2j0-1相鄰,由j0的極小性得,(z0,z2j0-1)∈A(H),由定理2的條件,則z0z2j0-1z2j0z2j0+1z2j0+2z2j0+3z0是H中的彩虹圈,所以(uj=z2j0+2,z2j0+3,z0,z2j0-1,z2j0=uj-1)是H中的彩虹(uj,uj-1)路,由c(H)的定義,(uj,uj-1)∈A(c(H))是C中弧(uj-1,uj)的對(duì)稱弧,與C是c(H)中沒(méi)有對(duì)稱弧的圈矛盾。

綜上所述,在每一種情形下都找到了矛盾,因此c(H)是核完美有向圖。

定理3 設(shè)H=(V1,V2)是m-弧著色的二部競(jìng)賽圖,若H中的每個(gè)圈都是彩虹圈且每個(gè)TB4和CB5都是彩虹的,則H中有彩虹路的核。

證明由定理2可知,c(H)是核完美有向圖,設(shè)S?V(c(H))是c(H)的一個(gè)核,因此對(duì)于任意的x,y∈S,x和y在c(H)中不相鄰且對(duì)任意的z∈V(c(H))-S,存在一點(diǎn)v∈S,使得(z,v)∈A(c(H)).由c(H)的定義,對(duì)任意的x,y∈S,H中沒(méi)有彩虹(x,y)路且對(duì)任意的z∈V(H)-S,H中有從z到S的彩虹路。因此S是H的彩虹路的核。