# D1 Terminology

Some terminology from D1 - I don't know what exam board, so some of it might be D2. It's mostly stuff on graphs and networks - there's a little on the simplex method at the end, but not much

• Created by: emily
• Created on: 19-01-13 15:05
Algorithm
A set of precise instructions which will solve a problem if followed
1 of 74
Properties of an algorithm
Each stage must be defined precisely;l there must be no ambiguity in any instruction; there must be a finite set of instructions; the algorithm must work for any values that are input
2 of 74
Flow diagrams: oval boxes
Start, Stop, Input. or Output
3 of 74
Flow diagrams: square boxes
Operations to be carried
4 of 74
Flow diagrams: diamond boxes
Questions, or Decisions
5 of 74
Graph
A finite number of points connected by lines
6 of 74
Verticies / Nodes
The points on a graphs
7 of 74
Edges / Arcs
The lines on a graph
8 of 74
Network / Weighted graph
A graph with a number associated to each edge representing time, distance, cost etc.
9 of 74
Connected vertices
Vertices joined by an edge
10 of 74
Connected Graph
A graph where all vertices are connected
11 of 74
Fully connected / Complete graph
A graph where each vertex is connected at least once to every other vertex
12 of 74
Loop
An edge with the same vertex at each end
13 of 74
Simple graph
A graph with no loops, and where at most one edge connects any pair of vertices
14 of 74
Degree / Order /Valency of a vertex
The number of edges connected to the vertex
15 of 74
Directed graph / Digraph
A graph that has directed edges
16 of 74
Bipartite graph
A graph with two sets of vertices, with edges that only connect vertices from one set to another
17 of 74
Trail / Walk
A sequence of edges of a graoph such that the second vertex of each edge is the first vertex of the next edge, with no edge included more than once
18 of 74
Path
A trail in which no vertex is visited moer than once, except that the first vertex may be the last
19 of 74
Cycle / Circuit
A closed path with at least one edge, where its first vertex must be its last
20 of 74
hamilton cycle
A cycle that visits every vertex of a graph
21 of 74
Number of permutations of a Hamilton cycle
0.5 x (n - 1)!
22 of 74
Tree
A connected graph with no cycles
23 of 74
Spanning Tree
A tree that connects all the vertices of a graph
24 of 74
Minimum spanning tree / Minimum connector
The spanning tree of minimum weight for that network
25 of 74
A matrix representing a graph
26 of 74
Planar graph
A graph that can be drawn without any arcs intersecting
27 of 74
Eulerian trail
A trail that uses every edge of a graph. Each node must have an even degree
28 of 74
Semi-Eulerian trail
A non-closed Eulerian trail - it doesn't finish at the start vertex. It must have exactly 2 odd vertices, where it must start and finish
29 of 74
Traversable / Eulerian graph
A graph where it is possible to trace each edge once in a single trail. It must have no odd vertices.
30 of 74
Edge set
A set of edges
31 of 74
Vertex set
A set of vertices
32 of 74
Subgraph
A subset pf the vertices together with a subset of the edges
33 of 74
Isomorphic graphs
Two (or more) graphs that can be deformed to make each other - vertices can be moved and the edges straightened or bent to do this
34 of 74
Comparison
Where you compare two values
35 of 74
Swap
Where you swap the positions of two side-by-side values
36 of 74
Upper bound
a value that exists but may be improved upon
37 of 74
Lower bound
The smallest integer greater than or equal to the result
38 of 74
Heuristic algorithm
An algorithm that attemots to find the best solution
39 of 74
The complexity of an algorithm
The extent to which the number of possibilities increases as the size of the problem increases
40 of 74
The Travelling Salesman Problem (TSP)
Find a route of minimum weight which visits every vertex in an undirected network
41 of 74
Tour
A cycle which visits every vertex and returns to the start vertex
42 of 74
An upper bound for the total length of the solution to the practical travelling salesman problem
Twice the length of the minimum spanning tree
43 of 74
The Route Inspection / Chinese Postman Problem
Find a minimum weight route which traverses every edge of a given connected network at least once
44 of 74
Activity
A task which needs to be done and takes a given amount of time/resources to complete. It is represented by the edge of a graph
45 of 74
Event
The start or finish of one of more activities. It is represented in a graph by a vertex
46 of 74
Precedence table
A table that shows which activities need to be done together, their duration and their immediate predecessors
47 of 74
Precedence network
A network showing a sequence of activities; it must have a start node and a finish node. Events are numbered so thatthe activity ends at a higher numbered event than it started at.
48 of 74
Dummy activity
An activity of zero length so that no two activities have the same start and finish events
49 of 74
Critical path
the longest path from source node to sink node
50 of 74
Earliest start time
The earliest time that you can arrive at event i with all the incoming activities completed
51 of 74
Latest start time
The latest time at which an activity can start
52 of 74
Earliest finish time
The earliest possible time at which an activity can finish
53 of 74
Latest finish time
The latest time you can leave event i without extending the length of the critical path
54 of 74
Slack
The allowable delay at an event
55 of 74
Total float
The maximum posible delat that can be incurred in the processing of the activity without increasing the length of the critical path
56 of 74
Independant float
The float that does not affect other activities
57 of 74
Interfering float
The float that is shared between two or more activities
58 of 74
Critical activities
Activities which have zero float. Their timing is critical if the project is to be compoleted in the minimum time. They will form the critical path through the network
59 of 74
Flow network / Transmission system
A network representing a system of flows, such as liquids, gases or information
60 of 74
Cut (Flow networks)
A division / partition of the vertices of a flow network into two sets, one containing the source and one containing the sink
61 of 74
Capacity of a cut
The sum of capacities of all edges which connect a vertex in the source set to a vertex in the sink set
62 of 74
Max flow-min cut theorem
The maximum total flkow that can be established through a flow network is equal to the capacity of the minimum cut
63 of 74
Excess capcacity
The amount by which the flow along the edge may be increased
64 of 74
Back capacity
The amount by which flow along the edge may be reduced
65 of 74
Flow augmenting path
A path from source to wink along which each edge has some unused capacity and so the flow along this path may be increased
66 of 74
Objective function
The function of the decision variables which is to be optimised
67 of 74
Feasible solution
Any pair of values, x and y, which satisfy all the constraints in a linear programming problem
68 of 74
Feasible region
The region which contains all feasible solutions
69 of 74
The Simplex Method
The algebraic method for solving linear programming problems
70 of 74
A linear programming problem in standard form
Maximise (ax + by + cz) subject to the constraints (ax + by + cz (smaller than or equal to) d)
71 of 74
Matching
A bipartite graph in which every vertex has at most one edge connected to it and no two edges have a common vertex
72 of 74
Maximal matching
A matching in which the number of edges is as larfe as possible
73 of 74
Complex matching
A matching in which there are n vertices in each vertex set and n edges
74 of 74

## Other cards in this set

### Card 2

#### Front

Each stage must be defined precisely;l there must be no ambiguity in any instruction; there must be a finite set of instructions; the algorithm must work for any values that are input

#### Back

Properties of an algorithm

### Card 3

#### Front

Start, Stop, Input. or Output

### Card 4

#### Front

Operations to be carried

### Card 5

#### Front

Questions, or Decisions