D1 Definitions

• Created by: jroe99
• Created on: 14-06-18 20:29
Algorithm
Precise set of instructions that anyone can use them to achieve a particular goal in a specified number of steps.
1 of 49
Graph
Vertices connected by arcs.
2 of 49
Subgraph
Part of a graph.
3 of 49
Weighted graph
Graph with numbers on each edge.
4 of 49
Vertex degree/valency/order
The number of edges incident to a vertex
5 of 49
Path
A finite sequence of edges such that the end of the vertex of one edge is the start vertex of the next edge and no vertex appears more than once.
6 of 49
Walk
A path in which vertices can appear more than once.
7 of 49
Cycle/circuit
A closed path (the end vertex of the final edge is the same as the start vertex of the first edge).
8 of 49
Connected vertices
Vertices with a path between them.
9 of 49
Connected graph
A graph in which all the vertices are connected.
10 of 49
Loop
An edge which starts & finished at the same vertex.
11 of 49
Simple graph
A graph with no loops & not more than one edge connecting any pair of vertices.
12 of 49
Digraph
A graph in which some of the edges are directed.
13 of 49
Tree
A connected graph with no cycles.
14 of 49
Spanning tree
A subgraph which includes all vertices of the original graph and is a tree.
15 of 49
Minimum spanning tree
A spanning tree such that the total length of the arcs is as small as possible.
16 of 49
Bipartite graph
A graph consisting of two sets of vertices & edges which joins members of one set of members of the other set & has no edges joining members of a set to members of the same set.
17 of 49
Complete graph
A graph in which every vertext is directly connected by an edge to every other vertex.
18 of 49
K_n
A complete graph with n vertices
19 of 49
K_(r,s)
A complete bipartite graph with r vertices in the first set & s vertices in the second set.
20 of 49
Isomorphic graphs
Graphs which show the same information but are drawn differently.
21 of 49
A matrix recording the number of direct links between vertices.
22 of 49
Distance matrix
A matrix recording the weights on the edges of a weighted graph.
23 of 49
Euelerian/traversible graph
A graph in which every vertex is even, making it possible to traverse every arc once & return to the start vertex.
24 of 49
Semi-Eulerian/traversible graph
A graph with precisely two odd vertices, making it possible to traverse every arc once provided you start & finish at the odd vertices.
25 of 49
Non-traversible graph
A graph with more than two odd vertices.
26 of 49
Critical activity
An activity for which an increase in its duration results in a corresponding increse in the duration of the project. Critical activities have no float.
27 of 49
Critical path
A path from one source to sink node which only follows critical activites. The longest path in the network, it represents the shortest possible time for the job to be completed.
28 of 49
Float
The difference between the amount of time available for an activity & its duration. It represents the amount of time an activity can be delayed for without affecting the duration of the whole project.
29 of 49
Dummy activity (dependence)
An activity with no weight needed because activity C depends only on activity A but activity D depends on both A & B.
30 of 49
Dummy activity (uniqueness)
An activity with no weight needed to enable the unique representation of activities in terms of their start & end events.
31 of 49
Alternating path
A path starting at an unmatched node of a bipartite graph & finishing at an unmatched node from the alternate set of the bipartite graph which uses arcs alternately in & not in the initial matching.
32 of 49
Matching
A one to one pairing of some or all of the nodes of one set in a bipartite graph with nodes of the alternate set. One to one means each node from one set is matched with only one node of the alternate set.
33 of 49
Maximal matching
A matching in which the number of arcs is as big as possible.
34 of 49
Complete matching
A matching in of two setsm each containing n nodes, which has n arcs.
35 of 49
Bubble sort
An algorithm to put a list into order using direct comparisons of adjacent elements. It stops when you complete a full pass with no swaps.
36 of 49
Quick sort
An algorithm to put a list in order using pivots. It stops when all elements are fixed.
37 of 49
Bin packing (first fit)
Place the items in the first bin that will take them using the order in which they are given. It is quick but not likely to lead to a good solution.
38 of 49
Bin packing (first fit decreasing)
Places the items in the first bin that will take them starting with the largest. It is easy and leads to a good solution, but may not be the optimal solution.
39 of 49
Bin packing (full bin)
Place the items into the bins by eye in order to fill as many bins as possible. It leads to a good solution but is difficult.
40 of 49
Binary search
An algorithm to locate a name in an ordered list. Finished when the name is located or the list becomes empty.
41 of 49
Kruskal
An algorithm for constructing a minimum spanning tree in a weighted network, finds the fastest way to link nodes in a system. Starts with the smallest arc & rejects arcs in increasing order of size.
42 of 49
Prim
An algorithm for constructing a minimum spanning tree in a weighted network, finds the quickest way to link nodes in a system. Can start with any node & has no need to check for cycles. Can be applied to a matrix.
43 of 49
Dijkstra
An algorithm for finding the shortest route from a start node to any other node in a weighted network.
44 of 49
Matching algorithm
An algorithm for improving one to one pairing of elements of one set with elements of another set represented by a bipartite graph.
45 of 49
Route inspection
An algorithm for finding the length of the shortest traverse through a non-Eurlerian graph, identifying which arcs should be repeated & at which nodes to start/finish.
46 of 49
Linear programming
A method of optimising a function given various constraints. Starts by formulating constraints & sketching the feasible region & can be completed using either the ruler or vertex method.
47 of 49
Critical path analysis
An algorithm to identify the shortest time to complete a sequence of dependent activities & the minimum number of workers needed.
48 of 49
Three differenes between Prims & Kruskals
Kruskals starts with shortest arc, Prim starts with any node. It is necessary to check for cycles when using Kruskal, not Prims. When using Prim, the 'growing' tree is always connected.
49 of 49

Other cards in this set

Card 2

Front

Vertices connected by arcs.

Graph

Card 3

Part of a graph.

Back Card 4

Front

Graph with numbers on each edge.

Back Card 5

Front

The number of edges incident to a vertex

Back 