Graphs/ Networks Flashcards
event where more than one activity starts
burst event
event where more than one activity ends
merge event
Dummy Activity
an activity that has zero duration
need for dummies:
- to prevent activities starting and finishing on the same node
- make it possible to draw the correct dependencies
earliest event times
- 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
latest event times
- backwards pass
- the smallest value you can get
critical activities
LET - EET - duration = 0
changing the duration will effect the overall minimum project completion time
minimum project completion time
duration of the longest path on the network
float
spare time associated with an activity
total float =
LET (i) - EET (j) - duration
float of a critical activity =
= 0
independent float =
EET (j) - LET (i) - duration
interfering float =
total float - independent float
Independent float
an activity can increase by x amount of time without effecting the minimum completion time
interfering float
a group of activities can increase by a set amount of time
float in cascade
dotted lines to show how an event can be moved
critical activities on a cascade chart
all in one row, other activities above on a different row depending on dependencies
Drawing cascade diagrams
- critical activities in order on a single row
- each activity on its own row with the correct float
For the adjacency matrix of a digraph:
Read in rows i.e. if there’s a weight in row A and column B Then the edge goes from A to B
Complete
every possible pair of vertices is connected by an edge
isomorphic
If two graphs look different but they are structurally the same (in terms of the connections between the vertices)
bipartite graph
vertices divided into two sets
connected
if every vertex can be reached from every other vertex by going along edges
route
a walk, trail or path
walk
set of edges in order
trail
a walk where no edge is repeated
path
a trail where no vertices are repeated
cycle
a closed trail
network
a graph with weights
eulerian network
all nodes have an even order
semi eulerian network
two nodes have odd order, the rest have even order
minimum spanning tree algorithms
kruskals and prims
how to find a route that travels along every edge of network without repeating edges
determine if the graph is eulerian or not
prims algorithm from a table
- choose the start vertex e.g. A, label the column A 1, and delete row A. Select the smallest entry in column A
- Whichever row the entry is in e.g. B, label the column B 2 and delete row B
- repeat until all the rows have been crossed out and each column has been labelled
finding the shortest path
Dijkstras
colouring argument
assigning each vertex a colour which is different to the neighbouring vertices with the aim of using the smallest amount of colours
uses of colouring arguments
to see if a graph is bipartite
Hamiltonian path
visits each vertex once and only once starting and finishing on different vertices
Hamiltonian cycle
a cycle which visits every vertex
Hamiltonian graph
a graph with a Hamiltonian cycle
Use of ores theorum
determines if a graph is hamiltonian
Ores theorum
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)
if ores theorem is not true
the graph may still be Hamiltonian
planar
A graph is planar if it can be drawn in two dimensions without any edges crossing
Eulers formula
V + R = E + 2
V = number of vertices
R = number of distinct regions
E = number of edges
Use of Eulers formula
if the graph satisfies eulers formula then the graph is planar
Kuratowski’s theorum
A graph is planar if an only if it does not contain a sub graph of K5 or K3,3
Use of Kuratowski’s theorum
determining if a graph is planar
Thickness
The number of layers that are needed to draw a graph without any crossing edges
Finding the most efficient route that goes to each node on a network if the graph is not eurlerian
- find the total of all the weights
- identify all the odd vertices
- pair all the odd vertices in all the possible ways and work out the weights
- identify the pairing where the total weight is the shortest and add this to the total weights for the network
Finding the lower bound for a travelling sales person problem
- remove a vertex and all its associated edges
- find a minimum spanning tree for the remaining network
- replace the vertex aswell as its two shortest vertices
- the result is the lower bound
If the lower bound method for the travelling sales person problem gives a tour then…
if the tour is a hamiltonian cycle then this tour is optimal
planar graph thickness
1
How to find the upper bound for the travelling salesperson problem
nearest neighbour:
- choose a starting node
- choose the smallest arc from this node to a node not yet in the tour
- repeat until all nodes are in the tour
- add an arc back to the starting node
for a non Eulerian network the shortest tour starts and finishes on the…
odd degree vertices ( because only the odd degree vertices which it doesn’t start/ finish on have to be repeated)
Ores Theorum
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)
