Abstract
中文摘要 在二分排列圖上的支配數問題 國立清華大學資訊工程學系碩士學位論文 學生：崔愷文 指導教授：唐傳義 支配數( Domatic Number )是圖形演算法上一重要且相當困難之問題，在計算機網路上有著許多方面的應用，支配數問題的定義結合了支配集問題( Dominating Set )和著色數問題( Chromatic Number )為：在一圖上，對點集合作分組，使得每一組均為一支配集，並要使分出的組數為最大。而在實際的應用上，這是一個非常實用的問題，在計算機網路上，每一個可提供服務的機器均為一節點，要讓服務能遍及所有的網路，即為一支配集問題，若希望在至少毀損k個節點時，此網路仍可正常運作，此時k即為此網路拓樸的支配數。然而，此問題在一般的圖形上為一NP-Hard問題，因此，本篇論文的內容主要是探討支配數問題在二分排列圖( Bipartite Permutation Graph )上的性質，並提出一線性時間複雜度的演算法。 關鍵字：支配集，支配分割，支配數，二分排列圖