Discrete Maths Flashcards
1
Q
Existence
A
Determining whether there is a solution
2
Q
Construction
A
Involves finding a solution
3
Q
Enumeration
A
Finding out how many solutions there are
4
Q
Optimisation
A
Finding out the best solution, according to some measure, perhaps the shortest of cheapest or most profitable
5
Q
Partition
A
A partition is a collection of disjoint subsets of a given set such that the union of the subsets must equal the original set
6
Q
Pigeon Hole principle
A
If there are m pigeonholes and n pigeons where m is smaller than n, there will be at least one pigeonhole with more than one pigeon
7
Q
What does nPr mean
A
The number of permutations of r objects selected from n objects
n!/(n-r)!
8
Q
What does nCr mean
A
The number of combinations or selections of r objects chosen from n objects
N!/(n-r)!r!
9
Q
Degree
A
Number of arcs incident to that vertex
10
Q
Adjacent
A
For vertices- joined by an edge
For edges- share a common vertex
11
Q
Tree
A
Simply connected graph with no cycles
12
Q
Simple
A
No multiple edges or loops
13
Q
Connected
A
Exists a path between every pair of vertices
14
Q
Walk
A
Set of arcs where the end vertex of one is the start vertex of the next
15
Q
Trail
A
Walk where no arcs are repeated
16
Q
Path
A
Trail where no nodes are repeated
17
Q
Cycle
A
Closed path
18
Q
Route
A
Can be a walk trail or path or a closed walk rail or path
19
Q
Complete Kn
A
Kn is a complete graph of n vertices
A Graph where every two vertices share exactly one edge and where there are no loops
No of edges = n•(n-1)/2
20
Q
A bipartite graph
A
The vertices can be divided into two sets with edges only joining a vertex in one set to a vertex in the other
21
Q
A complete bipartite graph
Km,n
A
Each of the m vertices on one side is connected exactly once to each of the n vertices on the other
It has nm edges
22
Q
Eulerian
A
It is possible to travel round a graph without repeating any edges (along a trail) so that all the edges in the graph are covered. If the trial ends at its starting point it is Eulerian.
If it has no odd vertices, it is Eulerian
23
Q
Semi Eulerian
A
It is possible to travel round a graph without repeating any edges (along a trail) so that all the edges in the graph are covered. But the trail does not end at it’s starting point
If just two of the vertices are odd.
It is semi-Eulerian.
24
Q
Hamiltonian graph
A
Finding a route around a graph that visits all the vertices exactly once. And returns to the staring point
Edges cannot be repeated as this would mean a vertex is repeated. Not all edges must be traversed.
25
Hamiltonian cycle
A cycle which visits all the vertices of a graph exactly once and returns to the starting point
26
Hamilton path
Visits all the vertices exactly once but may not be a cycle
Travelling salesperson
27
ORES THEOREM
a sufficient though not necessary condition for a graph to be Hamiltonian is that for a simply connected graph G with n ≥ 3 vertices, G will be Hamiltonian if deg v + deg w ≥ n for every pair of non-adjacent vertices
28
K-colourable
A graph is k-colourable if each of its vertices can be assigned one of k colours in such a way that no two adjacent vertices have the same colour
Bipartite requires two colours
29
Isomorphic
Two graphs are isomorphic if one can be distorted in some way to produce the other
(Same no vertices, each same degree and their vertices must be connected in the same way)
Construct isomorphism by explicit labelling of vertices
Having the same degree sequence is necessary but NOT SUFFICIENT!!! To show isomorphism
30
Indegree
| Outdegree
In a directed graph the in-degree is the number of edges leading in to a vertex and an outdegree is the number of edges leading away from the vertex
31
Planar
A graph is planar if it can be distorted in such a way that it’s edges do not cross
32
A subdivision
A subdivision is obtained by inserting a new vertex of degree 2 into an edge one or more times (zero also counts)
33
Edge contraction
An edge contraction occurs when an edge is removed and the two vertices that were joined to it are merged, any edges which were incident to either of the original vertices now become incident to the nw vertex
Include the notation (AB) for the vertex created by contraction of the arc AB
34
Euler’s formula
V+R=E+2
35
Kurotowski’s theorem
A finite graph is planar if and only if it does not contain a sub graph which a subdivision of of K5 or K3,3
Subgraph is a graph that is formed from some of the vertices and edges of another graph
A vertex may be isolated can an edge has to have a vertex at each end
A subdivision is obtained by inserting a new vertex into an edge
36
Thickness
The minimum number of planar graphs that the edges of a graph can be grouped into
37
Network
Weighed graphs(directed or undirected) used to model the connections between objects
38
Algorithm
Input and output
It is finite (comes to an end)
It is deterministic - there is no chance involved, the same input will always produce the same output
39
Heuristic
An algorithm which will find a good solution but not necessary the optimal
40
Greedy
Makes the optimal choice at that moment but does not necessarily generate the optimal solution
41
Recursive
The algorithm repeatedly calls up a simpler version until it reaches a base case
42
Computing algorithms
Algorithmic methods are used by computers for solving large scale problems and that small scale problems are only used To demonstrate how can algorithm works
43
INT (x)
Integer part of N, (round down if pos, up if neg)
44
ABS(x)
Returns the magnitude of the value
45
How do you determine the order
When the maximum run time of an algorithm is represented as a function of the size of the problem. The order of the algorithm for very large sized problem is given by the dominant term
Compare the efficiency of two algorithms that achieve the same end result by considering a given aspect of the run-time in a specific case. Calculate, worse case run complexity T(n) by considering the WORST CASE.
Calculate the run time as a function of the size of a problem by considering best case worst case or a typical case. Includes considering all cases and averaging where appropriate
46
What is the complexity of sorting algorithms
Quadratic order in general as a function of the length of the list
Quick sort is only O(n^2) in worst case
47
Packing algorithms
Next fit- take boxes in order listed and pack each box in the first bin that has enough space for it staring with the current bin
First fit- starting with the first bin each time
First fit decreasing - first reorder the bidders from largest to smallest
Full bin- look for combinations that fill the boxes, pack those and put the rest together in combinations that are nearly as full as possible
THESE ARE HEURISTIC
48
Online/ offline
They deal with each time as it arrives and do not require the whole list to be available at the start
Offline required the whole list from the start ( full gin or first fit decreasing)
49
Knapsack
Each set of items has a mass and a profit for example, and you must determine which to include so that the profit is as large as possible while the mass does not exceed some limit
50
Order of Dijstrika’s
Quadratic
51
Order of Prims
Cubic
52
Order of Kruskal’s
Cubic order
53
Nearest neighbour method
| Where does it fail
Finds an upper bound for the travelling sales person problem. VISITS ALL THE NODES ONCE AND ONLY ONCE
When this is used on a network formed by weighting a graph that is not complete it may stall before reaching every vertex or it may reach every vertex but to close the route it may need a path that is not a direct connection from the end vertex back to the start vertex
54
Minimum spanning tree on reduced network
| Where does it fail
If the graph is not complete the method can give a value which is not a lower bound for travelling salesperson VISITING THE NODES ONCE AND ONLY ONCE
55
Solving route inspection problem
VISITS ALL THE EDGES ONCE AND ONLY ONCE
Eulerian- each of the arcs is covered once. Just add up the total weights of the networks
semi-Eulerian- if the start and end modes can be different then add up the weight. If you have to end where you started then:
Find the shortest path between two odd nodes and duplicate it. Then add that on
- more than four odd nodes and return to starting point
Find the shortest path between each pair of odd nodes. Then establish all the ways of pairing up the odd nodes then choose the combination of the pairings that give the smallest possible total. Add this to the weight of the graph
56
What is the number of pairings of n nodes
For 2n odd nodes, the numbers of pairings are
The product from r=1 to N of (2r-1)
57
Activity on arc
The activities- arcs- lead into nodes which are referred to as events and are assigned two boxes.
An event can only start once the activities that lead into them have been completed
Dotted lines are referred to as dummy variables which have duration zero. This is used when an activity shares a start node and an end node. And also to indicate dependency
58
Critical activities
A path of critical activities (critical path) is the longest path in a directed network
59
Earliest time
-event zero is given an earliest time of zero
- the event earliest times are given by the earliest time all the activities leading into that event can be completed
Carry out a forward pass to determine these
60
Minimum project time
Minimum completion time
Critical time
The minimum time the whole process can be completed, determined by the earliest completion time of the end event
61
Latest finish times
Carry out a backwards pass, place the maximum completion time as the late time for the last node
This is the latest time you must be ready to leave the arc in order to complete the following events by there time
62
Critical activities
Activities without any slack, have zero float
63
Slack
Critical path analysis
How much an activity could be delayed without increasing the duration of the project
64
Burst event
An event which has two or more outgoing activities
65
Merge event
Has two or more incoming activities
66
Total float
The total float of an ACTIVITY. I’m sorry the two events it is defined by
The latest finish time for the activity - the earliest start time - duration of the activity
i(4,6)———j(10,13) (activity length 2)
13-4-2=7
67
Independent float
Float which is not affected by other activities starting late or overrunning
i(4,6)———j(10,13) (activity length 2)
10-6-2 = 2
68
Interfering float
Can be affected by other activities stating late or running over
i(4,6)———j(10,13) (activity length 2)
13-4-2=7 TOTAL FLOAT
10-6-2 = 2 INDEPENDENT FLOAT
7-2= 5 INTERFERING FLOAT
69
Cascade charts
- used to determine the effect on minimum completion time of a delay or other scheduling restrictions
- one activity on each row or with the critical activities all together in one row and a row for each non critical activity
- each bar begins at their earliest start time, the bars have length of the duration of the activity and then a dotted border to show float
Can be used to construct a schedule to show how a given number of workers can complete a project. Length of bar is time taken, height of bar is number of workers.
70
BRANCH AND BOUND METHOD
* record the non integer solution at node one, together with the resulting value of the objective function. This is the upper bound(can be truncated to an integer)
* truncate the variables to obtain an integer solution, then give a lower bound, record this at node 1 as well
* branch on the variable that was truncated most to give for example x ≥ 4 and x ≤ 3
* solve the original problem again with those as added constrains. Record solution at each node along with the upper bound which applies to all branches from that node
* if the solution obtained is a purely integer one, it may produce an increase in the lower bound for the tree. The current LB is recorded at each node
* when choosing the next node to branch from, select the one with the largest upper bound, the two branches are obtained by truncating the non-integer value
* add the constrains and include those on earlier branches
* nodes are rejected when the value of the objective function is less than the current lower bound
* an optimal integer solution is obtained if the value of the objective function is equal to the largest upper bound among the remaining end nodes
If the objective function has to be minimised then the process is the same except that the roles of the upper and lower bounds are reversed
71
Simplex tableau standard format
Rows:
Objective to be maximised
Follows by constraints
Columns:
Objective, then variables, then slack variables and then a column representing RHS
To minimise P is the same as maximising -P . So minimising P=2x+y-3z is the same as maximising P=-2x-y+3z, so the coefficients in the table would be 2 1 and -3 because P+2x+y-3z=0
72
Interpreting the simplex tableau
The larger the value of the slack variables the further you are from that constraint line and the greater the amount of slack available
You are working your way around the vertices of the feasible region (moving along edges of the multidimensional convex polygon) (basic feasible solutions) until no further improvement can be made
The current improved solution at each stage can be obtained by setting all the non-basic variables to zero
The values of the basic solutions are the values in the RHS
73
Basic feasible solution
Vertices of the feasible region
74
Basic variables
Only has a coefficient in one row and the value of the coefficient is 1
75
Non basic
Has coefficients in more than one row
These are set to zero to interpret the solution
76
Zero sum game
The amount won by player one is equal to the amount lost by player 2
The pay off to player 2 is the negative of the pay off to player 1
77
Constant sum game
Some games have a constant sum. These can be converted to zero sum. By finding the constant sum, dividing it by 2. Assuming each player puts that value into a kitty from which the payout is made. So subtract the value from the payoffs
78
Dominated strategies
When a player would never choose an option because another option would always be of better or equal value. Then that option is said to dominate the other option. This option can be deleted and the pay-off matrix can be reduced
79
Play-safe strategies
A player chooses the option with the best worst outcome.
This the for player 1, the max of the row minima
And for player 2, the minimum of the column maxima
80
A stable solution/ saddle point
The game is in equilibrium. The value of the game is player 1s payoff
A stable solution occurs when the maximum of the row minima equals the minimum of the column maxima
Neither player has a motive to deflect
81
Nash Equilibrium
Neither player would want to change their choice assuming that be other player maintained their choice.
It is not necessarily the best solution for the two players.
Strict - the alternative is inferior.
Non-strict- alternative is the Same (in the case of weak dominance it is possible to loose a non-strict Nash equilibrium
82
Mixed strategy
Two variables
When a game has no stable solution:
Option A is played with probability P
Option B is played with probability P-1
The expected pay off depends on player 2’s choice
Form an expected payoff for both of player 2’s options
Plot these expected payoffs against p
Then look for the value of p such that the lowest of the two lines is as high as possible - when they intersect.
If it is three lines, look for the value of p such that the lower of the lines is as high as possible.
83
Converting games to linear programming
Add an amount to every element, n, so that the values are all positive. Remember to remove this value from the profit at the end.
Label the probabilities for each choice A can make as p1 p2 p3... - work out the expected pay off for each of Bs options.
V smaller than or equal to each expected pay off. Rearrange to get RHS equal to zero when forming the equation with slack
Maximise P=V-n rearrange to P-V =-n
Add the constraint p1+p2+p3 is less than 1
p1+p2+p3+s=1
The only values in RHS are from the probables inequality and the objective function
Solve the simplex tableau
84
Derangement
A permutation such that no object is in its original position
Approximately number of arrangements • 1/e
85
Are complete graphs Hamiltonian
Yes when n is greater than 2. Because it can be represented as a polygon with every pair of vertices joined. The cycle is through the outside of the polygon
86
Is a complete bipartite graph Hamiltonian
When m=n because any path needs to alternate between the two sets
87
Ad hoc method
Impromptu strategy that may be unique to a particular problem, rather than being a general strategy
•usually only work for small scale problems
88
Why is it not possible to create a minimum spanning tree including directed edge
It must be possible to get from any vertex to any other vertex. If there is a directed arc, there must be a way to get from the end of the arc to the start, therefore there is a cycle
