# Edge-weighted graph

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 .

## Weight functions

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 .

## Metric graph

A complete edge-weighted graph is called **metric** if for all nodes of the graph

applies. This means that the route from via to must not be cheaper than the direct route from to . An example of metric graphs distance graphs .

## Applications

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.

## See also

## Individual evidence

- ↑ Noltemeier, Hartmut: Graph Theoretical Concepts and Algorithms . 3. Edition. Vieweg + Teubner Verlag, Wiesbaden 2012, ISBN 978-3-8348-1849-2 , pp. 74 f .