论文部分内容阅读
测地线的概念起源于几何学，拓扑学及函数分析中的凸集理论，它在选址问题，网络设计及控制理论等方面有重要意义.在图论中定义了凸性后，测地线问题及与之相关的测地数问题成为揭示图的结构性质的一个重要指标及参数.
本文主要研究图的测地集问题．特别是具有特定限制条件的图的测地集，如边测地集，线测地集等.同时，考虑了部分图的运算的测地集问题．
（一）在第一章中，我们首先简单介绍了图论的起源发展，介绍了测地集概念的产生背景及在图论中的推广意义及测地集问题的研究现状和进展.同时，介绍了相关问题的一些基本概念和记号．
（二）在第二章第一节，我们首先研究图的测地集的性质，介绍了测地集与图的其它结构参数的关系，并在此基础上得到了单圈图与完全r部图的测地数．
第二节，确定了一些图类的边测地数，并指出图的测地数与边测地数的关系．主要结果如下：
(ⅰ)设G为树Tn（或完全图Kn，Kn-e，Km,n，Km1，…mr及单圈图Gn）．则g(G)=ge(G)；
(ⅱ)对于任意的正整数2≤a≤b，存在连通图G使得：g(G)=a，ge(G)=b．
第三节中，研究了图的线测地集与线测地数，确定了一些简单图类的线测地集和线测地数.主要结果如下：
(ⅰ)设T是叶子数为k的n阶树，则gl(T)=七，且对T中的叶子集合任意标记下标为：S={v1，v2，…，vk}，S都构成了T的最小线测地集．
(ⅱ)设G(≠)Cn为单圈图，且种植在圈上的树不全为路，则gl(G)=g(G)．
（三）在第三章中，考虑了图的部分运算对边测地集（线测地集）的影响．主要结果如下：
设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(GuoHv)=gl(G)+gl(H)-2.