Routing --- маршрутизация
A routing in a graph or digraph assigns to every pair of different vertices a path (a chain) from to . The paths are called routes. Given a graph , it is assumed that all communications between vertices are done through the routes of a fixed routing. Two parameters have been proposed to measure the efficiency and fault tolerance of a fixed routing in a graph or a digraph: the forwarding index and the diameter of the surviving route digraph. The vertex-forwarding index of a routing in a graph or a digraph , , is the maximum number of routes passing through a vertex. The edge- or arc-forwarding index, , is defined analogously.
For a given set of faulty vertices and/or arcs, the vertices of the surviving route digraph are the non-faulty vertices and there is an arc between two vertices if and only if there are no faults on the route between them. Fault-tolerant routings are such that the diameter of the surviving route digraph is small for any set of faults of a bounded size.