Optimality

Question 1

Weighted graph?

Answer 1

Question 2

For a weighted graph, W is?

Answer 2

Question 3

For a weighted graph, length of W
=?

Answer 3

Question 4

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

Answer 4

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

Question 5

Complexity of Djikstra’s algorithm?

Answer 5

O(|V|²)

Question 6

Crucial technique in Dijkstras algorithm

Answer 6

Relabelling, shortest distance

Question 7

Requirement for Kruskal’s algorithm

Answer 7

G is always a simple, connected weighted graph

Question 8

Minimal, spanning tree

Answer 8

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

Question 9

Kruskal’s algorithm

Answer 9

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. 

Question 10

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

Answer 10

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

Question 11

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

Answer 11

Contains a unique cycle denoted C_T (e)

Question 12

Incidence matrix of a graph

Answer 12

Question 13

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

Answer 13

<= n-1

Question 14

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

Answer 14

And only if the columns of A are linearly independent

Question 15

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

Answer 15

Rank = n-p

Question 16

Let A be The incidence matrix of a digraph G

Answer 16

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

Question 17

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?

Answer 17

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

Question 18

Matrix tree theorem

Answer 18

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)

Question 19

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

Answer 19

MM^T = L where L is Laplacian of G

Question 20

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

Answer 20

Laplacian<=> Riskoff
L=D-A

Question 21

c(G)=?

Answer 21

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

Question 22

Kirchoff’s matrix tree theorem
?

Answer 22

Question 23

Complete graph K_n has ? Spanning trees

Answer 23

n^(n-2)

Question 24

An orientation is?

Answer 24

An undirected graph that has a direction assigned to each edge