多分圖 - 维基百科,自由的百科全书
在數學的分支圖論中,一個 k-分圖是一個图,其點集被分成 k 部分,各部分各自形成独立集。換句话說,可以把圖的所有點著色,使得相鄰的點著不同色且總共用了k 個顏色。k = 2 的情況被稱作二分圖,而 k = 3 的情況被稱作三分圖。
K2,2,2 | K3,3,3 | K2,2,2,2 |
---|---|---|
![]() 由正八面體的頂點和邊組成的圖 | ![]() 由複廣義正八面體的頂點和邊組成的圖 | ![]() 由正十六胞體的頂點和邊組成的圖 |
事實上,辨別一個圖是二分圖只需要多項式時間。但當 k > 2,辨別一個圖是否為 k-分圖卻是NP完全的[1] 。不過,在一些圖論的應用場合中,給計算器處理 k-分圖會包含 k 個部份的劃分,比如說各個部分所代表的是不同類型的物件。例如可以用三分圖做大眾分類法的數學模型,三個部份分別為系統的使用者、系統擁有的資料來源、使用者給資料來源的標籤[2]。
一個完全 k-分圖是一個 k-分圖,其中兩點若屬於相異的部分則必相鄰。該圖的記為一個大寫 K,在下標標註個部份的頂點數,並用英文逗號分開。例如 K2,2,2 可以想成正八面體的頂點和邊,其中三個獨立集使三組對頂點。所有的完全 k-分圖統稱為完全多分圖[3]。圖蘭圖是一種特殊的完全多分圖,其中各部分的頂點數至多差 1。
参考资料
[编辑]- ^ Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, 1979, ISBN 0-7167-1045-5.
- ^ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd, FolkRank : A Ranking Algorithm for Folksonomies, LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006: 111–114, 2006[失效連結].
- ^ Chartrand, Gary; Zhang, Ping, Chromatic Graph Theory, CRC Press: 41, 2008, ISBN 9781584888017.