Further maths - Graph definitions

Graph, vertice, nodes

a graph consists of points (vertices / nodes) which are connected by lines (edges / arcs)

Weighted graph / network

if a graph has a number associated with each edge (usually called its weight) then the graph is known as a weighted graph / network

subgraph

a graph where each vertex belongs to an original graph and each edge belongs to an original graph, it’s part of the original graph

degree/valency

degree / valency / order of a vertex is the number of edges incident to it

walk

a route through a graph along edges from one vertex to the next

path

a walk in which no vertex is visited more than once

even / odd degree

if a vertex’s degree is even it had even degree if it’s odd it had odd degree

trail

a walk in which no edge is visited more than once

cycle

a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

Hamiltonian cycle

a cycle that includes every vertex

loop

edge that starts and finishes at the same vertex

connected

two vertices are connected if there is a path between them, graphs are connected if all its vertices are connected

simple graph

a graph with no loops and there is at most one edge connecting any pair of vertices

directed edges + graph / digraph

if the edges of a graph have a direction associated with them they are known as directed edges and the graph is a directed graph / digraph

Euler’s handshaking lemma

in any undirected graph the sum of the degrees of the vertices = 2 x the number of edges ; as a result the number of odd nodes must be even

tree

connected graph with no cycles

spanning tree

subgraph which includes all the vertices of the original graph and is also a tree

complete graph

a graph in which every vertex is directly connected by a single edge to each of the other vertices

Isomorphic graph

graphs that have the same number of vertices and the degrees of corresponding vertices are the same and they’re connected in the same way

planar graph

a graph that can be drawn in a plane in a way so that no two edges meet except at a vertex to which they’re both incident

eulerian graph + cycle

a graph with every vertex of even degree, a cycle which includes every edge of a graph exactly once

semi-eulerian graph

a graph with exactly two vertices of odd degree

efficiency

measure of an algorithm’s run-time and in most cases is proportional to the number of operations that must be carried out

size

of a problem is a measure of its complexity and so in the case of algorithms on graphs it’s likely to be the number of vertices on the graph

order

of an algorithm is a measure of its efficiency as a function of the size of the problem