Brainscape's Knowledge GenomeTM

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


See full index

Further Maths > Discrete > Flashcards

Discrete Flashcards

1
Q

Graph

A

Vertices joined by edges

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

Simple graph

A

No loops or multiple edges

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

Connected

A

If all vertices are connected

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

Subgraph

A

Part of another graph

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

Subdivision

A

Add a new vertex to an edges

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

Degree/order of vertex

A

Number of lines coming off it

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

Sum of degrees

A

Always double the number of edges

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

Walk

A

Sequences of edges that flow end to end

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

Trail

A

A walk without repeating edges

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

Cycle

A

A trail that starts and ends at the same vertex

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

Hamiltonian cycle

A

Goes though each vertex exactly once

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

Planar graph

A

No edges cross each other

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

Euler’s formula

A

v-e+f=2

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

Complete graph

A

All vertices directly connected

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

Complement

A

Bits to add to make a complete graph

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

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

Tree

A

Graph with no cycles

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

Adjacency matrices

A

Show number of links between vertices

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

Isomorphic graphs

A

Identical, vertices and edges connected in same way

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

Network

A

Graph with weights

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

Distance table

A

Shows weights between nodes (vertices)

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

Spanning tree

A

Subgraph that includes all nodes

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

Minimum spanning tree

A

Shortest way to connect all points

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

Kruskals algorithm

A

Add arcs in ascending order of weight, not if will create a cycle, until all nodes connected

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

Prims algorithm

A

Pick a node, choose are of least weight to join node in tree to node not in tree

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

Route inspection algorithm

A

Finds shortest path covering all arcs

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

Connected graph - Eulerian

A

All nodes have even degree

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

Connected graph - semi-eulerian

A

Exactly two nodes have odd degree

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

Route inspection for Eulerian network

A

Weight of network, if have to go down each path twice then becomes Eulerian (double network weight)

30
Q

Route inspection for semi-Eulerian

A

Weight of network + weight of shortest path between two odd nodes

31
Q

Route inspection for non-Eulerian

A

Pair odd nodes in all possible ways, find pair with smallest total, add extra arcs between these nodes, graph is now Eulerian

32
Q

Classical travelling salesperson

A

Lower bound (largest is best) _< minimum weight of Hamiltonian cycle _< upper bound (smallest is best)

33
Q

Practical travelling salesperson

A

Not always a Hamiltonian cycle - add arcs then classical - might be shortcuts

34
Q

Lower bound algorithm

A

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
Q

Upper bound

A

Length of any known route, use nearest neighbour algorithm to find routes

36
Q

Precedence tables

A

Show which activities need doing before others

37
Q

Activity networks

A

Show information from precedence tables more clearly
Nodes represent activities
Arcs show any immediate predecessors

38
Q

Critical paths

A

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
Q

Forward pass for earliest start time (EST)

A

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
Q

Minimum completion time

A

Sink nodes

Add EST to duration, biggest number

41
Q

Backward pass for latest finish time (LFT)

A

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
Q

Float

A

How long an activity can be delayed for

LFT - duration - EST

43
Q

Critical activities

A

Can’t be delayed

Float of zero

44
Q

Critical path

A

Made up of critical activities
Runs from source node to sink node
Can be refined and improved
Can have limitations - weather, travel

45
Q

Pay-off matrix

A

Shows possible outcomes

Outcomes written from point of view of player one (strategies listed in first column)

46
Q

Stable solution

A

Where neither player can achieve a better result by changing their strategy without the other player also changing

47
Q

Value of a game

A

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
Q

Dominated strategies

A

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
Q

Mixed strategies

A

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
Q

Graph - if other player has more than two strategies

A

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
Q

Network flow problem

A

Each arc has a capacity and direction
Model moving things along routes with limited capacity
Actual flow shown with values in circles

52
Q

Cut

A

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
Q

Maximum flow

A

Equal to minimum cut, largest feasible amount of flow that can pass from source to sink

54
Q

Super source/super sink

A

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
Q

Lower capacities

A

Where a minimum flow has to be met

Finding value of a cut - add upper capacities (as normal) then subtract lower capacities

56
Q

Linear programming

A

Aims to produce optimal solution to a problem

57
Q

Decision variables

A

Things being produced, bought, sold, etc

58
Q

Constraints

A

Factors that limit the problem, written as inequalities in terms of decision variables

59
Q

Objective function

A

What you’re trying to maximise or minimise, written as equation in terms of decision variables

60
Q

Feasible solution

A

Satisfies all constraints, gives a value for each decision variable

61
Q

Optimal solution

A

Solution in a feasible region that maximises or minimises objective function

62
Q

Table

A

Put information given into a table to make it easier to interpret and work out inequalities you need

63
Q

Slack variables

A

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
Q

Graphs (linear programming)

A

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
Q

Binary operation

A

Combines two elements in a set

Often shown with a *

66
Q

Cayley tables

A

Show all possible combinations of elements

Element in row x and column y is x*y

67
Q

Modular arithmetic

A

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
Q

Commutativity

A

If ab = ba
Addition, multiplication, and matrix addition are commutative
Subtraction, division, and (in general) matrix multiplication aren’t

69
Q

Associativity

A

If (ab)c = a(bc)
Addition, multiplication, matrix addition, and matrix multiplication are associative
Subtraction and division aren’t

70
Q

Identity element

A

Leaves every element in the set unchanged with the binary operation
Unique
Some sets don’t have an identity element

71
Q

Inverse

A

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)

Further Maths (2 decks)

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