圖與超圖的全著色的任務(wù)書

圖與超圖的全著色的任務(wù)書題目：圖與超圖的全著色【問題描述】在圖論中，圖是由一些節(jié)點(diǎn)或頂點(diǎn)和它們的邊所組成的。圖論中的一個重要問題是尋找圖的某種著色方式，使得相鄰節(jié)點(diǎn)著不同的顏色。這種著色方式稱為圖的全著色。超圖是圖的加強(qiáng)版，超圖中的節(jié)點(diǎn)可以同時和多個邊相連。超圖的全著色問題是給超圖中的節(jié)點(diǎn)著顏色，使得每條邊的所有節(jié)點(diǎn)顏色都不相同。請你分別實(shí)現(xiàn)圖和超圖的全著色算法，并分析算法的時間復(fù)雜度和空間復(fù)雜度?！据斎敫袷健枯斎胛募邪舾尚?，每行代表一條邊或超邊，每條邊或超邊的格式如下：kv1v2...vk其中，k表示邊或超邊上節(jié)點(diǎn)或頂點(diǎn)的總數(shù)，v1,v2,...,vk表示這些節(jié)點(diǎn)或頂點(diǎn)的編號，編號范圍是1到n。例如，下面是一個圖的數(shù)據(jù)文件：423453134212235這個圖的節(jié)點(diǎn)編號是1、2、3、4、5，共有5個節(jié)點(diǎn)。其中，第一條邊連接了四個節(jié)點(diǎn)，分別是2、3、4、5。第二條邊連接了三個節(jié)點(diǎn)，分別是1、3、4。第三條邊連接了兩個節(jié)點(diǎn)，分別是1、2。下面是一個超圖的數(shù)據(jù)文件：423452133125這個超圖的節(jié)點(diǎn)編號是1、2、3、4、5，共有5個節(jié)點(diǎn)。其中，第一條超邊連接了兩個節(jié)點(diǎn)，分別是2、3，第二條超邊連接了三個節(jié)點(diǎn)，分別是1、2、5?！据敵龈袷健枯敵鑫募邪舾尚?，每行代表一個節(jié)點(diǎn)的顏色，每行的格式如下：ic其中，i表示節(jié)點(diǎn)的編號，c表示該節(jié)點(diǎn)著的顏色。例如，下面是一個解決上述圖全著色問題得到的輸出文件：1122334152【樣例說明】樣例輸入文件表示的是上面的圖。如果對這個圖進(jìn)行全著色，方案如下：1可以是1、2或3。2可以是1或3。3可以是2或3。4可以是1、2或3。5可以是1或3。根據(jù)上面的方案可以得到如下的輸出文件：1123324153【提示信息】1.算法的實(shí)現(xiàn)需要選擇合適的數(shù)據(jù)結(jié)構(gòu)來表示圖和超圖，并且需要合理處理節(jié)點(diǎn)的顏色。2.建議先實(shí)現(xiàn)圖或超圖中的全著色算法，然后再