论文部分内容阅读
正如我们所知道的，图论中的图代表很多含义。因此，图论有很多方面的应用，例如，如果一个简单无向图G=（V，E）的每个顶点代表分子中的一个原子，每条边代表原子之间形成的化学键，这种图就叫分子图。分子拓扑指数以及分子图的不变量的研究是现代化学图论中最活跃的研究领域之一。它们能够被用来描述有机化合物的物理化学特性尤其是药理特性。自从1947年H．Wiener提出第一个分子拓扑指数即Wiener指数以来，数百种分子拓扑指数，包括Randi（?）指数以及广义Randi（?）指数，在数学和化学文献中被研究。这里，图G的广义Randi（?）指数定义为 Wα（G）=sum from=（u，v）∈E[d（u）d（v）]α其中d（u）表示顶点u的度并且α为不等于0的实数．特别地，w-1／2（G）称为图G的Randi（?）指数． 除此之外，我们也通常用一个连通的（有向或无向）图G=（V，E）作为互连网络的拓扑结构，这时图G的顶点代表网络中的组件，组件之间的通信联系用相应顶点之间的连线来表示。网络中的容错路由选择的研究是网络中图论问题的研究的一个重要方向。设x和y是（强）连通（有向）图G=（V，E）中不同的顶点，PG（x，y）是G中（x，y）-路之集，P（G）={PG（x，y）：x，y∈V，x≠y)，B=V×V＼{（x，x）：x∈V}。G中路由选择定义为映射ρ：B→P（G），（x，y）→ρ（x，y）∈PG（x，y）。也就是说，映射ρ给B中的每一点对（x，y）都指定了一条（x，y）-路ρ（x，y）。ρ（x，y）称为路径，网络中的路由选择ρ是预先设计好的，因而必须通过ρ指定的那些路径来传输所有的数据。因此，当容错网络的某些结点和（或）连线发生故障时，通过那些包含这些结点（作为内部点）和（或）连线的路径来传输数据就不可能。但仍可以通过一系列幸存的路径传输数据。为了使数据传输的时间不至于太长，经过的幸存路径应该尽可能地少。对于具有给定路由选择ρ且顶点和边（或弧）故障F可能发生的通信网络G。幸存路径图的直径D（R（G，ρ）／F）是一个重要的网络容错参数，它直接反映数据传输延迟时间。 本文主要研究化学图论中的Randi（?）指数和广义Randi（?）指数以及网络中的容错路由选择问题。全文共分为五章。 第一章除了介绍一些图论术语外，还介绍了我们所研究的问题的背景以及一些已知结果。