Graphs/ Networks

Question 1

event where more than one activity starts

Answer 1

burst event

Question 2

event where more than one activity ends

Answer 2

merge event

Question 3

Dummy Activity

Answer 3

an activity that has zero duration

Question 4

need for dummies:

Answer 4

1. to prevent activities starting and finishing on the same node
2. make it possible to draw the correct dependencies

Question 5

earliest event times

Answer 5

• 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

Question 6

latest event times

Answer 6

• backwards pass

- the smallest value you can get

Question 7

critical activities

Answer 7

LET - EET - duration = 0

changing the duration will effect the overall minimum project completion time

Question 8

minimum project completion time

Answer 8

duration of the longest path on the network

Question 9

float

Answer 9

spare time associated with an activity

Question 10

total float =

Answer 10

LET (i) - EET (j) - duration

Question 11

float of a critical activity =

Answer 11

= 0

Question 12

independent float =

Answer 12

EET (j) - LET (i) - duration

Question 13

interfering float =

Answer 13

total float - independent float

Question 14

Independent float

Answer 14

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

Question 15

interfering float

Answer 15

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

Question 16

float in cascade

Answer 16

dotted lines to show how an event can be moved

Question 17

critical activities on a cascade chart

Answer 17

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

Question 18

Drawing cascade diagrams

Answer 18

• critical activities in order on a single row

- each activity on its own row with the correct float

Question 19

For the adjacency matrix of a digraph:

Answer 19

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

Question 20

Complete

Answer 20

every possible pair of vertices is connected by an edge

Question 21

isomorphic

Answer 21

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

Question 22

bipartite graph

Answer 22

vertices divided into two sets

Question 23

connected

Answer 23

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

Question 24

route

Answer 24

a walk, trail or path

Question 25

walk

Answer 25

set of edges in order

Question 26

trail

Answer 26

a walk where no edge is repeated

Question 27

path

Answer 27

a trail where no vertices are repeated

Question 28

cycle

Answer 28

a closed trail

Question 29

network

Answer 29

a graph with weights

Question 30

eulerian network

Answer 30

all nodes have an even order

Question 31

semi eulerian network

Answer 31

two nodes have odd order, the rest have even order

Question 32

minimum spanning tree algorithms

Answer 32

kruskals and prims

Question 33

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

Answer 33

determine if the graph is eulerian or not

Question 34

prims algorithm from a table

Answer 34

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

Question 35

finding the shortest path

Answer 35

Dijkstras

Question 36

colouring argument

Answer 36

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

Question 37

uses of colouring arguments

Answer 37

to see if a graph is bipartite

Question 38

Hamiltonian path

Answer 38

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

Question 39

Hamiltonian cycle

Answer 39

a cycle which visits every vertex

Question 40

Hamiltonian graph

Answer 40

a graph with a Hamiltonian cycle

Question 41

Use of ores theorum

Answer 41

determines if a graph is hamiltonian

Question 42

Ores theorum

Answer 42

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)

Question 43

if ores theorem is not true

Answer 43

the graph may still be Hamiltonian

Question 44

planar

Answer 44

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

Question 45

Eulers formula

Answer 45

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

Question 46

Use of Eulers formula

Answer 46

if the graph satisfies eulers formula then the graph is planar

Question 47

Kuratowski's theorum

Answer 47

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

Question 48

Use of Kuratowski's theorum

Answer 48

determining if a graph is planar

Question 49

Thickness

Answer 49

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

Question 50

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

Answer 50

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

Question 51

Finding the lower bound for a travelling sales person problem

Answer 51

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

Question 52

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

Answer 52

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

Question 53

planar graph thickness

Answer 53

1

Question 54

How to find the upper bound for the travelling salesperson problem

Answer 54

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

Question 55

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

Answer 55

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

Question 56

Ores Theorum

Answer 56

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)