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

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

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