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

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