"A network is a group of system of interconnecting objects which can be represented as a diagram of connected lines (called edges) and points (called vertices). For example a rail network."

Image: London Tube Map

See Resources and Bonus Activities for examples.

"A network diagram is a representation of a group of objects called vertices that are connected together by lines called edges.

Also known as: network graph, graph

'Network diagram' should be used instead of 'graph', as it can be confused with graphs of functions.

Network diagrams are generally not drawn to scale.

"A vertex is a point in a network diagram at which lines of pathways (called edges) intersect or branch."

Also called: node, object, point
Image: Vertices shown in red

Not to be confused with vertices from Geometry (point where two lines meet, forming an angle).

The set of vertices can be labelled as such: V = {A, B, C, D, E} where, e.g. A, is the label of the vertex.

"In a network diagram, an edge refers to a line which joins vertices to each other.

Also called: arc, link, line
Image: Edges shown in blue

Not to be confused with edges from Geometry (line segment joining two vertices in a polygon or polyhedron).

Edges can cross each other without intersecting at a vertex. Two vertices can be connected to each other by multiple edges. Vertices may also be connected to itself by loops (i.e. the edge starts and ends at the same vertex).

The set of edges can be labelled as such: E = (A,B), (B,C), (A,C) where, e.g. (A,B), is the label of the edge joining vertices A and B.

The degree of a vertex is equal to the number of edges that connect to the vertex.

The degree of a vertex is either even or odd, determined by the number of edges attached to the vertex.

Loops count as one edge but contribute two to the degree of a vertex.

The degree of a vertex A can be written as such:
deg(A) = 3.

"A directed network is a network whose edges have arrows and travel is only possible in the direction of the arrows."

Edges with arrows indicating direction of travel are called directed edges.

An undirected edge has no arrow; travel is possible in both directions. A network with all undirected edges is called an undirected network.

"A weighted edge is an edge of a network diagram that has a number assigned to it which implies some numerical value such as cost, distance or time."

"A path in a network diagram is a walk in which all of the edges and all the vertices are different. A path that starts and finishes at different vertices is said to be open, while a path that starts and finishes at the same vertex is said to be closed. There may be multiple paths between the same two vertices."

"A shortest path in a network diagram is a path between two vertices in a network where the sum of the weights of its edges are minimised."

Image: shortest path shown using green vertices and black arrowheads

"A tree is an undirected network in which any two vertices are connected by exactly one path."

"A spanning tree of an undirected network diagram is a tree which includes all the vertices of the original network connected together, but not necessarily all the edges of the original network diagram. A network can have many different spanning trees."

Image: spanning tree shown in red

"A minimum spanning tree is a spanning tree of minimum length in a connected, undirected network. It connects all the vertices together with the minimum total weighting for the edges."

Image: minimum spanning tree shown in red

The weight of this minimum spanning tree is calculated by summing the weights of the edges included.

"Prim's algorithm determines a minimum spanning tree for a connected weighted network."

See: Lesson 7

"Kruskal's algorithm finds a minimum spanning tree for a connected weighted network graph."

See: Lesson 8

Dijkstra's algorithm finds the shortest path between two vertices for a connected weighted network graph.

See: Lesson 10