Modeling with Algorithms - Chapter 2: Graphs

Graph

Graph

Consists of a finite set of vertices connected by edges

Edge

Joins one vertex to another

Loop

Where an edge starts and ends at the same vertex

Multiples edges

When there is more than one edge joining the same pair of vertices

Simple graph

there are no loops or edges

Connected graph

Every vertex is linked by a single edge

Completed graph

Simple graph where every vertex is connected to every other by a single edge

Degree

Number of edges that start or finish at a vertex

Handshaking theorem

Total degrees of vertices = 2 x edges

Digraph

When the edges of a graph have a direction associated with them

Subgraph

Part of a graph which is a graph in itself