圖和有向圖的測(cè)地?cái)?shù).pdf

1、圖的測(cè)地?cái)?shù)是揭示圖的結(jié)構(gòu)特性的一個(gè)重要參數(shù)。圖的測(cè)地?cái)?shù)源于幾何學(xué)、拓?fù)鋵W(xué)和函數(shù)分析中的凸集理論，是凸集理論在圖論中的應(yīng)用和推廣，也與圖論中“路覆蓋”和“路分解”等問(wèn)題相關(guān)聯(lián)。 本文主要介紹圖和有向圖的測(cè)地?cái)?shù)的研究進(jìn)展和本人在這方面所做的工作，主要的工作包括以下四個(gè)部分：(1)給出完全r-部圖的測(cè)地?cái)?shù)；(2)研究了Gu+Hv的測(cè)地?cái)?shù)及其上測(cè)地?cái)?shù)和下測(cè)地?cái)?shù)；(3)研究了GuoHv的測(cè)地?cái)?shù)及其上測(cè)地?cái)?shù)和下測(cè)地?cái)?shù)；(4)討論了G×K3的

2、測(cè)地?cái)?shù)。 在第二章中，介紹了無(wú)向圖的測(cè)地?cái)?shù)，我們主要做了以下二方面的工作：●在文獻(xiàn)[10]，GaryChartrand，F(xiàn)rankHarary和PingZhang給出了完全二部圖的測(cè)地?cái)?shù)，即：g(Kr,s)=min{r,s，4}(r,s≥2)，我們類似地給出完全r-部圖的測(cè)地?cái)?shù)，即：g(Kn1，n2，…，nr)=min{n1，4}，其中ni≥2，i=1，2，…，r且n1≤n2≤…≤nr.●在文獻(xiàn)[4]，呂長(zhǎng)虹考察了圖的兩種運(yùn)算G

3、u+Hv和GuoHv，得出當(dāng)u，v分別屬于G和H最小測(cè)地集時(shí)，有g(shù)(Gu+Hv)=g(G)+g(H)-2和g(GuoHv)=g(G)+gH)-2。我們推廣上面的結(jié)論，證明了對(duì)于u和v分別是G和H中的任意點(diǎn)，都有g(shù)(G)+g(H)-2≤g(Gu+Hv)≤g(G)+g(H)，g(G)+g(H)-2≤g(GuoHv)≤g(G)+g(H). 在第三章中，討論了有向圖的測(cè)地?cái)?shù)，我們主要研究了Gu+Hv和GuoHv的上(下)測(cè)地?cái)?shù)，證明了下

4、列結(jié)果： ●設(shè)G和H是非平凡圖，對(duì)于u∈V(G)，v∈V(H)，則g+(G)+g+(H)-2≤g+(Gu+Hv)≤g+(G)+g+(H)，g-(G)+g-(H)-2≤g-(Gu+Hv)≤g-(G)+g-(H)；g+(G)+g+(H)-2≤g+(GuoHv)≤g+(G)+g+(H)，g-(G)+g-(H)-2≤g-(GuoHv)≤g-(G)+g-(H).●設(shè)G和H是兩個(gè)非平凡圖，當(dāng)u和v分別是G和H的懸掛點(diǎn)時(shí)，有g(shù)+(Gu+Hv)

5、=g+(G)+g+(H)，g-(Gu+Hv)=g-(G)+g-(H)-2；g+(GuoHv)=g+(G)+g+(H)-1，g-(GuoHv)=g-(G)+g-(H)-2. 在第四章，我們研究了圖的笛卡兒積G×K3的測(cè)地?cái)?shù)，得出了下列結(jié)論：●設(shè)G是非平凡連通圖，如果G包含某個(gè)最小測(cè)地集S，在S中存在一點(diǎn)x使得G中的任意點(diǎn)都位于x-w測(cè)地線上，其中w∈S，那么g(G)≤g(G×K3)≤g(G)+1. ●設(shè)G是階數(shù)至少為3的連