Discrete Flashcards
Graph
Vertices joined by edges
Simple graph
No loops or multiple edges
Connected
If all vertices are connected
Subgraph
Part of another graph
Subdivision
Add a new vertex to an edges
Degree/order of vertex
Number of lines coming off it
Sum of degrees
Always double the number of edges
Walk
Sequences of edges that flow end to end
Trail
A walk without repeating edges
Cycle
A trail that starts and ends at the same vertex
Hamiltonian cycle
Goes though each vertex exactly once
Planar graph
No edges cross each other
Euler’s formula
v-e+f=2
Complete graph
All vertices directly connected
Complement
Bits to add to make a complete graph
Bipartite graph
Two sets of vertices, an edge can only join a vertex in one set to a vertex in another set
Tree
Graph with no cycles
Adjacency matrices
Show number of links between vertices
Isomorphic graphs
Identical, vertices and edges connected in same way
Network
Graph with weights
Distance table
Shows weights between nodes (vertices)
Spanning tree
Subgraph that includes all nodes
Minimum spanning tree
Shortest way to connect all points
Kruskals algorithm
Add arcs in ascending order of weight, not if will create a cycle, until all nodes connected
Prims algorithm
Pick a node, choose are of least weight to join node in tree to node not in tree
Route inspection algorithm
Finds shortest path covering all arcs
Connected graph - Eulerian
All nodes have even degree
Connected graph - semi-eulerian
Exactly two nodes have odd degree
Route inspection for Eulerian network
Weight of network, if have to go down each path twice then becomes Eulerian (double network weight)
Route inspection for semi-Eulerian
Weight of network + weight of shortest path between two odd nodes
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
Classical travelling salesperson
Lower bound (largest is best) _< minimum weight of Hamiltonian cycle _< upper bound (smallest is best)
Practical travelling salesperson
Not always a Hamiltonian cycle - add arcs then classical - might be shortcuts
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
Upper bound
Length of any known route, use nearest neighbour algorithm to find routes
Precedence tables
Show which activities need doing before others
Activity networks
Show information from precedence tables more clearly
Nodes represent activities
Arcs show any immediate predecessors
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)
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
Minimum completion time
Sink nodes
Add EST to duration, biggest number
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
Float
How long an activity can be delayed for
LFT - duration - EST
Critical activities
Can’t be delayed
Float of zero
Critical path
Made up of critical activities
Runs from source node to sink node
Can be refined and improved
Can have limitations - weather, travel
Pay-off matrix
Shows possible outcomes
Outcomes written from point of view of player one (strategies listed in first column)
Stable solution
Where neither player can achieve a better result by changing their strategy without the other player also changing
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
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)
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)
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
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
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
Maximum flow
Equal to minimum cut, largest feasible amount of flow that can pass from source to sink
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
Lower capacities
Where a minimum flow has to be met
Finding value of a cut - add upper capacities (as normal) then subtract lower capacities
Linear programming
Aims to produce optimal solution to a problem
Decision variables
Things being produced, bought, sold, etc
Constraints
Factors that limit the problem, written as inequalities in terms of decision variables
Objective function
What you’re trying to maximise or minimise, written as equation in terms of decision variables
Feasible solution
Satisfies all constraints, gives a value for each decision variable
Optimal solution
Solution in a feasible region that maximises or minimises objective function
Table
Put information given into a table to make it easier to interpret and work out inequalities you need
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
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
Binary operation
Combines two elements in a set
Often shown with a *
Cayley tables
Show all possible combinations of elements
Element in row x and column y is x*y
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)
Commutativity
If ab = ba
Addition, multiplication, and matrix addition are commutative
Subtraction, division, and (in general) matrix multiplication aren’t
Associativity
If (ab)c = a(bc)
Addition, multiplication, matrix addition, and matrix multiplication are associative
Subtraction and division aren’t
Identity element
Leaves every element in the set unchanged with the binary operation
Unique
Some sets don’t have an identity element
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)
