AHL 3.14 (HL)—Graph theory basics

A graph consists of vertices and edges representing objects and connections. Edges may be directed or undirected and weighted or unweighted, depending on the relationship being modelled.

The degree counts incident edges; a path records a route and a cycle returns to its start. Choose the graph type to match whether direction, capacity or cost matters.

In a delivery network, a one-way road needs a directed edge and travel time needs a weight. Treating it as an unweighted undirected graph can permit an impossible or misleading route.

A graph edge is not automatically a physical straight line. State what vertices and edges mean before interpreting an algorithm's result.

Graph checklist: a simple graph has no loops or parallel edges; a complete graph joins every pair of distinct vertices; a subgraph uses selected vertices and edges; a tree is connected and has no cycles. In a directed graph distinguish in-degree from out-degree. Connected means every vertex pair is linked by a path in an undirected graph; strongly connected means directed paths exist in both directions between every pair.