Decision Maths - Edexcel

Activity

A job or process that forms part of an overall project.

Adjacency Matrix

A way of representing a graph on a matrix. Rows and columns respond to vertices, and the entries in the matrix correspond to the number of edges from one vertex to another.

Algorithm

A sequence of precise instructions to solve a problem.

Complete graph

A simple graph in which every pair of vertices is connected by an edge.

Connected graph

A graph is connected if a path exists between every pair of vertices.

Critical activity

An activity with no float - any delay to a critical activity will result in a delay for the whole project. A critical activity must lie on a critical path.

Critical path

A route through a precedence network on which all of the activities are critical activities.

Cycle

A closed path (the end of the last edge is the start of the first edge and no vertices are repeated except that the final vertex is the same as the first).

Degree / Order / Valency of a vertex

The number of edges connecting to it.

Digraph

A graph in which at least one edge has direction associated with it.

Distance table

A tabular representation of a network, in which each element represents the weight of the arc between two nodes on the network.

Edge

A line connecting two vertices (nodes) on a graph.

Eulerian graph

A graph in which it is possible to traverse each edge once, starting and finishing at the same vertex (all vertices have even valency).

Eulerian cycle

A cycle that includes each edge of a graph exactly once.

Even vertex

A vertex where an even number of edges meet

Event

An event occurs when an activity can start, or when a whole project is complete (represented by nodes on an activity network).

Feasible region

A region on a graph where all the constraints in a linear programming problem are satisfied.

Float

The amount of time by which an activity can be delayed without affecting the completion time of the project.

Flowchart

A diagrammatic representation of the sequence of steps in an algorithm (in a clear and economical way).

Graph

A set of vertices, linked with a set of edges.

Isomorphic

Two graphs are isomorphic if one can be stretched, twisted or otherwise distorted into the other.

Loop

An edge whose beginning and end both link into the same vertex.

Minimum spanning tree

A tree that connects all the nodes of a network together using the minimum total arc length.

Network

A weighted graph (has a weight associated with each arc).

Objective function

The value of the quantity you wish to maximise or minimise in a linear programming problem.

Objective line method

The optimal solution in a linear programming problem with the objective function ax+b may be solved from its graph by drawing the line ax+b=c, which lies within the feasible region, and then moving the line parallel to this line as far (upwards if maximising, downwards if minimising) as possible within the feasible region.

Odd vertex

A vertex where an odd number of edges meet

Optimal solution

The set of values of the variables that maximise or minimise the value of the objective function while satisfying all the constraints (it will always lie in the feasible region).

Path

A finite sequence of edges, so that the end of one edge is the start of the next, and in which no vertex is repeated.

Precedence network

A network drawn to show how the activities in a project are dependent upon each other. Activities are represented by arcs.

Precedence table

A table listing the activities involved in a project, showing all the dependencies of activities on other activities.

Project

This is the overall task to be analysed using critical path analysis, A project is made up of a number of different activities.

Semi-eulerian

A graph is semi-eulerian if it is possible to find a route in which each edge is traversed once only, starting and finishing at different vertices. This is only the case if all the vertices are even vertices except for the start and finish vertices, which are odd.

Simple graph

A graph in which there are no loops and in which there is no more than one edge connecting any pair of vertices.

Solution to a linear programming problem

Any set of values for the decision variables that satisfies all the constraints.

Sorting algorithm

Sorts a list into order.

Source node

This is the event node that represents the event that occurs at the beginning of a whole project. The earliest event time and latest event time for the source node is zero.

Spanning tree

A tree which includes all the vertices of the graph.

Subgraph

A subset of the vertices of a graph, together with a subset of edges.

Traversable

A network where all the nodes can be connected and the same edge cannot be traced twice (if it has zero or two odd vertices, the network is traversable - it is therefore either eulerian or semi-eulerian).

Tree

A simple connected graph with no cycles.

Vertex

A point on a graph that is connected to other vertices by edges.

Vertex set

The set of all the vertices of a graph

Walk

A sequence of edges in which the end of each edge, is the beginning of the next.

Weight

A numerical value associated with an arc on a network.