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

王雅

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

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

1.引言

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

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

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

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

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

混合超圖的染色理論還可以應(yīng)用于平行計(jì)算、數(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.