Discrete Flashcards
1
Q
Graph
A
Vertices joined by edges
2
Q
Simple graph
A
No loops or multiple edges
3
Q
Connected
A
If all vertices are connected
4
Q
Subgraph
A
Part of another graph
5
Q
Subdivision
A
Add a new vertex to an edges
6
Q
Degree/order of vertex
A
Number of lines coming off it
7
Q
Sum of degrees
A
Always double the number of edges
8
Q
Walk
A
Sequences of edges that flow end to end
9
Q
Trail
A
A walk without repeating edges
10
Q
Cycle
A
A trail that starts and ends at the same vertex
11
Q
Hamiltonian cycle
A
Goes though each vertex exactly once
12
Q
Planar graph
A
No edges cross each other
13
Q
Euler’s formula
A
v-e+f=2
14
Q
Complete graph
A
All vertices directly connected
15
Q
Complement
A
Bits to add to make a complete graph
16
Q
Bipartite graph
A
Two sets of vertices, an edge can only join a vertex in one set to a vertex in another set
17
Q
Tree
A
Graph with no cycles
18
Q
Adjacency matrices
A
Show number of links between vertices
19
Q
Isomorphic graphs
A
Identical, vertices and edges connected in same way
20
Q
Network
A
Graph with weights
21
Q
Distance table
A
Shows weights between nodes (vertices)
22
Q
Spanning tree
A
Subgraph that includes all nodes
23
Q
Minimum spanning tree
A
Shortest way to connect all points
24
Q
Kruskals algorithm
A
Add arcs in ascending order of weight, not if will create a cycle, until all nodes connected
25
Prims algorithm
Pick a node, choose are of least weight to join node in tree to node not in tree
26
Route inspection algorithm
Finds shortest path covering all arcs
27
Connected graph - Eulerian
All nodes have even degree
28
Connected graph - semi-eulerian
Exactly two nodes have odd degree
29
Route inspection for Eulerian network
Weight of network, if have to go down each path twice then becomes Eulerian (double network weight)
30
Route inspection for semi-Eulerian
Weight of network + weight of shortest path between two odd nodes
31
Route inspection for non-Eulerian
Pair odd nodes in all possible ways, find pair with smallest total, add extra arcs between these nodes, graph is now Eulerian
32
Classical travelling salesperson
Lower bound (largest is best) _< minimum weight of Hamiltonian cycle _< upper bound (smallest is best)
33
Practical travelling salesperson
Not always a Hamiltonian cycle - add arcs then classical - might be shortcuts
34
Lower bound algorithm
Choose a node (A), find lowest two weights joined to this node (x and y), delete node A and all arcs attached, find minimum spanning tree and work out weight (W)
Lower bound = W + x + y
35
Upper bound
Length of any known route, use nearest neighbour algorithm to find routes
36
Precedence tables
Show which activities need doing before others
37
Activity networks
Show information from precedence tables more clearly
Nodes represent activities
Arcs show any immediate predecessors
38
Critical paths
Duration - how long it takes to complete (middle box)
Earliest start time - depends on durations of preceding activities (first box)
Latest finish time - without increasing duration of entire project (last box)
39
Forward pass for earliest start time (EST)
Source nodes ESTs are 0
| Move through network, look at preceding activity and add EST to duration, if more than one activity use biggest number
40
Minimum completion time
Sink nodes
| Add EST to duration, biggest number
41
Backward pass for latest finish time (LFT)
Sink nodes LFTs are equal to minimum completion time
Move backwards through network, subtract duration of succeeding activity from LFT, if more than one activity use smallest number
42
Float
How long an activity can be delayed for
| LFT - duration - EST
43
Critical activities
Can’t be delayed
| Float of zero
44
Critical path
Made up of critical activities
Runs from source node to sink node
Can be refined and improved
Can have limitations - weather, travel
45
Pay-off matrix
Shows possible outcomes
| Outcomes written from point of view of player one (strategies listed in first column)
46
Stable solution
Where neither player can achieve a better result by changing their strategy without the other player also changing
47
Value of a game
Found by looking for stable solution
Play safe for P1 - max(row minima) - maximin value
Play safe for P2 - min(column maxima) - minimax value
If maximin=minimax this is a stable solution (value is gain made by P1)
If maximin≠minimax then no stable solutions
48
Dominated strategies
If strategy B is always better off than strategy A, A is dominated by B and can be removed (as will never be chosen)
49
Mixed strategies
Maximise value of unstable solutions
For P1, optimal mixed strategy maximises value of game
For P2, optimal mixed strategy minimises value of game
For two strategy games, optimal mixed strategy found by ensuring the expected gain is the same, whatever opponent does (an equalising strategy)
50
Graph - if other player has more than two strategies
Plot expected gains for P1 on graph for values of p between 0 and 1, and value of game, choose p so minimum value of three functions is as high as possible
51
Network flow problem
Each arc has a capacity and direction
Model moving things along routes with limited capacity
Actual flow shown with values in circles
52
Cut
Partitions nodes into two disjoint (a node can’t be in both subsets) subsets, S (source-side), T (sink-side)
Value or capacity is total capacity of arcs it crosses - only count arcs directed from S to T
Value of a cut puts upper bound on flow through a network - value of flow _< value of any cut
53
Maximum flow
Equal to minimum cut, largest feasible amount of flow that can pass from source to sink
54
Super source/super sink
If a network has more than one source and/or sink you need to add extra nodes - total capacity into each original source must equal total capacities out
55
Lower capacities
Where a minimum flow has to be met
| Finding value of a cut - add upper capacities (as normal) then subtract lower capacities
56
Linear programming
Aims to produce optimal solution to a problem
57
Decision variables
Things being produced, bought, sold, etc
58
Constraints
Factors that limit the problem, written as inequalities in terms of decision variables
59
Objective function
What you’re trying to maximise or minimise, written as equation in terms of decision variables
60
Feasible solution
Satisfies all constraints, gives a value for each decision variable
61
Optimal solution
Solution in a feasible region that maximises or minimises objective function
62
Table
Put information given into a table to make it easier to interpret and work out inequalities you need
63
Slack variables
Turn inequalities into equations, slack is amount of resource left unused
Can only be used when decision variables are constrained by an upper limit - only one slack variable per constraint
64
Graphs (linear programming)
Draw each constraint as line on graph, decide whether feasible solutions will be above or below the line, shade region you don’t want, unshaded area is feasible region
Objective function - draw line Z=ax+by (choose fixed value of Z, a and b given in question), this is objective line - to maximise slide right (last point it touches), to minimise slide left (last point it touches)
Vertex method - find x and y values of vertices of feasible region, put into objective function Z=ax+by to find value of Z, look at Z values and work out which is optimal value
65
Binary operation
Combines two elements in a set
| Often shown with a *
66
Cayley tables
Show all possible combinations of elements
| Element in row x and column y is x*y
67
Modular arithmetic
Two integers, a and b, are said to be congruent modulo m (or modn) if a-b is divisible by n
a=b(modn)
Addition modulo n (+n) -> x +n y = x+y(modn)
Multiplication modulo n (xn) -> x xn y = x x y (modn)
68
Commutativity
If a*b = b*a
Addition, multiplication, and matrix addition are commutative
Subtraction, division, and (in general) matrix multiplication aren’t
69
Associativity
If (a*b)*c = a*(b*c)
Addition, multiplication, matrix addition, and matrix multiplication are associative
Subtraction and division aren’t
70
Identity element
Leaves every element in the set unchanged with the binary operation
Unique
Some sets don’t have an identity element
71
Inverse
In set S with binary operation *, inverse x^-1 of x is element where x^-1 * x = e and x * x^-1 = e (e is identity)
