Further maths- Decision and definitions

Algorithm

a finite sequence of step-by-step instructions carried out to solve a problem

How are unordered lists sorted?

bubble sort or quick sort

A graph

consists of points (called vertices or nodes) which are connected by lines (edges or arcs)

Weighted graph or network

A graph that has a number associated with each edge

Vertex or vertices or nodes

a point on a graph

An edge or arc

a line segment joining vertices

Vertex set

A list of vertices

Edge set

a list of edges

A subgraph

a graph of each of whose vertices and edges belongs to another graph

A degree or valency or order of a vertex

the number of edges incident to it

A walk

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

A path

A walk in which no vertex is visited more then once

A trail

a walk in which no edge is visited more than once

A cycle

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

A Hamiltonian cycle

a cycle that includes every vertex

A connected graph

all vertices are connected

A loop

an edge that starts and finishes at the same vertex

A simple graph

is one in which there are no loops and there is at more one edge connecting any pair of vertices

directed graph or digraph

a graph in which the edges have a direction associated with them.

Euler’s handshaking lemma

Any undirected graph that the sum of degrees of the vertices is equal to 2x the number of edges. As a consequence, the number of odd vertices must be even, including the number zero

A tree

a connected graph with no cycles

A spanning tree

a subgraph which includes all the vertices and is also a tree

A complete graph

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

An isomorphic graph

graphs which show the same information but may be drawn differently

Adjacency matrix

describes the number of arcs joining the corresponding vertices

A distance matrix

the entries represent the weight of each arc, not the number or arcs

A planar graph

one that can be drawn in a plane such that no two edges meet except at a vertex

Kruskal’s algorithm

used to find a minimum spanning tree

Prim’s algorithm

used to find a minimum spanning tree

Dijkstra’s algorithm

used to find the shortest path through a network

Floyd’s algorithm

used to find the shortest pair between every pair of vertices in a network

Eulerian graph or network

one which contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph whose vertices are all even is eularian.

A semi-Eulerian graph or network

one which contains a trial that includes every edge but starts and finished at different vertices. Any connected graph with exactly two odd vertices is semi-Eulerian

A walk in a network

A finite sequence of edges such that the end vertex of one edge is the start vertex of the next

A tour

A walk in which visits every vertex and returns to its starting vertex