發(fā)布時(shí)間：2020-03-22 02:49

【摘要】：圖G=(V,E)的一個(gè)混合控制集是一個(gè)滿足如下條件的集合D銰V∪E:不在D中的每個(gè)點(diǎn)或每條邊都相鄰或關(guān)聯(lián)于D中的至少一個(gè)點(diǎn)或一條邊.確定圖的最小基數(shù)的混合控制集的問(wèn)題稱為混合控制問(wèn)題.本文研究混合控制問(wèn)題的算法復(fù)雜性,證明了混合控制問(wèn)題在無(wú)向路圖上是NP-完全的,但在塊圖上有線性時(shí)間算法.無(wú)向路圖和塊圖都是弦圖的子類,又是樹的母類.

【相似文獻(xiàn)】

相關(guān)期刊論文 前6條

1 楊振宇,陳宗基;遞階混合控制系統(tǒng)的分析、綜合與證明[J];控制與決策;1998年01期

2 肖笛,程勉,高為炳;機(jī)器人的自適應(yīng)混合控制[J];北京航空航天大學(xué)學(xué)報(bào);1992年04期

3 楊振宇,陳宗基;基于HIOA~+模型的混合控制設(shè)計(jì)[J];信息與控制;1998年03期

4 張曉芹;康麗英;;塊圖中的無(wú)權(quán)1-中心問(wèn)題[J];上海大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

5 程郁琨;;塊圖上的p-maxian問(wèn)題[J];蕪湖職業(yè)技術(shù)學(xué)院學(xué)報(bào);2009年01期

6 李永欣;劉巖;;圈塊圖的最小Hosoya指數(shù)[J];華南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年04期

相關(guān)碩士學(xué)位論文 前1條

1 寧宇;塊圖的2-彩虹控制問(wèn)題算法研究[D];華東師范大學(xué);2011年

，

本文編號(hào)：2594351