Graph Edge Weight Function

References

http://en.wikipedia.org/wiki/Weighted_graph#Weighted_graphs_and_networks
- QUOTE: A weighted graph associates a label (weight) with every edge in the graph. Weights are usually real numbers. They may be restricted to rational numbers or integers. Certain algorithms require further restrictions on weights; for instance, Dijkstra's algorithm works properly only for positive weights. The weight of a path or the weight of a tree in a weighted graph is the sum of the weights of the selected edges. Sometimes a non-edge is labeled by a special weight representing infinity. Sometimes the word cost is used instead of weight. When stated without any qualification, a graph is always assumed to be unweighted. In some writing on graph theory the term network is a synonym for a weighted graph. A network may be directed or undirected, it may contain special vertices (nodes), such as source or sink. The classical network problems include: minimum cost spanning tree, shortest paths, and maximal flow (and the max-flow min-cut theorem)

(Alon et al., 2006) ⇒ Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph (Seffi) Naor. (2006). “A General Approach to Online Network Optimization Problems.” In: ACM Transactions on Algorithms (TALG) Journal, 2(4). doi:10.1145/1198513.1198522
- QUOTE: Such problems are associated with an input graph [math]\displaystyle{ G = (V, E) }[/math] (directed or undirected), a cost function [math]\displaystyle{ c : E \rightarrow \mathbb{R}^+ }[/math], and a requirement function [math]\displaystyle{ f }[/math] (to be defined for each problem separately). The goal is to find a minimum cost subgraph that satisfies the requirement function. Our model is online; that is, the requirement function is not known in advance and it is given "step by step" to the algorithm, while the input graph is known in advance.