Routing

Материал из WikiGrapp
Перейти к:навигация, поиск

Routing --- маршрутизация

A routing \rho in a graph or digraph G assigns to every pair of different vertices a path (a chain) \rho(x,y) from x to y. The paths \rho(x,y) are called routes. Given a graph G, 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 \rho in a graph or a digraph G, \xi(G,\rho), is the maximum number of routes passing through a vertex. The edge- or arc-forwarding index, \pi(G,\rho), is defined analogously.

For a given set F 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.