圖的（d1）全標(biāo)號問題的中期報(bào)告

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