Network¶

Definition¶

A network consists of a set of vertices and edges connecting specified pairs of vertices. Vertices represent entities or locations; edges represent connections. Depending on the problem, edges may have directions and numerical values such as distances, costs, or capacities.

Interpretation¶

A network separates the connection structure of a problem from its physical setting: it records only which pairs of objects are joined and, where needed, a number on each connection. The same representation can describe roads between cities, cables between sites or the order of project activities.

The figure has six vertices $A,\dots,F$ and nine edges, each labelled with its length; only these numbers count, not the lengths on paper.

Edges may be usable in both directions, as in an undirected network, or in one direction only, as in a directed network. An edge value is read in the problem's own units: a distance is added up along a path, while a capacity limits how much can pass through a single edge.

Key Results¶

• Vertices are also commonly called nodes.
• An edge may be used only in its specified direction in a directed network.
• The meaning of an edge value depends on the problem: distance and capacity are different quantities.

Examples¶

The figure has vertices $\{A,\ldots,F\}$ and edge labels denoting lengths.

• A road network connects cities by roads.
• A project network represents activities and their precedence relations.

Prerequisites¶

• No additional prerequisites.

Related Concepts¶

• Directed Network
• Undirected Network
• Path in a Network
• Vertex Degree

Sources¶

• OR Modelling · Week 4

Keywords: graph

Last updated: 20 October 2026 03:02