|
點集合D 是圖形G=(V,E) 的支配集(Dominating Set)，則每一個V-D 中的點必需和D
中的點必需和D 中的一個點相連接，而G 的支配數(Domatic Number)是G 中彼此不相
交支配集的最大個數，我們把它記為d(G)。所謂支配分割(Domatic Partition) 問題
是將V 分割成d(G)個支配集。兩兩不相交的邊稱為配對(Matching)，擁有最大個數的
配對稱為最大配對(Maximum Matching)。在本論文中，我們提出了一個新的演算法設
計方法稱為延遲查詢(Deferred-Query)，並以此方法針對區段圖(Interval Graphs)
上支配分割及配對問題設計快速的演算法。此外，我們亦以貪進法(Greedy)設計一個
簡單的演算法解決強弦圖(Strongly Chordal Graphs) 上的支配分割問題。
|