Numerical Methods for Unary Optimization
- PDF / 10,378,926 Bytes
- 118 Pages / 594 x 828 pts Page_size
- 21 Downloads / 266 Views
I. Intuitively speaking, a network is a set of points and a set of connections where each connection joins one point to another and has a certain length. The combinatorial structure of such a network is described as a graph G which is defined to be a pair (V, E) where • V is any finite set of elements, called vertices, and • E is a finite family of elements which are unordered pairs of vertices, called edges. Additionally, assume that a function l: E --+ R is given for the edges of the graph G. Usually, assume that l has only positive values and call it a length-function. A (connected) graph equipped with a length-function is called a network. The length of a subgraph G' = (V ~, E~), V ~ C V, E ' C_ E 71 (y'), of the network G is defined as
L(G') := ~
l(e).
eEE I
Each network G = (V, E) with the length-function l: E --+ R is a metric space (V, p) by defining the distance function in the way that p(v,v ~) is the length of a shortest path between the vertices v and v ~ in G. T h a t means that p: V × V --+ R is a real-valued function satisfying: i) p(v,v ~) >>O for all v, v l i n V ; ii) p(v, v ~) = 0 if and only if v = vt; iii) p(v, v') = p(v', v) for all v, v' in V; and iv) p(v, v') < p(v, w) + p(w, v') for all v, v', w in
V (triangle inequality). The problem of finding shortest paths in a graph with a length-function is an important and wellstudied problem. Such a p a t h is easy to find by an algorithm created by E.W. Dijkstra [7]: PROCEDURE shortest path InputInstance(); Start with the vertex v; Label the vertex v with 0: L(v) = 0; REPEAT Select an edge ww' between a labeled vertex w and an unlabeled vertex w~ such that the quantity L(w) + l(ww') is minimal as possible; Label w': L(w') = L(w) + l(ww') UNTIL v' is achieved END shortest path; A pseudocode for a procedure finding a shortest path between two vertices v and v' in a network. Assume that the procedure runs if all vertices of the network are achieved then the procedure creates a spanning tree rooted at the vertex v containing shortest paths from v to every vertex. More-
Network design problems over, the label L(w) denotes the distance from v to w, in other terms, p(v, w) = L(w). Conversely, each finite metric space can be represented as a graph with a nonnegative lengthfunction [23]. Graphs lend themselves as natural models of transportation as well as communication networks. Consequently, it is natural to study network design problems such as optimal facility location problems for graphs and as graphs in metric spaces. The core network design problem is the minimum spanning tree problem, where one wish to design a minimum cost network contains a path from each vertex to each other. Such a network must be a tree, which is called a minimum spanning tree (MST). Creating a minimum spanning tree is the problem one has the longest history of all ND problems, starting with O. Borflvka [2] in 1926. See [19] for an excellent historical survey. All the known efficient minimum spanning tree algorithms are special cases of a general greedy method, in which
Data Loading...
