论文部分内容阅读
图论是离散数学的一个重要分支,它是现代电子计算机的理论基础,不论在理论上还是在现实中都扮演着重要的角色。图论的发展具有悠久的历史的,自欧拉首次给出柯尼斯堡七桥问题开始,图论吸引了一大批学者的关注与研究,不断的新的问题的提出与解决给图论发展带来了源源不断的动力与乐趣。本文主要研究一些具有简单结构的、常见的图类的距离控制数。在计算机网络中,控制数具有重要的应用,它表示控制整个网络的所需要的最少的点数,也就是所需要的最小费用。因而研究控制数具有重要的理论和现实意义。与控制数相关的一个重要概念就是束缚数,它是网络安全性能的一个重要指标。距离控制数和距离束缚数是经典的控制数和束缚数的自然推广,具有更加广阔的现实背景和意义。但确定一个图的距离控制数是一个NPC问题。因此,确定一些典型图类的距离控制数以及它们的界就显得尤为重要。这能为进一步确定其他复杂结构的图的距离控制数提供重要的界的依据。 本文第一章介绍了图论中必要的基本概念,以及控制数、束缚数的现实背景。 第二章确定了与路相关的几种笛卡尔乘积图Pn,Pn×P2,Pn×P3,Pn×Km的k-距离控制数。 第三章确定了与圈相关的图Cn,Cn×P2,Cn×P3,Cn×Km的k-距离控制数。