Modeling with Algorithms - Chapter 2: Graphs

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 multiple 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

Planar Graph

A graph that can be drawn without any edges crossing

Bipartite Graphs

Where there are two discrete sets of vertices with edges only joining vertices between sets and not within a set

Complete bipartite graph

In which each vertex in A is joined to every vertex's in B (K(R,S))

Isomorphic

Same number of vertices and edges with same degrees