text: 在數學的分支圖論中，一個 "k"-分圖是一個圖，其點集被分成 "k" 部分，各部分各自形成獨立集。換句話說，可以把圖的所有點著色，使得相鄰的點著不同色且總共用了"k" 個顏色。"k" = 2 的情況被稱作二分圖，而 "k" = 3 的情況被稱作三分圖。事實上，辨別一個圖是二分圖只需要多項式時間。但當 "k" &gt; 2，辨別一個圖是否為 "k"-分圖卻是NP完全的 。不過，在一些圖論的應用場閤中，給計算器處理 "k"-分圖會包含 "k" 個部份的劃分，比如說各個部分所代表的是不同型別的物件。例如可以用三分圖做大眾分類法的數學模型，三個部份分別為系統的使用者、系統擁有的資料使用者給資料標籤。一個完全 "k"-分圖是一個 "k"-分圖，其中兩點若屬於相異的部分則必相鄰。該圖的記為一個大寫 K，在下標標註個部份的頂點數，並用英文逗號分開。例如 "K"2,2,2 可以想成正八面體的頂點和邊，其中三個獨立集使三組對頂點。所有的完全 "k"-分圖統稱為完全多分圖。圖蘭圖是一種特殊的完全多分圖，其中各部分的頂點數至多差 1。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 多分圖
metadata: https://zh.wikipedia.org/wiki?curid=6202224