當(dāng)前大家對(duì)于圖著色問題都是頗為感興趣的，大家都想要了解一下圖著色問題，那么小美也是在網(wǎng)絡(luò)上收集了一些關(guān)于圖著色問題的一些信息來分享給大家，希望能夠幫到大家哦。

1、圖著色問題（Graph Coloring Problem, GCP） 又稱著色問題，是最著名的NP-完全問題之一。

2、道路著色問題（Road Coloring Problem）是圖論中最著名的猜想之一。

3、數(shù)學(xué)定義：給定一個(gè)無向圖G=（V, E），其中V為頂點(diǎn)集合，E為邊集合，圖著色問題即為將V分為K個(gè)顏色組，每個(gè)組形成一個(gè)獨(dú)立集，即其中沒有相鄰的頂點(diǎn)。

4、其優(yōu)化版本是希望獲得最小的K值。

本文到此結(jié)束，希望對(duì)大家有所幫助。

版權(quán)說明：本文由用戶上傳，如有侵權(quán)請(qǐng)聯(lián)系刪除！

標(biāo)簽：