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

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

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