關于圖測地數(shù)界的研究.pdf

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

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