Edexcel D1 Definitions

HideShow resource information
• Created by: OctaviaL
• Created on: 14-06-16 20:24
Activity Network
Provides a visual representation of a project. The activities are represented by arcs or edges and the completion of those activities, known as events, are represented by nodes.
1 of 55
Algorithm
A precise set of instructions that will allow anyone, including a computer, to use it to achieve a particular goal in a specified number of steps.
2 of 55
Arc
A curved line connection points (nodes or vertices) on a graph.
3 of 55
Bin packing
Refers to problems that involve the packing of objects into well defined regions called bins, so that they do not overlap. The main purpose is to make efficient use of the available space.
4 of 55
Binary search
A technique for locating a particular value in a sorted list by finding the median value and comparing it to the target value.
5 of 55
Bipartite graph
A graph consisting of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. (If there are r vertices in X and s vertices in Y then this graph in Kr,s.)
6 of 55
Bubble sort
A simple sorting procedure that begins by ordering the first and second items, then the second and third, and so on, until the end of the set is reached. The process is repeated until all items are correctly ordered.
7 of 55
Circuit
A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge. (Same as a cycle.)
8 of 55
Complete graph
A graph in which each of the n vertices is connected to every other vertex.
9 of 55
Complete matching
A matching where every member of the first set X is paired with a member of the second set Y.
10 of 55
Connected
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.
11 of 55
Constraints
In linear programming, constraints relate to the decision variables and limit the number of possible values they could take. The constraints will depend on the specific context of the problem.
12 of 55
Critical activity
An activity where any increase in its duration results in a corresponding increase in the duration of the whole project.
13 of 55
Critical path
A path from the source node to the sink node which entirely follows critical activities. A critical path is the longest path contained in the network. It is possible for a project to have more than one critical path.
14 of 55
Cycle
A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge. (Same as a circuit.)
15 of 55
Decision variable
In linear programming, these are the quantities whose optimal values need to be found to solve the problem.
16 of 55
Degree
The degree or valency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degree.
17 of 55
Digraph
A graph with directed edges.
18 of 55
Dijkstra's algorithm
An algorithm that finds the shortest paths from a single source vertex to all other vertices in a directed graph.
19 of 55
Directed edges
If the edges of a graph have direction associated with them they are known as directed edges and the graph is known as a digraph.
20 of 55
Dummy activity
In critical path analysis a dummy activity is represented by a dotted line to show that a given activity also depends on another activity. The line has no 'time' or 'cost' value.
21 of 55
Earliest (or early) event time
The earliest time at which all of the dependent events may be completed, allowing the event in question to begin. Early event times are calculated using a forward scan.
22 of 55
Edge
A line on a graph connecting two nodes.
23 of 55
End node
The last point in a network.
24 of 55
Even vertex (or node)
A vertex is even if it has even degree.
25 of 55
Feasible solution
In linear programming, a feasible solution is found when the values of the decision variables satisfy all constraints.
26 of 55
Feasible region
In graphical linear programming, the refion that contains all the feasible solutions.
27 of 55
Provides a graphical way to represent the range of possible start and finish times for all activities on a single diagram. It can be used to find the minimum number of workers needed to complete a project in the critical time.
28 of 55
Graph
A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs).
29 of 55
Kruskal's (greedy) algorithm
An algorithm used to find the minimum spanning tree of a network. Uses a different method to Prim's algorithm.
30 of 55
Latest (or late) event time
The latest time at which any of the dependent events may be completed without delaying the project. Late event times are calculated using a backward scan.
31 of 55
Matching
A matching is the pairing of some or all the elements of one set, X, with elements of a second set, Y.
32 of 55
Maximum matching
A matching where the number of pairings between the elements of one set, X, with the elements of a second set, Y, is as high as possible.
33 of 55
Middle item
In a list containing N items the 'middle' item has position [ 1/2 (N+1)] if N is odd [1/2 (N+2)] if N is even, so that if N=9, the middle item is the 5th and if N=6 it is the 4th.
34 of 55
Minimum connector
Same as a minimum spanning tree.
35 of 55
Minimum spanning tree (MST)
A spanning tree such that the total length of its arcs is as small as possible. (MST is sometimes called the minimum connector.)
36 of 55
Network
A graph where each edge has a 'weight'. (Also known as a weighted graph.)
37 of 55
Node
A point on a graph (same as a vertex).
38 of 55
Objective Function
The objective that is trying to be achieved in a linear programming problem. The function of the decision variables that is to be optimised is called the objective function.
39 of 55
Odd vertex (or node)
A vertex is odd if it has odd degree.
40 of 55
Optimal solution
A feasible solution that meets the objective.
41 of 55
Path
A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
42 of 55
Precedence table
A table showing which activities must be completed before others can be started. Also known as a dependence table.
43 of 55
Prim's algorithm
An algorithm used to find the minimum spanning tree of a network. Uses a different method to Kruskal's algorithm.
44 of 55
Quick Sort
A sorting technique that orders a list by continuously dividing the list into two parts above and below a chosen pivot point.
45 of 55
Scheduling
Scheduling is required when the number of available workers is less than the minimum needed to complete a project within its critical time. A scheduling diagram can be used to represent the situation.
46 of 55
Source node
The first point in a network.
47 of 55
Spanning tree
A spanning tree of graph G is a subgraph which includes all the vertices of G and is also a tree.
48 of 55
Subgraph
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
49 of 55
Total float
In critical path analysis, the total float of an activity is the amount of time that its start may be delayed without affecting the duration of the project. Total float = latest finish time - duration - earliest start time.
50 of 55
Tree
A connected graph with no cycles.
51 of 55
Valency
Same as degree.
52 of 55
Vertex
A point on a graph (also called a node).
53 of 55
Weight
The number associated with each edge on a graph.
54 of 55
Weighted graph
A graph where each edge has a 'weight'. (Also known as a network).
55 of 55

Other cards in this set

Card 2

Front

A precise set of instructions that will allow anyone, including a computer, to use it to achieve a particular goal in a specified number of steps.

Algorithm

Card 3

Front

A curved line connection points (nodes or vertices) on a graph.

Card 4

Front

Refers to problems that involve the packing of objects into well defined regions called bins, so that they do not overlap. The main purpose is to make efficient use of the available space.

Card 5

Front

A technique for locating a particular value in a sorted list by finding the median value and comparing it to the target value.