Edge-weighted graph

from Wikipedia, the free encyclopedia

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 .


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

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