Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete Mathematics > Discrete Maths > Flashcards

Discrete Maths Flashcards

1
Q

Existence

A

Determining whether there is a solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Construction

A

Involves finding a solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Enumeration

A

Finding out how many solutions there are

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Optimisation

A

Finding out the best solution, according to some measure, perhaps the shortest of cheapest or most profitable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What does nPr mean

A

The number of permutations of r objects selected from n objects

n!/(n-r)!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does nCr mean

A

The number of combinations or selections of r objects chosen from n objects

N!/(n-r)!r!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Degree

A

Number of arcs incident to that vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Adjacent

A

For vertices- joined by an edge

For edges- share a common vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Tree

A

Simply connected graph with no cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Simple

A

No multiple edges or loops

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Connected

A

Exists a path between every pair of vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Walk

A

Set of arcs where the end vertex of one is the start vertex of the next

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Trail

A

Walk where no arcs are repeated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Path

A

Trail where no nodes are repeated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Cycle

A

Closed path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Route

A

Can be a walk trail or path or a closed walk rail or path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Hamiltonian cycle

A

A cycle which visits all the vertices of a graph exactly once and returns to the starting point

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Hamilton path

A

Visits all the vertices exactly once but may not be a cycle

Travelling salesperson

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

ORES THEOREM

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

K-colourable

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Isomorphic

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Indegree

Outdegree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Planar

A

A graph is planar if it can be distorted in such a way that it’s edges do not cross

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

A subdivision

A

A subdivision is obtained by inserting a new vertex of degree 2 into an edge one or more times (zero also counts)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Edge contraction

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Euler’s formula

A

V+R=E+2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Kurotowski’s theorem

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Thickness

A

The minimum number of planar graphs that the edges of a graph can be grouped into

37
Q

Network

A

Weighed graphs(directed or undirected) used to model the connections between objects

38
Q

Algorithm

A

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
Q

Heuristic

A

An algorithm which will find a good solution but not necessary the optimal

40
Q

Greedy

A

Makes the optimal choice at that moment but does not necessarily generate the optimal solution

41
Q

Recursive

A

The algorithm repeatedly calls up a simpler version until it reaches a base case

42
Q

Computing algorithms

A

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
Q

INT (x)

A

Integer part of N, (round down if pos, up if neg)

44
Q

ABS(x)

A

Returns the magnitude of the value

45
Q

How do you determine the order

A

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
Q

What is the complexity of sorting algorithms

A

Quadratic order in general as a function of the length of the list

Quick sort is only O(n^2) in worst case

47
Q

Packing algorithms

A

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
Q

Online/ offline

A

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
Q

Knapsack

A

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
Q

Order of Dijstrika’s

A

Quadratic

51
Q

Order of Prims

A

Cubic

52
Q

Order of Kruskal’s

A

Cubic order

53
Q

Nearest neighbour method

Where does it fail

A

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
Q

Minimum spanning tree on reduced network

Where does it fail

A

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
Q

Solving route inspection problem

A

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
Q

What is the number of pairings of n nodes

A

For 2n odd nodes, the numbers of pairings are

The product from r=1 to N of (2r-1)

57
Q

Activity on arc

A

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
Q

Critical activities

A

A path of critical activities (critical path) is the longest path in a directed network

59
Q

Earliest time

A

-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
Q

Minimum project time
Minimum completion time
Critical time

A

The minimum time the whole process can be completed, determined by the earliest completion time of the end event

61
Q

Latest finish times

A

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
Q

Critical activities

A

Activities without any slack, have zero float

63
Q

Slack

Critical path analysis

A

How much an activity could be delayed without increasing the duration of the project

64
Q

Burst event

A

An event which has two or more outgoing activities

65
Q

Merge event

A

Has two or more incoming activities

66
Q

Total float

A

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
Q

Independent float

A

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
Q

Interfering float

A

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
Q

Cascade charts

A
  • 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
Q

BRANCH AND BOUND METHOD

A
  • 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
Q

Simplex tableau standard format

A

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
Q

Interpreting the simplex tableau

A

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
Q

Basic feasible solution

A

Vertices of the feasible region

74
Q

Basic variables

A

Only has a coefficient in one row and the value of the coefficient is 1

75
Q

Non basic

A

Has coefficients in more than one row

These are set to zero to interpret the solution

76
Q

Zero sum game

A

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
Q

Constant sum game

A

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
Q

Dominated strategies

A

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
Q

Play-safe strategies

A

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
Q

A stable solution/ saddle point

A

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
Q

Nash Equilibrium

A

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
Q

Mixed strategy

Two variables

A

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
Q

Converting games to linear programming

A

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
Q

Derangement

A

A permutation such that no object is in its original position

Approximately number of arrangements • 1/e

85
Q

Are complete graphs Hamiltonian

A

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
Q

Is a complete bipartite graph Hamiltonian

A

When m=n because any path needs to alternate between the two sets

87
Q

Ad hoc method

A

Impromptu strategy that may be unique to a particular problem, rather than being a general strategy

•usually only work for small scale problems

88
Q

Why is it not possible to create a minimum spanning tree including directed edge

A

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

Discrete Mathematics (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions