# 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)}$ ## 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 .