圖的幾種測地集.pdf

1、測地線的概念起源于幾何學(xué)，拓撲學(xué)及函數(shù)分析中的凸集理論，它在選址問題，網(wǎng)絡(luò)設(shè)計及控制理論等方面有重要意義.在圖論中定義了凸性后，測地線問題及與之相關(guān)的測地數(shù)問題成為揭示圖的結(jié)構(gòu)性質(zhì)的一個重要指標及參數(shù).
　　 本文主要研究圖的測地集問題．特別是具有特定限制條件的圖的測地集，如邊測地集，線測地集等.同時，考慮了部分圖的運算的測地集問題．
　　 （一）在第一章中，我們首先簡單介紹了圖論的起源發(fā)展，介紹了測地集概念的產(chǎn)生背景及

2、在圖論中的推廣意義及測地集問題的研究現(xiàn)狀和進展.同時，介紹了相關(guān)問題的一些基本概念和記號．
　　 （二）在第二章第一節(jié)，我們首先研究圖的測地集的性質(zhì)，介紹了測地集與圖的其它結(jié)構(gòu)參數(shù)的關(guān)系，并在此基礎(chǔ)上得到了單圈圖與完全r部圖的測地數(shù)．
　　 第二節(jié)，確定了一些圖類的邊測地數(shù)，并指出圖的測地數(shù)與邊測地數(shù)的關(guān)系．主要結(jié)果如下：
　　 (ⅰ)設(shè)G為樹Tn（或完全圖Kn，Kn-e，Km,n，Km1，…mr及單圈圖Gn）．

3、則g(G)=ge(G)；
　　 (ⅱ)對于任意的正整數(shù)2≤a≤b，存在連通圖G使得：g(G)=a，ge(G)=b．
　　 第三節(jié)中，研究了圖的線測地集與線測地數(shù)，確定了一些簡單圖類的線測地集和線測地數(shù).主要結(jié)果如下：
　　 (ⅰ)設(shè)T是葉子數(shù)為k的n階樹，則gl(T)=七，且對T中的葉子集合任意標記下標為：S={v1，v2，…，vk}，S都構(gòu)成了T的最小線測地集．
　　 (ⅱ)設(shè)G(≠)Cn為單圈圖，且種

4、植在圈上的樹不全為路，則gl(G)=g(G)．
　　 （三）在第三章中，考慮了圖的部分運算對邊測地集（線測地集）的影響．主要結(jié)果如下：
　　 設(shè)S1，S2分別為兩個非平凡圖G，日的最小邊測地集（線測地集）．若u∈S1,v∈S2，則:
　　 (ⅰ)ge(Gu+H)=ge(G)+ge(H)-2,gl(Gu+Hv)=gl(G)+gl(H)-2.
　　 (ⅱ)ge(GuoHv)=ge(G)+ge(H)-2，gl(