Maths

Complete Bipartite Graph

Where every vertex of the first set is connected to every vertex of the second set

Tree

A graph with only 1 face (no enclosed regions)

Adjacency Matrix (non-directed graph)

When the entry in row i column j is the number of edges joining the vertices i and j. A loop is counted as 1 edge.

Adjacency Matrix (directed graph)

When the entry in row i and column j is the number of directed edges (arcs) joining the vertex i and j in the direction i to j.

Planar Graph

Can be drawn in the plane and so that no 2 edges cross

Euler’s Formula

For a connected planar graph. Euler’s rule states that v + f - e = 2

Walk

A sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence.

Trail

A walk in which no edge is repeatedP

Path

A walk in which all of the edges and vertices are different. (i.e. no repeats, except for the first and last vertex)

Open Walk/Trail/Path

A walk/trail/path that starts and finishes at different vertices

Closed Walk/Trail/Path

A walk/trail/path that starts and finishes at the same vertex

Circuit

A closed trail

Cycle

A closed path

Eulerian Trail

A closed trail which includes every edge in the graph once (vertices can be repeated)

Eulerian Graph

A graph which contains an Eulerian trail. Contains no odd vertices

Semi - Eulerian Graph trail

An open trail which includes every edge in the graph once. Contains exactly 2 odd vertices, where the trail starts and ends

Semi - Eulerian Graph

A graph which contains a semi - Eulerian trail

Hamiltonian Path

A path which includes every vertex exactly once (except possibly the first one). No edge is repeated

Hamiltonian cycle

A closed Hamiltonian path

Hamiltonian Graph

A graph that contains a Hamiltonian cycle

Semi - Hamiltonian graph

A graph which contains an open Hamiltonian path

Traversable

A graph is traversable if it is Eulerian or Semi - Eulerian

Examples of a Network

Trails connecting campsites in a National Path or a transport network with one-way streets

Graph

Diagram that consists of a set of vertices joined by edges

Vertex/Node

Points in a graph

Edge

A line joining two vertices

Face

The faces of a planar graph are the regions bounded by the edges, including the outer infinitely large region

Adjacent Vertices

Vertices joined by an edge

Multiple Edges

2 or more edges which connect the same vertices

Loop

An edge in a graph that joins a vertex to itself

Arc

A directed edge

Degree

The number of edges that enter/exit from the vertex. Loops are counted twice. The sum of the degrees in an undirected graph will be equal to twice the number of edges

Undirected Graph

A graph where the edges are not directed

Directed Graph

A diagram comprising points, called vertices, joined by arcs. Commonly called digraphs

In/Out Degree

For directed graphs, the “in degree” is the number of edges going into a vertex and the “out degree” is the number of edges going out of the vertex

Connected Graph

A graph is connected if there is a path between each pair of vertices

Bridge

An edge in a connected graph that, if removed, leaves a graph disconnected

Simple Graph

A graph with no loops or multiple edges

Weighted Graph

A graph in which each edge is labelled with a number used to represent some quantity associated with the edge (e.g. distances, capacity)

Complete Graph

A simple graph in which every vertex is joined to every other vertex by an edge. The complete graph with n vertices is denoted by Kn

Subgraph

When the vertices and edges of a graph A are also vertices and edges of the graph G, graph A is said to be a subgraph of graph G

Bipartite Graph

A graph whose set of vertices can be split into two distinct groups so that each edge of the graph joins a vertex in the first group to a vertex in the second group.