论文摘要
图的测地数是揭示图的结构特性的一个重要参数。图的测地数源于几何学、拓扑学和函数分析中的凸集理论，是凸集理论在图论中的应用和推广，也与图论中“路覆盖”和“路分解”等问题相关联。本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工作，主要的工作包括以下四个部分：（1）给出图的最小测地集与割点之间的关系；（2）讨论了图Tn（Kd）和Tn（Cd）的测地数；（3）研究了G∨H的测地数及其上测地数和下测地数；（4）讨论了G×P3的测地数。在第二章中，介绍了无向图的测地数，我们主要做了以下的工作：我们研究了含有割点的图的测地集，并得到相关结论：图的最小测地集都不包含它的割点，这个结论是对文献[8]中有关树Tn测地数这一内容的推广；在[8]中，Grary Chartrand，Frank Harary和Ping Zhang证明了g（Kn）=n，我们推广了这个结论得到：如果图G有n≥3个顶点和k个割点，并且G的每个块都是完全图，那么g（G）=n-k。我们定义了一个新图Tn（H）。若Tn表示顶点为n≥2的树，H为一个图，则Tn（H）表示如下构造得到的图：用图H来替代Tn中所有的顶点，若Hu，Hv分别表示代替Tn中相邻顶点u，v的图H，则用边xy来代替Tn的边uv，其中x∈V（Hu），y∈V（Hv）。并且证明了以下结论：●如果Tn是有n≥2个顶点，l片叶子的树，那么g（Tn（Kd））=ld；如果Tn不是星图，且Tn有l片树叶，d≥4，n≥3，那么g（Tn（Cd））≤min{「d／2」l，2（n-l）}。在第三章中，讨论了有向图的测地数，我们主要研究了G∨H的上（下）测地数及和测地数之间的关系，证明了下列结果：●对于任意图G和H，有g-（G∨H）=2。如果G和H是两个非平凡图，那么g+（G∨H）≥g+（G）+g+（H）。在文献[1]中，吕长虹提出了一个关于图的测地数的猜想：对于任意图G，都有g+（G）≥g（G），并且证明了当d是n阶连通图的直径且d≥（n-1）／2或g（G）≤4时，这个猜想是正确的，我们主要研究了G∨H的上测地数和测地数之间的关系，并且证明了：●如果G和H都不是完全图，那么g+（G∨H）≥g（G∨H）；如果H是完全图，G是弦图或ω（G）＜3，那么g+（G∨H）≥g（G∨H）；假设S是G的最小2-N-控制集，如果H是完全图，S中每一点在G／S中至多只有一个邻居，那么g+（G∨H）≥g（G∨H）。在第四章中，讨论了图的笛卡儿积的测地数。在文献[1]中，吕长虹给出了g（G）=g（G×K2）的充要条件，我们考察了当g（H）=2时G×H的测地数，得出了下列结论：●如果存在最小测地集S和基于S的测地族F使得S相对于F分成（S1，S2），那么对任意测地数为2的图H有g（G）=g（G×H）。●设G是不平凡的连通图，那么g（G）=g（G×P3）当且仅当存在最小测地集S和基于S的测地族F使得S相对于F分成（S1，S2，S3）或（S1，S2）。