關(guān)于圖測(cè)地?cái)?shù)界的研究.pdf

1、連通圖G中的任意兩點(diǎn)u和v，一條u-v測(cè)地線是指u，v兩點(diǎn)間的最短路。令Lu，v表示位于u-v測(cè)地線上所有點(diǎn)的集合。對(duì)于子集S，令I(lǐng)(S)=Uu，v∈I(u，v)，如果I(S)=V(G)，則我們稱S是G的測(cè)地集。把圖G測(cè)地集的最小基數(shù)叫做G的測(cè)地?cái)?shù)。同樣我們可以相對(duì)應(yīng)的定義有向圖D的相關(guān)概念.對(duì)圖G的所有邊給定一個(gè)方向后的圖稱為圖G的定向圖，我們稱S(G)={g(D)：D是圖G的定向圖}為圖G測(cè)地?cái)?shù)的譜。g+(G)=maxS(G)為圖G

2、的上測(cè)地?cái)?shù)。本文討論了無(wú)向圖以及有向圖的測(cè)地?cái)?shù)，主要內(nèi)容如下：
　　 在第一章中，我們簡(jiǎn)單介紹了圖測(cè)地集研究的背景與已有的一些結(jié)果。
　　 在第二章中，我們研究上測(cè)地?cái)?shù)下界的一個(gè)猜想：如果圖G是一個(gè)直徑為d最小度為δ的非平凡的連通圖，則有g(shù)+(G)≥d+δ。證明了這個(gè)猜想對(duì)無(wú)三圈圖，△(G)≤3的圖以及單位區(qū)間圖是正確的。
　　 在第三章中，我們先給出了二部圖與完全圖笛卡爾積上測(cè)地?cái)?shù)的下界。并且研究圖上測(cè)地?cái)?shù)與測(cè)