设$G=(V(G),E(G))$是一个简单连通图, 记$R_G\{x,y\}=\{u|u\in V(G),d_G(x,u)\neq d_G(y,u)\}$,其中$d_G(x,y)$表示顶点$x$到顶点$y$的距离. 顶点集合$V(G)$的子集$W$称为$G$的一个可解集,如果对于任意两个不同的顶点$x$和$y$都有$R_G\{x,y\}\cap W\neq\emptyset$.含有最少元素的可解集的元素个数叫做图$G$的度量维数,记作$\mu(G)$. 度量维数的概念, 是在上个世纪70年代, 分别由Harary 和 Melter \cite{Ha},以及Slater \cite{Sl1}提出. 度量维数在网络, 组合优化, 机器人导航, 药物化学等领域都用重要的应用. Garey 和 Johnson \cite{Ga} 以及 Khuller, Raghavachari 和 Rosenfeld \cite{Kh} 都证明了计算图的度量维数是NP完备的.本文分为五章来研究图的度量维数及相关问题.第一章, 介绍度量维数的背景和应用, 并简单叙述与它有关的一些概念.第二章, 我们通过构造可解集给出双线型图的度量维数的上界, 并改进了 Babai 关于该图度量维数的上界.记$\mathbb{F}_{q}$为$q$个元素的有限域.我们用$\mathbb{F}_{q}^{n+d}$表示$\mathbb{F}_{q}$上的一个$n+d$维向量空间,取定它的一个$n$维子空间$N$. 定义双线形图$H_{q}(n,d)$如下: 它的顶点集为$\mathbb{F}_{q}^{n+d}$的所有与$N$的交为零子空间的$d$维子空间, 两个顶点相邻当且仅当它们的交为$d-1$维子空间. 注意到$H_q(n,1)$是完全图,它的度量维数为$q^n-1$;而且$H_q(n,d)$是同构于$H_q(d,n)$, 所以我们只需要考虑$n\geq d\geq 2$.事实上, Babai \cite{LB}已经得到了$\mu(H_{q}(n,d))<4\sqrt{q^{nd}}\log(q^{nd})$. 本章改进了他的上界, 得到下面的结论:当$n\geq d\geq 2$时,$\mu(H_{q}(n,d))\leq q^{n+d-1+\lfloor\frac{d+1}{n}\rfloor}$.第三章, 研究（有向和无向）线图的度量维数, 主要结论如下:(1) 如果强连通有向图$G$不是有向圈, 那么它的有向线图的度量维数$\mu(L(G))=|E(G)|-|V(G)|$, 作为推论, 我们计算出两类非常重要的有向网络---de Brujin有向图和 Kautz有向图的度量维数.(2) 如果$G$是至少有5个点的连通无向图, 则它的线图的度量维数满足下面的不等式: $\lceil\log_2\Delta(G)\rceil\leq\mu(L(G))\leq |V(G)|-2$,其中$\Delta(G)$表示图$G$的最大点度.(3) 研究了树（无向）的线图的度量维数, 并用树的其它参数表示出了它,最后发现树的度量维数与树的线图的度量维数是相等的.第四章, 计算出了图的字典积的识别码的最小值.对于$G$的任一顶点$v$,记$B_{G}(v)=\{u|u\in V(G),d_G(u,v)\leq 1\}$.如果$V(G)$的一个子集$C$满足：(i) 对于任意$v\in V(G)$,$B_{G}(v)\cap C\neq\emptyset$; (ii)图$G$中任意两个不同顶点$x$和$y$都满足$B_{G}(x)\capC\neq B_{G}(y)\cap C$, 则称$C$为$G$的一个识别码. 识别码的概念是由Karpovsky et al.\cite{Ka1}提出.注意到并不是所有的图都存在识别码, 我们把存在识别码的图叫做可识别的图, 并把识别码元素个数的最小值记作$I(G)$. 认识到识别码和可解集之间的关系, 本章推广了$\mu(G)$和$I(G)$得到另外一些参数.本章的主要结论如下:(1) 给出了两个图$G$和$H$的字典积$G[H]$存在识别码的充要条件,并用$G$和$H$的推广的参数表示出了$I(G[H])$.(2) 完全计算出了$I(G[P_n])$和$I(G[C_n])$, 其中$P_n$和$C_n$分别表示$n$阶路和$n$阶圈.第五章, 研究图的分数度量维数.度量维数的计算可以转化为一个整数规划问题, 如果把这个整数规划问题放松到线形规划问题, 就可以定义分数度量维数. 函数$f:V(G)\longrightarrow[0,1]$,对于$V(G)$的任意子集$W$,记$f(W)=\sum_{u\in V(G)}f(u)$. 如果对于$G$中任意两个不同顶点$x$和$y$,满足$f(R_G\{x,y\})\geq 1$, 则称$f$为$G$的一个可解函数.图$G$的分数度量维数$\mu_f(G)=\min\{|f||f\textup{ 是$G$的可解函数 }\}$, 这里$|f|=f(V(G))$. 分数度量维数的概念分别独立地由Currie et al. \cite{Cu} 和 Fehr et al. \cite{Fe}提出,并由 Arumugam et al.\cite{Ar} 给出了系统的定义和基本的结论.记$r(G)=\min\{|R_G\{x,y\}||x,y\in V(G),x\neq y\}$. 本章完全解决了 Arumugam et al. \cite{Aru}提出的四个公开问题, 并得到如下主要结论：(1) 如果$G$是点传递图, 则$\mu_f(G)=\frac{|V(G)|}{r(G)}$; 并用距离正则图的交叉数表示出了点传递距离正则图的分数度量维数, 进一步计算出了Hamming图和Johnson图的分数度量维数.(2) 给出了任意图$G$的度量维数与分数度量维数的一个不等式关系: $\mu_f(G)\geq\frac{|V(G)|}{|V(G)|-\mu(G)+1}$,并完全刻画了等号成立的充要条件.(3) 研究了两个图$G$和$H$的笛卡尔积$G\Box H$的分数度量维数, 并得到：$\max\{\mu_f(G),\mu_f(H)\}\leq\mu_f(G\Box H)\leq\min\{\max\{\mu_f(G),|V(H)|\},\max\{\mu_f(H),|V(G)|\}\}$.

The metric dimension of a graph is the least number of vertices in aset with the property that the list of distances from any vertex tothose in the set uniquely identifies that vertex. We study the metricdimension of bilinear forms graphs and line graphs in Chapter 2 and Chapter3, respectively. And inChapter 4 and Chapter 5, we study another two concepts---identifying codes and fractionalmetric dimension, which are related to the concept of metric dimension.