用圖論方法判斷范疇的特殊對象

葉麗霞

(浙江外國語學院科學技術學院，浙江杭州310012)

1 引言

在同調(diào)代數(shù)中，范疇的始對象、終對象和零對象是非常重要的概念.

定義1［1］11設C為范疇.若I∈obC滿足

定義2［1］11設C為范疇.若I∈obC滿足

則稱I為C的一個終對象.若Z同時是C中的始對象與終對象，則稱Z為C的一個零對象.

定義 3［2］172設有向圖 D= ＜ V，E ＞=m.令為頂點vi鄰接到頂點vj的邊的條數(shù)，稱()n×n為D的鄰接矩陣.

定義4［2］206一棵非平凡的有向樹，如果有一個頂點的入度為0，其余頂點的頂點的入度均為1，則稱此有向樹為根樹.在根樹中，入度為0的頂點稱為樹根;入度為1，出度為0的頂點稱為樹葉.

定義 5［2］157設 D= ＜ V，E ＞ 為 n 階有向圖，若，即圖中每個頂點的度都是0，則稱D為n階零圖.特別地，1階零圖也稱為平凡圖.

定義6［2］162設D= ＜V，E＞為n階有向簡單圖，

則稱D為n階圈圖.

可以看出，范疇的定義比較抽象，而且范疇的始對象或終對象不一定存在.在文獻［1］的例5中，作者用圖來表示范疇，這樣就可以相對直觀地判斷出范疇的特殊對象.本文利用圖論知識建立了判斷范疇的始對象、終對象和零對象的兩個等價定理，并得到了偏序范疇等特殊范疇的相關推論.

2 主要結(jié)論及相關推論

設C為范疇，其中對象集是obC={a1，a2，…，an}.現(xiàn)規(guī)定obC為圖的頂點集，當不同對象ai到aj存在態(tài)射時，則在兩頂點之間連上一條有向邊，但忽略各對象到自身的恒等態(tài)射，于是范疇C可表示為一個沒有環(huán)和重邊的n階有向簡單圖.

定理1 設C為范疇，其中obC={a1，a2，…，an}.設圖G為范疇C對應的n階圖，則有

(1)若在圖G中，頂點ai到其余n－1個頂點都只有一條長度小于n的有向通路，則ai是范疇的一個始對象;

(2)若在圖G中，其余n－1個頂點到頂點ai都只有一條長度小于n的有向通路，則ai是范疇的一個終對象;

(3)若頂點ai同時滿足以上兩個條件，則ai是范疇的一個零對象.

證明 若在范疇C對應的圖G中，頂點ai到其余n－1個頂點都只有一條長度小于n的有向通路，則在范疇C中，對象ai到其余n－1個對象都只有一個態(tài)射，而ai到自身存在恒等態(tài)射，于是ai到每個對象都只有一個態(tài)射，根據(jù)定義1，ai是范疇C的一個始對象;同理，若在圖G中，其余n－1個頂點到頂點ai都只有一條有向通路，則在范疇C中每個對象到ai都只有一個態(tài)射，根據(jù)定義2，ai是C的一個終對象.第三種情形顯然成立.

由于任何一個有向圖都有唯一的鄰接矩陣，故定理1有以下一個等價定理:

定理2 設C為范疇，其中obC={a1，a2，…，an}.設圖G為范疇C對應的n階圖，A為圖G的鄰接矩陣，令矩陣 B=A+A2+ … +An－1，則有

(1)若在矩陣B的第i行中，bii=0，該行其余元素都是1，則頂點ai是范疇C的一個始對象;

(2)若在矩陣B的第i列中，bii=0，該列其余元素都是1，則頂點ai是范疇C的一個終對象;

(3)若在矩陣B的第i行和第i列中，bii=0，第i行和第i列的其余元素都是1，則頂點ai是C的一個零對象.

當范疇對應的圖是一些特殊圖時，可得到相應的推論.

任意偏序集合C=(obC，≤)可看作一個范疇，其中obC的元素為對象，對象ai到aj存在一個態(tài)射當且僅當ai≤aj.把偏序關系的關系圖刪去所有環(huán)，就得到偏序范疇對應的圖，于是有以下結(jié)論:

推論1 設C是一個偏序范疇，于是范疇存在始對象當且僅當obC存在一個最小元;范疇存在終對象當且僅當obC存在一個最大元.特別地，若范疇只有一個對象，則此對象是零對象.

證明 若ai是偏序集C=(obC，≤)的最小元，則ai≤aj對所有aj∈obC都成立.于是在范疇C對應的圖中，頂點ai到其余n－1個頂點都只有一條長度小于n的有向通路，由定理1，ai是C的一個始對象.同理可證最大元就是終對象.若范疇只有一個對象，則此對象既是最小元也是最大元，從而它是零對象.

實際上，由于偏序范疇對應的圖和哈斯圖一一對應，因此在推論1的實際應用中，也可以根據(jù)哈斯圖來判斷特殊對象.在哈斯圖中，若最下端的頂點只有一個，那么它就是始對象;若最上端的頂點只有一個，那么它就是終對象.在全序關系的哈斯圖中，最下端的頂點就是始對象，最上端的頂點就是終對象.

例 集合obC={1，2，3，6}上的整除關系是一個偏序關系，偏序范疇C對應的圖和哈斯圖分別如圖1中(1)、(2)所示，顯然最小元1和最大元6分別是偏序范疇的始對象和終對象.

圖1 偏序范疇對應的圖和哈斯圖

推論2 若范疇對應的圖是一棵根樹，則根樹的樹根為范疇的始對象，當且僅當根樹只有一片樹葉時，該樹葉是范疇的終對象.另外，當根樹是一棵平凡樹時，它的唯一頂點是范疇的零對象.

證明 由定義4易知樹根到其余頂點都只有一條長度小于n的有向通路，由定理1，樹根為范疇的始對象.若根樹只有一片樹葉，那么其余頂點到該樹葉都只有一條長度小于n的有向通路，于是該樹葉是范疇的終對象.當根樹是一棵平凡樹時，它的唯一頂點顯然是零對象.

推論3 若范疇對應的圖是一個n階零圖，則當n＞1時，范疇不存在始對象和終對象;當n=1時，該唯一頂點是零對象.

證明 由定義5易知零圖中的每個頂點都是孤立點，則每個頂點到其它頂點都沒有通路，于是只有當n=1時，該唯一頂點是零對象.

推論4 設范疇C對應的圖是一個n階圈圖，其中obC={a1，a2，…，an}，且邊集E={＜a1，a2＞，＜a2，a3＞，…，＜an－1，an＞，＜an，a1＞}，則頂點 a1是零對象.

證明 由定義6，圈圖的邊集 E={＜a1，a2＞，＜a2，a3＞，…，＜an－1，an＞，＜an，a1＞}，則頂點 a1到每個頂點都有一條長度小于n的有向通路，根據(jù)定理1，頂點a1是零對象.

［1］佟文廷.同調(diào)代數(shù)引論［M］.北京:高等教育出版社，1998.

［2］屈婉玲，耿素云，張立昂.離散數(shù)學［M］.2版.北京:清華大學出版社，2008.