From ProofWiki
(Redirected from Definition:Weighted Graph)
Jump to navigation Jump to search


A network $N = \struct {G, w}$ is:

a graph or digraph $G = \struct {V, E}$

together with:

a mapping $w: E \to \R$ from the edge set $E$ of $G$ into the set $\R$ of real numbers.

Weight Function

Let $N = \left({V, E, w}\right)$ be a network.

The mapping $w: E \to \R$ is known as the weight function of $N$.

A general network can be denoted $N = \struct {V, E, w}$ where the elements are understood to be expressed in the order: vertex set, edge set, weight function.


Let $N = \struct {V, E, w}$ be a network with weight function $w: E \to \R$.

The values of the elements of $E$ under $w$ are known as the weights of the edges of $N$.

The weights of a network $N$ can be depicted by writing the appropriate numbers next to the edges of the underlying graph of $N$.

Directed Network

A directed network is a network whose underlying graph is a digraph:


Undirected Network

An undirected network is a network whose underlying graph is an undirected graph:



A loop-network (directed or undirected) is a loop-graph together with a mapping which maps the edge set into the set $\R$ of real numbers.

That is, it is a network which may have loops.

Also known as

A network $N = \struct {\struct {V, E}, w}$ is also known in some contexts as a weighted graph.

Hence the elements of the codomain of $w$ are known as the weights of the elements of $E$.

Whether network or weighted graph is used usually depends on the particular application of network theory or graph theory under discussion.

Also see

Let $f$ be the associated mapping from the edge set $E$ to $\Z_+$.

Then let $u v$ be an edge in $E$.

We create a graph by drawing $\map f {u v}$ edges between each vertex $u$ and $v$.

  • Results about networks can be found here.

Linguistic Note

The word network is used in the context of a graph with a weight function because of its connection with the concept in the context of electronics.