廣義Halin圖的競(jìng)爭(zhēng)數(shù).pdf

1、ClassifiedIndex：1573UDC：5103SecrecyRate：Pubizie——d——UniversityCode：10082HebeiUniversityofScienceandTechnologyDissertationfortheMasterDegreeCompetitionNumbersofCandidate2Supervisor：AssociateSupervisor：AcademicDegreeApplie

2、dfor：Speciality：Employer：DateofOralExamination：GeneralizedHalinGraphsCaoZhijunProfWeiXianglinMasterofScienceMathematicsCollegeofSciencesJune，2015摘要摘要競(jìng)爭(zhēng)圖概念是由Cohen在研究生態(tài)學(xué)問題時(shí)提出的。令D=(V，A)為一個(gè)有向圖，D的競(jìng)爭(zhēng)圖C(D)為無向圖G，其頂點(diǎn)集與D的頂點(diǎn)集相同，對(duì)甜，

3、v∈V，UV∈E(G)，當(dāng)且僅當(dāng)存在頂點(diǎn)X∈V，使得(擾，x)，(v，X)∈4(D)。對(duì)于無向圖G，如果存在有向圖D使得C(D)=G，則稱G為競(jìng)爭(zhēng)圖。Robes發(fā)現(xiàn)，對(duì)于任意無向圖G，G并上足夠多的孤立頂點(diǎn)就是某個(gè)無圈有向圖的競(jìng)爭(zhēng)圖。這樣加進(jìn)來的孤立頂點(diǎn)的最少個(gè)數(shù)稱為圖G的競(jìng)爭(zhēng)數(shù)，記作七(G)。Opsut證明了計(jì)算圖的競(jìng)爭(zhēng)數(shù)是一個(gè)NPhard問題，所以一般來說計(jì)算圖的競(jìng)爭(zhēng)數(shù)是比較困難的。到目前為止，只知道一些特殊圖類的競(jìng)爭(zhēng)數(shù)。圖G的邊團(tuán)

4、覆蓋數(shù)曉(G)是指圖G的邊團(tuán)覆蓋所含團(tuán)的最小個(gè)數(shù)，圖G的邊團(tuán)覆蓋是指能覆蓋圖G的所有邊的一族團(tuán)。Halin圖G=丁uC為平面圖，包含無2度頂點(diǎn)的樹丁的一個(gè)平面嵌入和一個(gè)連接樹丁的葉子的圈C，并且C為外部面的邊界。若頂點(diǎn)x∈Uc(v)滿足Ⅳ，(v)r、坼(x)=g，則稱頂點(diǎn)v∈v(c)為樹丁的單葉，記樹r的所有單葉構(gòu)成的集合為K。(，2)Halin圖G為滿足下列條件的平面圖，其邊集E(G)可被劃分為E=E(r)wE(C1)uE(C2)uw

5、E(C)，其中丁為無2度頂點(diǎn)的樹，Cl，C2，，G為兩兩互不相交的圈，礦(C1)uy(C2)uuy(Cn)為樹丁的全部葉子。這樣，(1)HaliIl圖就是通常的Halin圖。稱一個(gè)最小度至少為3的2連通平面圖G為偽Halin圖，若刪除G的某個(gè)面五的邊界上的邊后得到的圖為樹。若五的頂點(diǎn)均為3度點(diǎn)，則G為Halin圖。面石的非正則點(diǎn)是指其度大于3的頂點(diǎn)，五的所有非正則點(diǎn)記作IR(fo)。如果允許Halin圖和(玎)一Halin圖中的樹有2度

6、頂點(diǎn)，則我們得到廣義Hdill圖和廣義(刀)Halin圖概念。論文研究廣義H2Llin圖、廣義(力)Halin圖和偽Halin圖的競(jìng)爭(zhēng)數(shù)，確定了廣義Halin圖和廣義(胛)。Halin圖的競(jìng)爭(zhēng)數(shù)的準(zhǔn)確值，給出了一類偽Halin圖的競(jìng)爭(zhēng)數(shù)的上界。主要結(jié)果如下：1令G為廣義Halin圖或廣義(門)H甜in圖。則有f1，G=蜀；七(G)=2，G≠E，K=a；I見(G)Iv(c)l2，G≠／q，K≠o。2令G為滿足條件IR(jj)=x)的偽Ha