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

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

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 which show the same information but may be drawn differently