王雅

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

關(guān)鍵詞： 混合超圖 最大邊數(shù) r一致B-混合超圖

1.引言

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

3.混合超圖染色理論的主要應(yīng)用

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

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

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

混合超圖的染色理論還可以應(yīng)用于平行計算、數(shù)據(jù)庫管理、分子生物學(xué)等其他理論.

參考文獻(xiàn)：

[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.