1736年，Euler解决哥尼斯堡七桥问题标志着图论的诞生.今天，图论在计算机科学、通讯科学、化学、生物学、物理学等学科的应用已经是众所周知的。 在交通系统中应用单行道不仅是改善城市交通堵塞状况的经济而有效的方法，而且提高了交通安全，减轻了交通管理工作.单行道问题的图论模型最初由Robbins提出，单行道问题可以归结为图的定向问题.Chartrand等人提出了强定向图中强距离的概念.设G是一个二边连通图，D是G的一个强定向.D中任两个顶点u，υ间的强距离sd(u，υ)为D中包含u，υ的最小强有向子图的弧数.点u的强离心率se(u)定义为u与图中其他所有点的强距离的最大值.强定向图D的强半径srad(D)(强直径sdiarn，(D))定义为图中所有点的强离心率的最小值(最大值).二边连通图G的最小强半径srad(G)(最大强半径SRAD(G))为G的所有强定向图的强半径的最小值(最大值).相应地，G的最小强直径sdiam(G)(最大强直径SDIAM(G))为G的所有强定向图的强直径的最小值(最大值).确定一个图G的srad(G)、SRAD(G)、sdiam(G)和SDIAM(G)这四个参数的问题是图论研究中有重要应用背景的前沿课题。 由于对计算机运算性能日益增长的需求，多处理器计算机正在被广泛使用.网格结构是多处理器计算机系统互连的拓扑结构，它已被证明拥有许多吸引人的特性.并行计算机使用网格作为基本架构已有多年.网络中的路由是指将消息从源节点(处理器)经过一些中间节点最终传递到目标节点的过程.当网络中存在故障时，设计路由算法使消息绕过故障点最终到达目标点具有客观重要意义。 本文研究强定向图的强距离及网格的容错自适应路由.对满足Ore条件的图，给出了最小强半(直)径、最大强半(直)径的上、下界；对笛卡尔乘积图G1×G2，确定了G1×G2的最小强半(直)径与G1×G2的半(直)径以及G1和G2的最小强直径之间的关系，并进而确定了一些特殊笛卡尔乘积图的最小强直径的值，确定了SDIAM(Km×Kn)的值，SDIAM(Pm×Pn)的下界，SRAD(Km×Kn)和SRAD(Pm×Pn)相应的上、下界.对于以网格作为并行计算机拓扑结构的多处理器计算机系统的容错自适应路由的研究，本文提出了裂痕故障块模型，在此模型下，所有的故障都包含在块的内部.当块形成时，可以由每个节点的状态判断该点所处的位置-在块的边界、块的内部或块的外部.对块的内部点及边界点设计了新的特殊路由，对块外部的点仍采用一般路由方案，并证明所给的路由方案一定能克服活锁状态将消息送到目标节点。 全文共分为五章。 在第一章，我们首先给出本文的基本概念和符号，综述了本文研究领域的已有结果和本文的主要结论。 在第二章，我们研究Ore图G的最小强半(直)径srad(G)(sdiam(G))、最大强半(直)径sRAD(G)(sDIAM(G))的上、下界，得到以下结论：g≤srad(G)≤5， g≤sdiam，(G)≤9，[n2]≤SRAD(G)≤n， n≤SDIAM(G)≤n+1，其中n，g分别为G的顶点数和围长。 在第三章，研究了笛卡尔乘积图G1×G2的最小强半(直)径，证明了如下结果：srad(G1×G2)=2r(G1×G2)，sdiam，(G1×G2)≤min{sdiam(G1)+sdiam(G2)，2d(G1×G2)，4r(G1×G2))；给出sdiam(G1×G2)=2d(G1×G2)成立的三个充分条件，并由所给出的充分条件确定了一些特殊笛卡尔乘积图的最小强直径的值；确定了SDIAM(Km×Kn)的确切值，SDIAM(pM×Pn)的下界， SRAD(Km×Kn)和SRAD(Pm×Pn)的上、下界。 在第四章，我们给出了二维网格的容错自适应路由.当网格中存在故障时，原有的贪婪路由方案不一定能将信息送到目标点，可能陷入活锁状态(信息在网络的某子网络循环，到不了目标点).为此，我们设计了算法，用以构造网络中的不交的极小故障块，使得块的边界和块外部没有故障，同时，当块形成时每个节点有相应的稳定状态，可以根据点的稳定状态判断它的位置一位于块的外部、块的边界或块的内部.在我们的容错路由方案里，处于块边界及内部的点都有特殊的路由，并证明了给出的路由方案一定能克服潜在的活锁状态，将信息送到目标点.与这方面的现有算法最大的区别在于，在我们的方案里，故障块内部的点也可以成为目标点或源点.这是网络容错性方面的一个显著的提高。 在第五章中，我们将二维网格中的故障块模型推广到多维网格中，给出相应的容错自适应路由，并证明了所给出的自适应路由不会产生活锁状态。 另外，在每一章中，我们都给出了相关的发展前景和展望。