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