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

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

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

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

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