圖的幾種測(cè)地集.pdf

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

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

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

4、植在圈上的樹(shù)不全為路，則gl(G)=g(G)．
　　 （三）在第三章中，考慮了圖的部分運(yùn)算對(duì)邊測(cè)地集（線測(cè)地集）的影響．主要結(jié)果如下：
　　 設(shè)S1，S2分別為兩個(gè)非平凡圖G，日的最小邊測(cè)地集（線測(cè)地集）．若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(