二元傳遞關(guān)系計數(shù)的上界估計

董永紅 郭海林 劉智秉

(1 九江學(xué)院理學(xué)院; 2 九江學(xué)院圖書館 江西九江 332005)

1 預(yù)備知識

定義1［1］若S?R ×R，則稱S為R上的一個二元關(guān)系.稱S對應(yīng)的m階(0，1)矩陣A =(aij)m×m為S的關(guān)聯(lián)矩陣，即(ai，aj)∈S，aij =1;(ai，aj)?S，aij =0.

定義2［2］給定一個二元關(guān)系S，S對應(yīng)一個有向圖Γ，稱Γ 為S的對應(yīng)圖.圖Γ的頂點集為R ={ai|i =1，2，…，m}，邊集為E ={eij=aiaj|(ai，aj)∈S}.

定義3 給定一個二元關(guān)系S，記RS ={ai∈R|?aj∈R，s.t. (ai，aj)∈S}.稱|RS|為關(guān)系S涉及R的元素個數(shù).一般|RS|≤m =|R|.若|RS|=m稱S為二元全涉關(guān)系，此時關(guān)系對應(yīng)的矩陣稱為全涉矩陣，對應(yīng)的圖為全涉圖.依據(jù)圖論知識，有向圖的邊集是一個多重子集，而二元關(guān)系是單重子集，因此二元關(guān)系的對應(yīng)圖是沒有重邊的.

文獻［4］的完全計數(shù)是考慮有限集R中元素的次序下，滿足某些性質(zhì)的二元關(guān)系的計數(shù).若不考慮有限集R中元素的次序，筆者發(fā)現(xiàn)二元關(guān)系對應(yīng)的關(guān)聯(lián)矩陣滿足交換行列的合同變換，稱為置換合同，即:B=PAPT，其中P為置換矩陣，PT表示P的轉(zhuǎn)置.易見這種合同變換是全體關(guān)聯(lián)矩陣上的一個等價變換，由此本文將關(guān)聯(lián)矩陣合并成等價類，來討論二元關(guān)系的等價類計數(shù).特別是結(jié)合關(guān)聯(lián)矩陣與有向圖的關(guān)系，估計出二元傳遞關(guān)系的等價類計數(shù)的一個上界.

2 主要結(jié)論

定理2 二元傳遞關(guān)系的等價類計數(shù)記為qm，其一個上界為Lm:

其中［x］表示對實數(shù)x下取整.

證明定理2 時，需要轉(zhuǎn)化為有向圖來討論，在此處介紹兩個命題.

命題1 若二元傳遞關(guān)系對應(yīng)的圖是圈，則涉及n個點的圈是一個有向圈.

證明:如果二元傳遞關(guān)系對應(yīng)的涉及n個點的圈為a1→a2→a3→…→an→a1，那么對任意的i，j有ai→aj，aj→ai.不妨設(shè)i≤j≤n，當i ＜j時，有aij=aji =1;當i=j時，由傳遞性知ai(i+j)=a(i+j)i =1，有aii =1.由此圈上的每個點都帶有自環(huán)，且每條邊都是雙向的，易見這種圈對應(yīng)的矩陣為全1 陣.如果傳遞關(guān)系對應(yīng)的有向圖中有圈，那么將這樣的圈看成一個點或壓縮為一點，并不改變原圖的連通性.由此我們來構(gòu)造新的有向圖.

例如對圖Γ=(V，E)，V為圖的頂點，E為圖的邊.用ai，aij分別表示原圖Γ的頂點和邊，用a'i，a″ij分別表示新圖Γ'的頂點和邊.

若圖Γ的頂點集為:

則新圖Γ'的頂點集為:

其中V(Γ1)，V(Γ2)，…，V(ΓS)為有向圈上的點集，V(Γ Γi)為原圖減去所有有向圈后余下的頂點集.這樣原圖中的頂點集V(Γi)在新圖中被壓縮成一個點a'i.

上述方法構(gòu)造的新圖與原圖有命題2 描述的性質(zhì).

命題2 若圖Γ'是圖Γ 構(gòu)造的，則新圖不改變原圖的連通性.此處的連通性是指:①圖Γ 中的有向圈與其分支的連通性;②圖Γ 中除去有向圈后剩余點的連通性;③圈與圈之間的連通性.

證明:

(1)設(shè)圖Γ 中的一個有向圈為Γ1=(V1，E1).假設(shè)ak?V1，若ai∈V1，使得aki =1，則對任意的aj∈V1，有akj=akiaij =1.同樣的，若ai∈V1，使得aik=1，則對任意的aj∈V1，有ajk=ajiaik =1.若原圖中頂點集V1中有許多點與ak相連，而新圖Γ'是將V1壓縮成一點與ak相連，因此這種壓縮不改變圖的連通性.即圖Γ 中的有向圈與其分支的連通性.

(2)設(shè)圖Γ 中所有圈的頂點集合為V1，V2，…，Vs.圖Γ的頂點為:

其中i =1，2，…，s;(VVi)表示圖Γ 減去所有圈余下的頂點集，w1∈V1，w2∈V2，…，ws∈Vs.

如果對任意的ai，aj∈(VVi)，有邊aiaj∈E(Γ)，那么新圖Γ'中有邊aia'j并且aia'j=aiaj.即圈外的點的連通性Γ'與Γ 是一致的.

(3)若頂點wi∈Vi，wj∈V，任取ai∈Vi，aj∈Vj有wij=aij =1，在新圖Γ'中表現(xiàn)為一個圈被壓縮成一個點.于是圖Γ 中的s個圈被壓縮為s個點，此時s個圈的連通性被簡化成s個點的連通性，因此新圖Γ'與原圖Γ的連通性是一致的.

為了方便刻畫二元關(guān)系的計數(shù)，筆者引入一個引理.

其中［x］表示對實數(shù)x下取整.

［1］Martin Aigner and Gunter M Ziegler. Proofs from the book (3rd edition.) ［M］. Berlin: Springer-Verlag Heidelberg，2004. 26.

［2］Reinhard Diestel. Graph Theory ［M］. Berlin: Springer-Verlag Heidelberg，2006. 13.

［3］劉丁酉. 矩陣分析［M］. 武漢: 武漢大學(xué)出版社，2003. 27.

［4］董永紅，朱一心，石富華. 二元關(guān)系的完全計數(shù)［J］. 數(shù)學(xué)的實踐與認識，2011，41(24) : 217.