樹圖上k-控制問題和塊圖上2-控制問題的算法研究.pdf

1、在過去的三十多年里,隨著計算機科學的迅速發(fā)展,圖論也得到了飛速發(fā)展,而圖論中發(fā)展最快的領域也許就是控制數(shù)理論的研究.控制數(shù)理論能夠快速發(fā)展的主要原因是它在現(xiàn)實世界中,例如編碼理論,計算機科學,通信網絡,監(jiān)視系統(tǒng)和社會網絡等理論與實踐中有著廣泛而深刻的應用背景.對于一個正整數(shù)k,k-控制問題就是尋找滿足下列條件擁有最小點數(shù)的集合D:即不在集合D中的任意點,至少需要被點集D中k個點所控制,G中所有滿足該條件的集合的最小勢叫做無向圖G的k-控

2、制數(shù).
　　對于圖G=（V,E）,每個點帶有二維標號M（v）=（t（v）,k（v））,其中k（v）的取值范圍是k（v）∈{0,1,2…,k},t（v）∈{B,R}.這種標號定義下的k-混合控制問題就是要找到一個包含所有t（v）=R的集合D使得所有不在D中的點至少被D中k（v）個點所控制.
　　換句話說,圖G=（V,E）的一個k-混合控制集D就是點集V中滿足下列兩個條件的子集:（MD1）如果t（v）=R,那么v∈D（MD2）對

3、于所有不在D中的點v,|NG（v）∩D|≥k（v）所有k-混合控制集的最小勢是該圖的k-混合控制數(shù),記作rkM（G）.具有最小k-混合控制數(shù)的集合稱為該圖的最小k-混合控制集.在圖的控制數(shù)理論研究中,算法研究是一個十分活躍的研究方向,其中一項重要工作是在特殊圖類上尋找控制數(shù)及其相關參數(shù)的有效算法,樹圖和塊圖是兩類著名的特殊圖類,它形成弦圖和完美圖的子類,它們在解決很多現(xiàn)實問題中有重要作用,由于樹圖和塊圖具有良好的結構性質,因此許多N P

4、-完全的控制數(shù)及其相關參數(shù)問題限制在樹圖和塊圖上都是多項式時間可解的.
　　本文我們主要研究了兩類控制參數(shù)（k-控制和k-混合控制）的算法問題,以下是本文的主要結果:（1）本文給出計算樹圖上最小k-混合控制數(shù)的線性時間算法,并證明了算法的正確性.同時該算法可被推廣用于找出樹上最小k-控制集.（2）本文給出計算塊圖上最小2-混合控制數(shù)的線性時間算法,并證明了算法的正確性.同時該算法可被推廣用于找出塊圖上最小2-控制集.（3）本文證明