| 【中文题名】 | 关于图的测地数若干问题的研究 |
| 【英文题名】 | The Study of Some Problems on the Geodetic Numbers of the Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-13 |
| 【中关键词】 | 凸集,测地集,测地数,割点,笛卡儿积, |
| 【英关键词】 | Convex set,Geodetic set,Geodetic number,Cut-vertex,Cartesian product, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
图的测地数是揭示图的结构特性的一个重要参数。图的测地数源于几何学、拓扑学和函数分析中的凸集理论，是凸集理论在图论中的应用和推广，也与图论中“路覆盖”和“路分解”等问题相关联。
本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工作，主要的工作包括以下四个部分：(1)给出图的最小测地集与割点之间的关系；(2)讨论了图T_n(K_d)和T_n(C_d)的测地数；(3)研究了G∨H的测地数及其上测地数和下测地数；(4)讨论了G×P_3的测地数。
在第二章中，介绍了无向图的测地数，我们主要做了以下的工作：
我们研究了含有割点的图的测地集，并得到相关结论：图的最小测地集都不包含它的割点，这个结论是对文献[8]中有关树T_n测地数这一内容的推广；在[8]中，Grary Chartrand，Frank Harary和Ping Zhang证明了g(K_n)=n，我们推广了这个结论得到：如果图G有n≥3个顶点和k个割点，并且G的每个块都是完全图，那么g(G)=n-k。
我们定义了一个新图T_n(H)。若T_n表示顶点为n≥2的树，H为一个图，则T_n(H)表示如下构造得到的图... |
| 【论文题纲】 |
|
论文摘要 |
6-8 |
|
ABSTRACT |
8-11 |
|
第一章 绪论 |
11-19 |
|
§1.1 引言 |
11 |
|
§1.2 基本概念 |
11-15 |
|
§1.3 问题的引入 |
15-17 |
|
§1.4 主要研究结果 |
17-19 |
|
第二章 无向图的测地数 |
19-25 |
|
§2.1 无向图测地数的性质 |
19-22 |
|
§2.2 特殊无向图的测地数 |
22-25 |
|
第三章 有向图的测地数 |
25-34 |
|
§3.1 有向图测地数的若干性质 |
25-26 |
|
§3.2 图的上(下)测地数 |
26-29 |
|
§3.3 图的上、下测地数及测地数之间的关系 |
29-33 |
|
§3.4 图的测地谱 |
33-34 |
|
第四章 图的笛卡儿积的测地数 |
34-39 |
|
§4.1 图的笛卡儿积 |
34 |
|
§4.2 图的笛卡儿积的测地数 |
34-39 |
|
作者申请硕士学位期间完成的工作 |
39-40 |
|
参考文献 |
40-42 |
|
致谢 |
42 |
|
| 【DOI】 | LunWen.ID:2.2008.11799 |
