FURTHER MATHS - MWA

trail

sequence of joined edges such that no edges are
repeated

Algorithm

a precise set of instructions which if followed will solve a problem

Path

is a sequence of edges such that the ned vertex on one edge is that start of the next, no vertex is visited more than once.

Heuristic Algorithm

provide a solution to the problem but not necessarily the optimum solution

First Fit Algorithm

Take the items in the order listed and place them into the first compartment that they will fit into.

First Fit Decreasing Algorithm

List the items in decreasing order and then place apply the first fit algorithm

Full Bin Algorithm

Gather the items into groups that fully fill the compartments completely, then pack the rest efficiently. (your own choice)

Recursive Algorithm

An algorithm which repeats instructions on a previous value sorted. The instructions used will define the output of the algorithm.

Efficiency

A measure of the speed or time of operation of the Algorithm

Worst Case Scenario Comparisons

1/2n(n-1)

digraph

directed graph, in which at least one edge has a direction associated with it.

Bipartite graph

where the nodes are in two distinct sets. Every edge connects a member of the first set to a member of the second set k(4,3)

isomorphic

corresponding or similar in form and relations.

Cycle

a closed path, the first and last vertex are the same.

Planar

Graphs which can be drawn without edges crossing

complete bipartite graph Ka,b

Each vertical in group A is joined to every vertex in group B by an edge.

Leading diagonal of a matrix

Symmetrical either side

Simple graph

No loops or multiple edges

Connected graph

Every vertex is linked by at least a single edge

Simply connected graph

Every edge is connected by only a single edge

Complete graph

Simple graph in which every vertex is connected to every other by a single edge Kn
N = vertices

Formula for edges in a complete graph

1/2n(n-1)

Degree of a vertex

Number of edges which start or finish at the vertex

Handshaking theorem

Sum of degree of vertices = 2x number of edges

Tree

A connected graph in which there are no cycles

Formula for tree

# of edges is = # of vertices - 1

Spanning tree

A subgraph which includes all the vertices in the original graph but is also a tree

Eulerian graph

It is possible to make a trail that uses all edges once, starting and ending at the same vertex

Semi-Eulerian graph

It is possible to make a trail that uses all edges once, starting and ending at different vertices

When is a connected graph Traversable (Eulerian)?

If and only it has no nodes with an odd degree

When is a connected graph semi- Eulerian ?

When a graph has exactly two odd nodes