# 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