# 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

4.0 / 5

HideShow resource information

- 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

Adjacency / Incidence matrix

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

#### Back

### Card 4

#### Front

Operations to be carried

#### Back

### Card 5

#### Front

Questions, or Decisions

#### Back

## Similar Leisure Studies resources:

0.0 / 5

1.0 / 5

0.0 / 5

0.0 / 5

0.0 / 5

## Comments

No comments have yet been made