塊圖的2-彩虹控制問題算法研究.pdf

1、設(shè)圖G是一個(gè)簡(jiǎn)單無向連通圖，_f：V(G)→P({1，…，к})。滿足：對(duì)任意點(diǎn)v∈V(G)，若f(v)=θ，則一定有Uu∈N[v]f(u)={1，…，к}。此時(shí)f稱為圖G的к-彩虹控制函數(shù)(к-RDF)。w(f)=∑v∈V(G)|f(v)|稱為f的權(quán)重。圖G的к-RDF的最小權(quán)重稱為G的к-彩虹控制數(shù)，記作γrk(G)。к-彩虹控制問題就是對(duì)任意圖，確定它的к-彩虹控制數(shù)和最小權(quán)重的к-彩虹控制函數(shù)。
　　 本文在前人關(guān)于樹к

2、-彩虹控制問題的研究成果的基礎(chǔ)上，探討了塊圖的2-彩虹控制問題的多項(xiàng)式時(shí)間算法。首先，給出了一個(gè)以塊為單位遍歷塊圖的方式，其次分析了一些特殊塊的2-彩虹控制標(biāo)記方法，并證明了塊圖上的2-彩虹控制問題與2-弱彩虹控制問題是等價(jià)的。定義了塊圖中一種特殊結(jié)構(gòu)-交替塊列，并給出了一種查找交替塊列的算法-回溯算法。并給出了一個(gè)塊圖的2-弱彩虹控制問題的多項(xiàng)式時(shí)間算法(M2-WRDF)。
　　 本文還研究了一類特殊的Cactus圖-S-Ca