Graph-Theoretical Optimization Methods

Communications networks of any kind — from early telegraph and circuit-switched telephone networks to future integrated broadband networks — are represented most naturally by a graph G(V,E), where vertices, or nodes, of V are essentially switches (telephones or computer terminals) and the edges or arcs of E are the transmission links. Classification of networks, for example into local area networks (LANs), metropolitan area networks (MANs) or wide area networks (WANs), will result in a change of the technical definitions of network nodes and their geographical coverage, but the graph representation preserves the concepts of ‘interconnectivity’ and ‘reachability’ in terms of existing paths leading from any one node to any other node. This is the precise reason why graph-theoretical methods are of great importance for design and routeing in telecommunications networks.