圖論中的控制與相關問題

Abstract

圖論中的控制問題，起源於作業研究的選址問題。在實際的應用上，控制問題會有許 多不同的變型。本論文探討其中的三種變型問題，即所謂K 鄰旁控制、邊控制和K 鄰 旁覆蓋，同時，也討論一些相關的問題，如控制數和邊控制數。 以下我們將正式的定義這些問題。考慮一個圖型G=(V，E)，所謂K 鄰旁控制問題是指 在G 中，找一個最小點集合 D，使得不在D 的點，一定和D 中至少K 個點相鄰。邊控 制問題是選一個最小邊集合De，使得不在 De 中的邊，必與 De 中某邊相鄰。而K 鄰 旁覆蓋的意思是在G 中，找一個最小的點集合 C，使得對G 中的每個邊，都存在C 中 的某點，與其兩端點的距離，同時小於或等於 K。控制數是指使得 V=Umi=1Di，并且 每個 Fi 均為G 的邊控制集的最大可能值n。 在本論文中，我們首先對K 鄰旁控制和邊控制問題，在塊狀圖 (block graphs) 上， 提出了線性的算則，同時證明K 鄰旁控制問題在弦圖(Chordal graphs)和二分圖(bi- partite graphs) 上是 NP 難。再者，我們決定了完全n 分圖 (Complete n-partite graphs) 的控制數和完全三分圖 (Complete 3-partite graphs)的邊控制數。最后， 我們在強弦圖 (strongly chordal graphs)上，針對K 鄰旁覆蓋，給了一個線性算則 ，也證明這問題在弦圖上是 NP 難。