Algorithm
A set of precise and step-by-step instructions used to solve a problem with a clear input and output. It must terminate
Heuristic algorithm
Does not give an optimal solution, but a sufficient one
Graph
A finite set of points connected by lines
Degree of a vertex
The number of edges leaving the vertex
Handshake lemma
The sum of the degrees of all the vertices is twice the number of edges, so is always even
Simple graph
A graph with no loops or multiple edges
Connected graph
Every vertex is connected by one edge/ a sequence of edges to every other vertex
Complete graph
A simple graph where every pair of nodes is connected by an edge
Subgraph
A part of a graph which is itself a graph
Digraph
A graph where edges have directions
Planar graph
A graph that can be drawn so that none of the arcs cross
Kruskal’s algorithm
An algorithm that
Prim’s algorithm
Maximum capacity
Maximum flow
Minimum flow
Cuts
Value
