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

${\displaystyle d\colon E\to \mathbb {R} }$,

which assigns a real number as weight to each edge . The edge weight of an edge is then denoted by or . ${\displaystyle e\in E}$ ${\displaystyle d(e)}$ ${\displaystyle d_{e}}$

Metric graph

A complete edge-weighted graph is called metric if for all nodes of the graph ${\displaystyle a,b,c}$

${\displaystyle d({a,c})\leq d({a,b})+d({b,c})}$

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 . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle c}$

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. ${\displaystyle (G,d)}$

See also

• Magic graph

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 .