圖的團橫貫數(shù).pdf

1、在過去的三十多年里，隨著計算機科學的迅速發(fā)展，圖論也得到了飛速發(fā)展，而圖的橫貫理論的研究是圖論中發(fā)展較快的幾個領域之一．圖的橫貫理論能夠快速發(fā)展的主要原因是它在組合優(yōu)化、編碼理論、計算機科學、通信網絡、監(jiān)視系統(tǒng)和選址等理論與實踐中有著重要的應用背景．其中圖的團橫貫是是圖中重要的一種橫貫． 由于，對于大部分圖，團橫貫數(shù)的判定問題均是NP-完全的，所以對團橫貫數(shù)的上下界進行精確估計以及圖的結構性質的刻畫是人們很感興趣的問題，這對于設

2、計相應的近似算法有重要的實際意義．本文主要研究了幾類圖上的團橫貫數(shù)，其相應的結果分為以下三部分： 第一部分，首先得到了立方圖上的團橫貫數(shù)的上下界，并對達到下界的立方圖進行了刻畫，另外得到了無爪立方圖上的一個緊的上界，并在無爪立方圖中把團橫貫數(shù)與匹配數(shù)進行了比較．最后我們證明了無爪立方圖是弱2－可著色的．(此結果被 Lecture Notes in Computer Science錄用) 第二部分，給出了外平面圖中團橫貫數(shù)