Distance and Scheduling Flashcards
edge weight:
a little label on an edge that signifies well. weight
w:E->real number
w(a,b)=weight of the edge between a and b
weight of the walk:
(l)Σ(j=1)w(ej)
d(a,b):
distance/metric between a and b
min{w(a)|a is a walk from a to b}
if there is no walk, d(a,b) is infinite
also no negative weights allowed
d(a,a)=0 for all a
it’s the weight of a minimal weight walk from a to b
sssp:
given a source vertex, find the distance between it and every other vertex
single source shortest path
all pairs shortest path:
find the distances between every vertex and every other vertex
bfs:
breadth first search
used to solve sssp problems
label the source vertex 0
label all neighbours 1
label all neighbours of those neighbours that don’t already have a label 2
repeat until all vertices are labelled
bellman’s equations:
take an sssp problem with |V|=n
source vertex is called v1
take all the weights and make a matrix such that wk,j=w(vk,vj) if vk,vj is an edge, and infinity otherwise
the quantities uj=d(v1,vj) satisfy the equations u1=0 and uj=min(uk+wk,j) (k!=j) for all 2<=j<=n
if all cycles in G have positive weight, then the equations have a unique solution
powers of the adjacency matrix count walks and proof:
take G, |V|=n, with adjacency matrix A
A^(l+1)=A^(l)A and A^0=In
Aij^l=the number of walks of length l from vertex i to j
base case - l=1, A^l=A
hypothesis - this is true for all l<=l0
induction - consider Aij^(l0+1)=(n)Σ(k=1)Aik^(l0)Akj
the only nonzero entries in this sum are when both Aik^(l0) and Akj are nonzero
the only possible nonzero value for Akj is 1, when that edge exists
by the hypothesis, Aik^l0 is the number of distinct length=l0 walks from i to k, and if we add the edge (k,j) to the end of one of those, we get a walk from i to j
every walk of length l0+1 from i to j must consist of a length l0 walk from i to a neighbour/predecessor k of j, followed by that final step
and that’s the end apparently
tropical arithmetic:
on the set of the union of the real numbers and infinity (the real numbers and also infinity)
first binary operation is ⊕, x⊕y=min{x,y}
second is ⊗, x⊗y=x+y
x⊗infinity=infinity
tropical arithmetic is:
commutative - x⊗y=y⊗x, x⊕y=y⊕x
associative - x⊕(y⊕z)=(x⊕y)⊕z, same for ⊗
identity element for ⊗ is 0, identity element for ⊕ is infinity - for both if you chuck in a and the identity element, you get a
a⊗(b⊕c)=(a⊗b)⊕(a⊗c) (doesn’t work if the signs are switched)
tropical matrix sum:
given 2 mxn matrices A and B, A⊕B
(A⊕B)ij=Aij⊕Bij
tropical matrix product:
given 2 mxn matrices A and B, A⊗B
(A⊗B)ij=(n)⊕(k=1)Aik⊗Bkj=min(1<=k<=n)(Aik+Bkj)
tropical matrix powers:
B^(⊗k+1)=B^(⊗k)⊗B and B^(⊗0)=In, where In is the tropical identity matrix (all values are infinity except the main diagonal which is 0)
weight matrix:
Wk,j=0 if k=j, w(vk,vj) if (vk, vj) is an edge, infinity otherwise
Wk,j^(⊗l) is the weight of a minimal weight walk from k to j, containing at most l edges, 0 and infinity rules from above still apply just for walks instead of edges
weight of a minimal walk from vi to vj:
d(vi,vj)=Wij^(⊗(n-1)) where n is the number of vertices in the graph
scheduling basics:
each task is a vertex
each weight is the time/whatever it takes for the task at the Tail
a start and end vertex, the only vertices with deg(in)(v)=0 and deg(out)(v)=0 respectively
directed edges show prerequesite tasks for the tasks they lead to
if there is a cycle, cry
note that we are pretending we have all the basic resources we need
how to find the shortest time between the start and a task dependency vertex:
find the maximal weight path
topological ordering:
/topological sorting, of G
a map a:V->{1,2,…,n} such that
a(v)=a(u) -> v=u
(u,v) in E -> a(u)<(a(v)
basically numbering the vertices such that the edges always point from vertices with smaller indexes to vertices with bigger ones
they aren’t unique but there is always at least one
sink and proof:
/sink vertex
if G is a directed acyclic graph, it contains at least one vertex v with deg(out)(v)=0, that’s the sink
proof - pick a vertex, if deg(out)(v)=0, you’re done, if not, pick a successor, check if the degree is 0, continue until you reach one. this will never revisit a vertex cause G is acyclic, and as G has finite vertices, construction must end after |V|-1 steps, which means there must be a sink cause the only way to end is to find it
how to compute earliest start of a vertex tv:
tv=max{tu+w(u,v)} - just gotta go through everything from the start to get the tu required
tS=0
how to compute the latest start of a vertex tv without delaying the whole project:
Tv is the time that the task v must be started in order to not delay the whole project
Tv=min(Tu-w(u,v))
critical path:
a maximal weight path from the start vertex to the end one, isn’t unique
basically the tasks for which the latest and earliest start are the same, they have to start as early as possible to avoid delaying the whole thing