An edge-weighted graph , weighted graph for short , is a graph in graph theory in which a real number is assigned as the edge weight to each edge . Edge-weighted graphs can be directed or undirected. A graph whose nodes are weighted is called a node-weighted graph .
Edge weights are generally given by an edge weight function. One such weight function is a mapping of the shape
which assigns a real number as weight to each edge . The edge weight of an edge is then denoted by or .
For many graph-theoretic problems, additional parameters are required, for example a cost function for determining shortest paths or a capacity function for determining maximum flows . In such a case, a problem instance is often described by a tuple of the form which, in addition to the graph, contains the desired weight function.
- Noltemeier, Hartmut: Graph Theoretical Concepts and Algorithms . 3. Edition. Vieweg + Teubner Verlag, Wiesbaden 2012, ISBN 978-3-8348-1849-2 , pp. 74 f .