r一致B—混合超圖可著色的最大邊數

王雅

摘 要： 本文主要討論了r一致B-混合超圖的可著色問題，并給出了一個可著色最大邊數的下界.

關鍵詞： 混合超圖 最大邊數 r一致B-混合超圖

1.引言

傳統圖與超圖的染色問題產生于19世紀并在20世紀得到了較快發展和完善，該理論主要解決的是根據一定的約束條件，將一個目標集分解成若干個子集的問題，該理論可應用于地圖的染色、排序、資源的分配、數據庫管理等領域.一個超圖的色數就是該超圖的所用顏色最少的染色所用的染色數.而很顯然，所用最多的顏色數為該超圖的頂點數.因此，超圖的染色理論是最小定點的染色理論.

3.混合超圖染色理論的主要應用

混合超圖的染色理論有廣泛的應用背景，可應用于以下方面：

（1）能源應用問題。由一組能源，所有能源都可以在任何時間內開通且工作時間都為一個單位時間，但有些能源不能完全開通，而有些能源不能在完全不同的時間開通，第一種類型能源組成D-超邊，第二種類型組成C-超邊，得到一混合超圖，則改組能源的排序問題可轉化為相應的混合超圖的染色問題.

（2）工作排序問題。由n項工作，每項工作可在任何單位時間內完成，有些工作由于使用同一種能源，以而不能同時開始，而由于技術上的原因，有些工作又必須同時開始，第一種類型的工作組成D-超邊，第二種類型的工作組成C-超邊，得到一個混合超圖，該工作的排序問題也可以轉化為混合超圖的染色問題.

混合超圖的染色理論還可以應用于平行計算、數據庫管理、分子生物學等其他理論.

參考文獻：

[1]Tao Jiang，Dhruv Mubayi，Zaolt Tuza，Vitaly Voloshin and Douglas B，West，The Chromatic Spectrum of Mixed Hypergraphs[J].Graphs and Combinatorics，2002，8：64-74.

[2]Berge C.Graphs and Hypergraphs [M].North Holland： Amsterdam，1973.

[3]Berge C.Hypergraphs：Combinatorics of Finite Sets[M].North Holland： Amsterdam，1989.