Maths apps- Graph theory definitions

Graph

Diagram showing lines connecting points

Vertex

One of the points in a graph

Edge

One of the connecting lines in a graph

Two vertices are adjacent if they are joined by an edge

Multiple edges

Two or more edges that connect the same vertices

Loop

An edge that joins a vertex directly to itself

Simple graph

One that has no loops or multiple edges

Degree of a vertex

The number of edges connected to that vertex (A loop is considered to be connected to its vertex twice)

The sum of the degrees in a graph will always be even since every edge joins two vertices

Directed graph

One in which all the edges have a direction- in this case the edges are usually called arcs

For an undirected graph

The sum of the degrees of the vertices equals twice the number of edges

Adjacency matrix

Shows the number of edges that join adjacent vertices

For a given network shows the number of one-step routes between the vertices eg M

M² gives number of two-step routes, M³ 3-step routes and so on

Symmetric about the leading diagonal

Means that you can go along each edge in either direction

Directed graph adjacency matrix

Shows the number of edges from one vertex to another, in that particular direction

Planar graph

A graph that can be drawn in the plane

A planar graph can always be drawn so that no two edges cross

Weighted graph

A graph in which each edge is labelled with a number used to represent some quantity associated with the edge

Connected graph

One in which there is a path between each pair of vertices, ie. a way of getting from each vertex to each other vertex via one or more edges

Bridge

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

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 K_n.

A complete graph with n vertices

Has n(n-1) / 2 edges

Subgraph

A graph that consists of some (though not necessarily all) of the vertices and edges in the original graph

Bipartite graph

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

Every subgraph of a bipartite graph is also bipartite

Complete bipartite graph

A bipartite graph where every vertex of the first set is connected to every vertex of the second set

Number of edges in a complete bipartite graph

Is m x n, where m is the number of vertices in the first group and n is the number of vertices in the second group

Bipartite graph test

Start at any vertex and colour it eg white, then colour any vertex connected to it black, then move to hose vertices and continue to process through the network until all vertices are either white or black. If any edge has two white or two black vertices at its ends, then the graph is not bipartite. If every vertex has one white and one black vertex at its ends, then the graph is bipartite

Faces

Regions in a graph bounded by the edges, including the outer infinitely large region

Euler’s rule

States that for a connected planar grate, v + f — e = 2, where v is the number of vertices, f is the number of faces and e is the number of edges

Walk

Any route in a graph from one vertex to another vertex along the connecting edges

Doesn’t have to include all the vertices/edges, can repeat vertices/edges

Open walk

A walk that starts and finishes at different vertices

Closed walk

A walk that starts and finishes at the same vertex

Length of a walk

The number of edges it includes

Trail

A walk in which no edge is repeated

Open trail

Trail that starts and finishes at different vertices

Closed trail/circuit

A trail that starts and finishes at the same vertex

Path

A walk in which all of the edges and all the vertices are different (a path may start and finish at the same vertex)

Open path

A path that starts and finishes at different vertices

Cycle/closed path

A path that starts and finishes at the same vertex

Eulerian

A connected graph that has a closed trail (starts and ends at the same vertex) that includes every edge once and once only

May include repeated vertices

Have no vertices of odd degree- each vertex must be of even degree

Semi-Eulerian

If there is an open trail that includes every edge once only

Two vertices must be of odd degree, all others even

Can only be traversed by starting at one of the odd vertices and finishing at the other

Eulerian trail

A walk with no repeated edges that includes every edge in a graph

Open/Semi Eulerian trail

Will only exist if graph has exactly two vertices of odd degree

Closed Eulerian trail

A walk with no repeated edges that includes every edge in a graph and starts and finishes at the same vertex

Will only exist if graph has all vertices of even degree

Hamiltonian path

A path that includes every vertex in a graph once only

A path cannot have repeated edges
Does not have to visit every edge

Hamiltonian cycle

A cycle that includes each vertex in a graph (except the first) once only

Hamiltonian graph

A graph that contains a Hamiltonian cycle

Semi-Hamiltonian graph

A graph that contains a Hamiltonian path but not a Hamiltonian cycle

Graph will not be hamiltonian

If it contains a bridge