關于圖的測地數(shù)若干問題的研究.pdf

1、華東師范大學碩士學位論文關于圖的測地數(shù)若干問題的研究姓名：莫艷紅申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：呂長虹20070401論文摘要圖的測地數(shù)是揭示圖的結(jié)構特性的一個重要參數(shù)圖的測地數(shù)源于幾何學，拓撲學和函數(shù)分析中的凸集理論，是凸集理論在圖論中的應用和推廣。也與圖論中“路覆蓋”和“路分解”等問題相關聯(lián)本文主要介紹圖和有向圖的測地數(shù)的研究進展和本人在這方面所做的工作，主要的工作包括以下四個部分，(1)給出圖的最小測地集與割點之間

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

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

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