關(guān)于圖的測(cè)地?cái)?shù)若干問(wèn)題的研究.pdf

1、華東師范大學(xué)碩士學(xué)位論文關(guān)于圖的測(cè)地?cái)?shù)若干問(wèn)題的研究姓名：莫艷紅申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：呂長(zhǎng)虹20070401論文摘要圖的測(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)給出圖的最小測(cè)地集與割點(diǎn)之間

2、的關(guān)系；(2)討論了圖死(楊)和L(a)的測(cè)地?cái)?shù)；(3)研究了GV目的測(cè)地?cái)?shù)及其上測(cè)地?cái)?shù)和下測(cè)地?cái)?shù)；(4)討論了GP3的測(cè)地?cái)?shù)在第二章中，介紹了無(wú)向圖的測(cè)地?cái)?shù)，我們主要做了以下的工作：我們研究了含有割點(diǎn)的圖的測(cè)地集，并得到相關(guān)結(jié)論；圖的最小測(cè)地集都不包含它的割點(diǎn)，這個(gè)結(jié)論是對(duì)文獻(xiàn)[8】中有關(guān)樹(shù)兀測(cè)地?cái)?shù)這一內(nèi)容的推廣；在【8】中，CraryChartrand，F(xiàn)rankHarary和PingZhang證明了g(蜀)=n，我們推廣了這個(gè)結(jié)論

3、得到，如果圖G有H≥3個(gè)頂點(diǎn)和k個(gè)割點(diǎn)，并且G的每個(gè)塊都是完全圖，那么罟(G)=n—k我們定義了一個(gè)新圖n(忉若L表示頂點(diǎn)為n≥2的樹(shù)，日為一個(gè)圖，則乃㈣表示如下構(gòu)造得到的圖，用圖Ⅳ來(lái)替代乃中所有的頂點(diǎn)，若版，凰分別表示代替乃中相鄰頂點(diǎn)“，V的圖H，則用邊拶來(lái)代替死的邊UV，其中xE礦(風(fēng))，Y∈V(UO并且證明了以下結(jié)論t如果乃是有”≥2個(gè)頂點(diǎn)，，片葉子的樹(shù)，那么g(乃(楊))=Id；f2，d=4如果死是星圖，那么“L(o))=3，d

4、=5，6；I4，d≥7如果霸不是星圖，且n有，片樹(shù)葉，d24，n≥3，那么g(L(c0))≤塒州『91，’2伽一D1在第三章中，討論了有向圖的測(cè)地?cái)?shù)，我們主要研究了Gv日的上m測(cè)地?cái)?shù)及和測(cè)地?cái)?shù)之間的關(guān)系，證明了下列結(jié)果，對(duì)于任意圖G和H，有g(shù)一(Gv加=2如果G和Ⅳ是兩個(gè)非平凡圖，那么g(GV功≥g(G)g(邱在文獻(xiàn)【1】中，呂長(zhǎng)虹提出了一個(gè)關(guān)于圖的測(cè)地?cái)?shù)的猜想，對(duì)于任意圖G，都有g(shù)(G)≥g(G)，并且證明了當(dāng)d是n階連通圖的直徑且d