Brainscape's Knowledge GenomeTM

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


See full index

A-Level Further Maths > Graphs/ Networks > Flashcards

Graphs/ Networks Flashcards

1
Q

event where more than one activity starts

A

burst event

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

event where more than one activity ends

A

merge event

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

Dummy Activity

A

an activity that has zero duration

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

need for dummies:

A
  1. to prevent activities starting and finishing on the same node
  2. make it possible to draw the correct dependencies
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

earliest event times

A
  • forwards pass
  • largest value you can get
  • an event cannot start until all events leading to it have finished i.e. its the longest path
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

latest event times

A
  • backwards pass

- the smallest value you can get

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

critical activities

A

LET - EET - duration = 0

changing the duration will effect the overall minimum project completion time

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

minimum project completion time

A

duration of the longest path on the network

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

float

A

spare time associated with an activity

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

total float =

A

LET (i) - EET (j) - duration

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

float of a critical activity =

A

= 0

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

independent float =

A

EET (j) - LET (i) - duration

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

interfering float =

A

total float - independent float

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

Independent float

A

an activity can increase by x amount of time without effecting the minimum completion time

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

interfering float

A

a group of activities can increase by a set amount of time

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

float in cascade

A

dotted lines to show how an event can be moved

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

critical activities on a cascade chart

A

all in one row, other activities above on a different row depending on dependencies

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

Drawing cascade diagrams

A
  • critical activities in order on a single row

- each activity on its own row with the correct float

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

For the adjacency matrix of a digraph:

A

Read in rows i.e. if there’s a weight in row A and column B Then the edge goes from A to B

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

Complete

A

every possible pair of vertices is connected by an edge

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

isomorphic

A

If two graphs look different but they are structurally the same (in terms of the connections between the vertices)

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

bipartite graph

A

vertices divided into two sets

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

connected

A

if every vertex can be reached from every other vertex by going along edges

24
Q

route

A

a walk, trail or path

25
Q

walk

A

set of edges in order

26
Q

trail

A

a walk where no edge is repeated

27
Q

path

A

a trail where no vertices are repeated

28
Q

cycle

A

a closed trail

29
Q

network

A

a graph with weights

30
Q

eulerian network

A

all nodes have an even order

31
Q

semi eulerian network

A

two nodes have odd order, the rest have even order

32
Q

minimum spanning tree algorithms

A

kruskals and prims

33
Q

how to find a route that travels along every edge of network without repeating edges

A

determine if the graph is eulerian or not

34
Q

prims algorithm from a table

A
  1. choose the start vertex e.g. A, label the column A 1, and delete row A. Select the smallest entry in column A
  2. Whichever row the entry is in e.g. B, label the column B 2 and delete row B
  3. repeat until all the rows have been crossed out and each column has been labelled
35
Q

finding the shortest path

A

Dijkstras

36
Q

colouring argument

A

assigning each vertex a colour which is different to the neighbouring vertices with the aim of using the smallest amount of colours

37
Q

uses of colouring arguments

A

to see if a graph is bipartite

38
Q

Hamiltonian path

A

visits each vertex once and only once starting and finishing on different vertices

39
Q

Hamiltonian cycle

A

a cycle which visits every vertex

40
Q

Hamiltonian graph

A

a graph with a Hamiltonian cycle

41
Q

Use of ores theorum

A

determines if a graph is hamiltonian

42
Q

Ores theorum

A

If
degree of v + degree of w >= n
for every pair of distinct non-adjacent vertices v and w then the graph is Hamiltonian
(n is the number of vertices)

43
Q

if ores theorem is not true

A

the graph may still be Hamiltonian

44
Q

planar

A

A graph is planar if it can be drawn in two dimensions without any edges crossing

45
Q

Eulers formula

A

V + R = E + 2
V = number of vertices
R = number of distinct regions
E = number of edges

46
Q

Use of Eulers formula

A

if the graph satisfies eulers formula then the graph is planar

47
Q

Kuratowski’s theorum

A

A graph is planar if an only if it does not contain a sub graph of K5 or K3,3

48
Q

Use of Kuratowski’s theorum

A

determining if a graph is planar

49
Q

Thickness

A

The number of layers that are needed to draw a graph without any crossing edges

50
Q

Finding the most efficient route that goes to each node on a network if the graph is not eurlerian

A
  1. find the total of all the weights
  2. identify all the odd vertices
  3. pair all the odd vertices in all the possible ways and work out the weights
  4. identify the pairing where the total weight is the shortest and add this to the total weights for the network
51
Q

Finding the lower bound for a travelling sales person problem

A
  1. remove a vertex and all its associated edges
  2. find a minimum spanning tree for the remaining network
  3. replace the vertex aswell as its two shortest vertices
  4. the result is the lower bound
52
Q

If the lower bound method for the travelling sales person problem gives a tour then…

A

if the tour is a hamiltonian cycle then this tour is optimal

53
Q

planar graph thickness

A

1

54
Q

How to find the upper bound for the travelling salesperson problem

A

nearest neighbour:

  1. choose a starting node
  2. choose the smallest arc from this node to a node not yet in the tour
  3. repeat until all nodes are in the tour
  4. add an arc back to the starting node
55
Q

for a non Eulerian network the shortest tour starts and finishes on the…

A

odd degree vertices ( because only the odd degree vertices which it doesn’t start/ finish on have to be repeated)

56
Q

Ores Theorum

A

If
degree of v + degree of w >= n
for every pair of distinct non-adjacent vertices v and w then the graph is Hamiltonian
(n is the number of vertices)

A-Level Further Maths (13 decks)

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