Optimality Flashcards
Weighted graph?
For a weighted graph, W is?
For a weighted graph, length of W
=?
Suppose the shortest path v_0 -> u -> v_i between two vertices in a weighted graph via an intermediate vertex u, then?
Both subpaths v_0 -> u and u-> v_i or shortest path between their respective vertices
Complexity of Djikstra’s algorithm?
O(|V|2)
Crucial technique in Dijkstras algorithm
Relabelling, shortest distance
Requirement for Kruskal’s algorithm
G is always a simple, connected weighted graph
Minimal, spanning tree
MST is a tree T whose total degree is minimal among all spanning trees
Kruskal’s algorithm
1) sort all the edges in non-decreasing order of weight
2) create a forest of single node trees were each node is a separate tree
3) starting with the smallest weight edge. Add edges to the forest, one at a time while ensuring that the edge doesn’t create a cycle. 
For a graph G, if G is a tree <=>
G does not have any cycles, but adding any further edge yields a unique cycle <=> any two vertices of G are connected by unique path <=> G is connected, and every edge of G is a bridge
Let T be a tree in graph G. Let e be an edge not in T. Then T u {e} ?
Contains a unique cycle denoted C_T (e)
Incidence matrix of a graph
Let G be a Diagraph with N vertices then the incidence matrix of G has rank?
<= n-1
A Diagraph G with incidence matrix A is a forest if?
And only if the columns of A are linearly independent
Let G be a Diagraph with n vertices and p connected components then the incident matrix A of G?
Rank = n-p
Let A be The incidence matrix of a digraph G
Then A is totally unimodular (each square submatrix has determinant 0 or +-1)
Let G be a digraph with n vertices and n - 1 edges. Let B be the matrix which arises from the incidence matrix A of G by deleting an arbitrary row. If G is a tree?
Then det(B) = 1 or -1, otherwise det(B) = 0
Matrix tree theorem
Let B be the matrix arising from the incidence matrix of a Diagraph G by deleting an arbitrary row. Then the number of spanning trees of G is det(BB^T)
A = adj matrix of G, M = incidence matrix of an arbitrary orientation H of G. Use the same ordering of the vertices for rows and columns of both matrices
MM^T = L where L is Laplacian of G
Let A be the adj matrix of G, then Laplacian is given?
Laplacian<=> Riskoff
L=D-A
c(G)=?
Number of connected components of G = n - rank(L) = dim(Ker(L))
Kirchoff’s matrix tree theorem
?
Complete graph K_n has ? Spanning trees
n^(n-2)
An orientation is?
An undirected graph that has a direction assigned to each edge
