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

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

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