# Optimality Flashcards

1
Q

Weighted graph?

A
2
Q

For a weighted graph, W is?

A
3
Q

For a weighted graph, length of W
=?

A
4
Q

Suppose the shortest path v_0 -> u -> v_i between two vertices in a weighted graph via an intermediate vertex u, then?

A

Both subpaths v_0 -> u and u-> v_i or shortest path between their respective vertices

5
Q

Complexity of Djikstra’s algorithm?

A

O(|V|2)

6
Q

Crucial technique in Dijkstras algorithm

A

Relabelling, shortest distance

7
Q

Requirement for Kruskal’s algorithm

A

G is always a simple, connected weighted graph

8
Q

Minimal, spanning tree

A

MST is a tree T whose total degree is minimal among all spanning trees

9
Q

Kruskal’s algorithm

A

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. ￼

10
Q

For a graph G, if G is a tree <=>

A

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

11
Q

Let T be a tree in graph G. Let e be an edge not in T. Then T u {e} ?

A

Contains a unique cycle denoted C_T (e)

12
Q

Incidence matrix of a graph

A
13
Q

Let G be a Diagraph with N vertices then the incidence matrix of G has rank?

A

<= n-1

14
Q

A Diagraph G with incidence matrix A is a forest if?

A

And only if the columns of A are linearly independent

15
Q

Let G be a Diagraph with n vertices and p connected components then the incident matrix A of G?

A

Rank = n-p

16
Q

Let A be The incidence matrix of a digraph G

A

Then A is totally unimodular (each square submatrix has determinant 0 or +-1)

17
Q

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?

A

Then det(B) = 1 or -1, otherwise det(B) = 0

18
Q

Matrix tree theorem

A

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)

19
Q

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

A

MM^T = L where L is Laplacian of G

20
Q

Let A be the adj matrix of G, then Laplacian is given?

A

Laplacian<=> Riskoff
L=D-A

21
Q

c(G)=?

A

Number of connected components of G = n - rank(L) = dim(Ker(L))

22
Q

Kirchoff’s matrix tree theorem
?

A
23
Q

Complete graph K_n has ? Spanning trees

A

n^(n-2)

24
Q

An orientation is?

A

An undirected graph that has a direction assigned to each edge