樹(shù)圖上k-控制問(wèn)題和塊圖上2-控制問(wèn)題的算法研究.pdf

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

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

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

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