Distance and Scheduling

Question 1

edge weight:

Answer 1

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

Question 2

weight of the walk:

Answer 2

(l)Σ(j=1)w(ej)

Question 3

d(a,b):

Answer 3

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

Question 4

sssp:

Answer 4

given a source vertex, find the distance between it and every other vertex
single source shortest path

Question 5

all pairs shortest path:

Answer 5

find the distances between every vertex and every other vertex

Question 6

bfs:

Answer 6

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

Question 7

bellman’s equations:

Answer 7

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

Question 8

powers of the adjacency matrix count walks and proof:

Answer 8

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

Question 9

tropical arithmetic:

Answer 9

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

Question 10

tropical arithmetic is:

Answer 10

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)

Question 11

tropical matrix sum:

Answer 11

given 2 mxn matrices A and B, A⊕B
(A⊕B)ij=Aij⊕Bij

Question 12

tropical matrix product:

Answer 12

given 2 mxn matrices A and B, A⊗B
(A⊗B)ij=(n)⊕(k=1)Aik⊗Bkj=min(1<=k<=n)(Aik+Bkj)

Question 13

tropical matrix powers:

Answer 13

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)

Question 14

weight matrix:

Answer 14

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

Question 15

weight of a minimal walk from vi to vj:

Answer 15

d(vi,vj)=Wij^(⊗(n-1)) where n is the number of vertices in the graph

Question 16

scheduling basics:

Answer 16

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

Question 17

how to find the shortest time between the start and a task dependency vertex:

Answer 17

find the maximal weight path

Question 18

topological ordering:

Answer 18

/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

Question 19

sink and proof:

Answer 19

/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

Question 20

how to compute earliest start of a vertex tv:

Answer 20

tv=max{tu+w(u,v)} - just gotta go through everything from the start to get the tu required
tS=0

Question 21

how to compute the latest start of a vertex tv without delaying the whole project:

Answer 21

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))

Question 22

critical path:

Answer 22

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