图论的产生最早可追溯到十八世纪三十年代,其标志性事件是瑞士数学家莱昂哈德.欧拉(Leonhard Euler,1707年4月15日-1783年9月18日)解决了哥尼斯堡七桥问题,这篇文章的发表被公认为是图论产生的里程碑。自二十世纪五十年代以来,计算机科学的迅猛发展大大地推动了图论的发展。现在,图论已经成为离散数学的一个骨干分支,它不仅具有重要的理论价值,而且具有重要的应用价值。其在化学、信息学、网络设计、管理科学、通信工程、计算机科学以及生物信息学等领域都得到了广泛应用。图的哈密尔顿性、染色理论以及最短路问题作为图论中的经典问题,得到了大量图论专家的关注。本文主要研究谢尔宾斯基相关图类的哈密尔顿性、染色理论以及最短路问题,其中染色理论包括路染色、线性染色以及2-距离染色。谢尔宾斯基相关图类与拓扑分形理论、汉诺塔数学理论及计算机科学等都有密切的联系。下面,首先介绍谢尔宾斯基相关图类S(n,k)、S+(n,k). S++(n,k)和s[n,k]的定义。谢尔宾斯基图S(n,k)(n,k≥1)的顶点集是由整数1,2….,κ的所有的n元组构成的,即V(S(n,k))={1,...,k)n。两个不同的顶点u=(u1,u2,...,un.)和v=(v1,u2,...,vn)相邻当且仅当存在一个h∈[1,n]使得下面三个条件成立：(a)ut=vt,其中t∈{1,...,h-1};(b)uh≠vh;(c)ut=vh和vt=uh,其中t∈{h+1,...,n}。在S(n,k)中,顶点(i,...,i),i∈{1,...,k},称为谢尔宾斯基图S(n,κ)的极点；形如(i,j,...,j)或者(i,...i,j)的顶点称为S(n,κ)的几乎极点。把不属于任何一个完全图的边称为桥边图S+(n,k)(n,k≥1)是在谢尔宾斯基图S(n,κ)的基础上,添加一个新的顶点ω和所有连接ω与S(n,κ)的k个极点的边得到的图。对于图S++(n,k),令S++(1,k)≌Kk+1;图S++(n,k)(n≥2,k≥1)的顶点集合V(S++(n,k))=V(S(n,k))∪V(S(n-1,k)),边的集合E(S++(n,k))=E(S(n,k))∪E(S(n-1,k))∪M,其中,M是一个含有κ条边的匹配,并且M中每条边的两个端点分别是S(n,κ)的一个极点和S(n-1,k)的一个极点。图S[n,k]是通过收缩谢尔宾斯基图S(n,κ)中所有桥边得到的图。给定一个图G,如果G中的一条路遍历了它所有顶点,则称这条路为图G的一条哈密尔顿路。类似的,若图G中的一个圈遍历了它的所有顶点,则称这个圈为图G的一个哈密尔顿圈。若G中存在一个哈密尔顿圈,则称G为哈密尔顿图。图G的一个t-染色就是一个映射φ:V(G)→{1,...,t)。给定图G的一个t-染色φ,我们用φ-1(i)记图G中染色为i的顶点的集合,并把图G中φ-1(j)的导出子图记为G[φ-1(i)]。如果每一个G[φ-1(i)],i∈{1,...,t},是图G的一个独立集,那么称φ为图G的一个正常t-染色。图G的色数x(G)就是使图G存在一个正常t-染色的最小的t。如果每一个G[φ-1(i)],i∈{1,...,t),是图G的一个线性森林,那么称φ为图G的一个路t-染色,其中,线性森林指的是每个连通分支都为路的图。图G的点线性荫度vla(G)就是使图G存在一个路t-染色的最小t。换句话说,图G的点线性荫度vla(G),就是划分它的顶点集所需要的顶点子集的最小个数,同时满足每个顶点子集在G中的导出子图为一个线性森林。如果每一个G[φ-1(i)∪φ-1(j)],i,j∈{1,...,t),是图G的一个线性森林,那么称φ为图G的一个线性t-染色。图G的线性色数lc(G)就是使图G存在一个线性t-染色的最小的t。图G的2-距离染色就是对图G的顶点进行染色使距离至多是2的顶点染不同的颜色。给定一个图G,对于任意两个顶点u,v∈V(G),u与v之间的最短路就是连通它们的长度最小的路。本文讨论了谢尔宾斯基相关图类S(n,k).S+(n,k).S++(n:k)和S[n,k]的哈密尔顿性、染色问题和最短路问题。具体说来,主要研究了谢尔宾斯基相关图类的哈密尔顿性、路染色、线性染色与谢尔宾斯基图S(n,κ)的2-距离染色和最短路问题。本文内容共分为四章。第一章,首先,介绍了一些图论中基本的概念、术语和符号；然后,给出了谢尔宾斯基相关图类的定义及研究现状；最后,列出了本文所得到的主要结果。第二章,分别确定出了S(n,k).S+(n,k)和S++(n,k)中边不交的哈密尔顿路和哈密尔顿圈的个数。第三章,研究了谢尔宾斯基相关图类的路t-染色、线性染色和2-距离染色。第四章,主要讨论了谢尔宾斯基图S(n,κ)中的最短路问题。完全确定出了Su={u∈V(S(n,k)):在S(n,k)中存在两条最短的u,v-路},其中,u是S(n,κ)的任意一个几乎极点。此外,对于S(n,3),我们找到了(n-3)·3n+3·2n对顶点使得每一对顶点之间存在两条不同的最短路并且刻画出了它们的特征,从而给出了S(n,3)中关于两个顶点之间有两条最短路的一个充分条件。