Undirected Network¶

Definition¶

An undirected network is a network in which edges have no prescribed orientation. An edge joining vertices $i$ and $j$ may be traversed in either direction.

Interpretation¶

An undirected network represents connections whose availability is symmetric, such as two-way roads or cables. The edge between $i$ and $j$ is an unordered pair: it can be written $\{i,j\}$ , and $\{i,j\}=\{j,i\}$ ${j, i}$ .

A network of six vertices joined by undirected edges, which can be travelled both ways.

The figure shows the network of this week's examples without lengths: six vertices and nine edges, each of which can be travelled both ways, as the red arrow indicates. Each edge still counts once, so the network has nine edges, not eighteen.

The course uses undirected networks for spanning trees, Euler tours, the Chinese postman problem and shortest paths. Several of these first require the network to be connected, meaning that a path joins every pair of vertices.

Key Results¶

The pair $i-j$ describes one undirected connection.
A path can traverse its edges in either direction.
Connectedness requires a path between every pair of vertices.

Examples¶

An undirected edge may be written $\{i,j\}$ ; roads, cables and other symmetric links provide examples. The degree counts incident edge ends.

A two-way road connects two towns.
A cable connecting two sites can be selected as part of a spanning tree.

Prerequisites¶

Network

Sources¶

OR Modelling · Week 4

Aliases: undirected graph

Last updated: 20 October 2026 03:02