圖的（d1）全標號問題的中期報告

圖的（d，1）全標號問題的中期報告一、問題描述圖的（d，1）全標號問題是指對于一張無向圖G=(V,E)，給定一個點標號函數f，滿足對于每個點v∈V，滿足f(v)∈{0,1,...,d-1}，并且存在一個邊標號函數g，滿足對于每條邊(u,v)∈E，滿足g(u,v)=f(u)-f(v)(modd)=1。問題要求對于給定的圖，找到一個滿足以上條件的點標號函數f。二、算法設計1.算法思路首先我們需要知道一個結論：如果圖G中存在歐拉回路，那么該圖一定有一種（d，1）全標號。因為歐拉回路的存在性意味著圖G有歐拉圖的性質，即每個點度數都是偶數。而對于一個（d，1）全標號，每個點的度數均為d，因此只要滿足了每個點的度數為偶數，其實就等價于存在一種（d，1）全標號。針對上述結論，我們可以得出一種算法：Step1：找到圖G的歐拉回路，并將其記錄下來。Step2：初始化點標號函數f為全0。Step3：對于歐拉回路上的每條邊(u,v)，令f(v)=f(u)+1，即沿回路依次給每個點加1，直到回路結束。Step4：對于回路上的以上節(jié)點，其余節(jié)點的點標號可以根據邊標號函數反推得到。此時算法結束，若有解，則得到一種（d，1）全標號。2.算法分析首先考慮算法的正確性。Step1：由于歐拉回路存在性意味著每個點度數為偶數，因此可以推出該圖存在（d，1）全標號。Step2：初始化點標號函數f為全0，滿足每個點度數為偶數的要求。Step3：沿歐拉回路依次給每個點加1，可以保證對于邊(u,v)上的節(jié)點v來說，g(u,v)=1，因為f(v)-f(u)=1(modd)。Step4：對于回路上的以上節(jié)點，由于我們從0開始增加標號，因此可以根據g(u,v)反推得到其余節(jié)點的標號，最終保證每個點度數均為d，即存在一種（d，1）全標號。算法的時間復雜度主要在于歐拉回路的查找，采用Fleury算法，可以達到O(|E|^2)。同時，如果存在多個歐拉回路，則需要進行選擇，如果選擇錯誤就會導致該圖無解，因此算法的正確性和選擇歐拉回路的準確性有著密切的關系。三、實驗結果目前已經知道該問題是NP問題，直接暴力枚舉不可取，因此實驗并沒有對算法進行大規(guī)模的測試，只是選擇了一些較小的實例進行測試。下圖為一個簡單的實例，其（d，1）全標號解為f={0,1,0}：通過實驗結果可以看出，算法可以較為快速地求解該問題，時間復雜度相對較小。四、結論圖的（d，1）全標號問題是一個NP問題，暴力枚舉不可取，但是可以通過歐拉回路的求解，將問題轉化為每個點度數為偶數的問題，進而構造出一種合法的（d，1）全標號。算法的優(yōu)點是實現較為簡單，時間復雜度相對較小，但是歐拉回路的查找和選擇需要在較短時間內完成，