Gullu - Optimal Substructure and Handshaking Lemma

Question 1

The edge a->b emanates from

Answer 1

a

Question 2

The edge a->b is incident to

Answer 2

b

Question 3

Adjacent Vertices

Answer 3

(in a->b the vertex b is adjacent to a)

Question 4

Out-Degree of a Vertex:

Answer 4

Number of edges emanating from a node. Written as |A(v)|

Question 5

In-Degree of a Vertex:

Answer 5

Number of edges incident on a node. Written as |I(v)|

Question 6

The subgraph S of a graph G is a graph where

Answer 6

• Each vertex in S is a vertex V of G
• Each edge in S is a subset of the edges in G, and each vertex in edges of S is a vertex in S (implied because subgraph is a graph).

Question 7

Connected Graph

Answer 7

There is a path between every pair of vertices.

Question 8

Graph Representations

Answer 8

Common representations are the adjacency list and the adjacency matrix. Suppose the vertices of a graph are labelled with numbers 0 to n-1…

Question 9

Adjacency List

Answer 9

• Adjacency List would then be a 2D array (n by n) of Boolean values
• A[i,j] true if there is an edge from i to j
• If a graph is unweighted then a value in the matrix is the weight
• If the graph is undirected, then A[i,j] = A[j,i]. This will make the matrix symmetrical about the diagonal.

Question 10

Adjacency Matrix

Answer 10

the space complexity is O(|v|^2). This is irrespective of the number of edges in the graph. If |E| < |V^2| then the matrix will be sparse and inefficient, most values will be zero.

Question 11

Suitability: Consider the operation of determining whether there is an edge between two vertices v1 and v2:

Answer 11

In adjacency matrix: Examine value of A[v1,v2]

In adjacency list: Locate v1 in the primary list, look for v2 in secondary list

Winner: Adjacency Matrix

Question 12

Suitability: Find all vertices adjacent to a vertex v1 in a graph having n vertices

Answer 12

In adjacency matrix: Go to row for v1 and iterate over n columns

In adjacency list: Go to element v1 and the secondary list is the list of adjacency vertices

Winner: Adjacency list

Question 13

The handshaking lemma

Answer 13

For undirected graphs, For example: There is a party in which some people shake hands, If i shake someones hand it follows that they shook my hand. There will be an even number of handshakes.

Question 14

Spanning Trees

Answer 14

Concerns undirected and connected graph. A spanning tree is a tree that connects all the vertices in a graph and uses some edges.

Question 15

The minimum spanning tree

Answer 15

Concerns connected and undirected graphs, The graph is weighted (edge weight function w:E->R).
The width of a spanning tree in the graph is the sum of weight it uses.
The minimum spanning tree is the spanning tree in the graph having the smallest weight.

Question 16

Claim: MSTs have optimal substructure.

Derivations from proof:

Answer 16

If we repeatedly connect a subtree of an MST to the rest of the graph and always pick the smallest weight edge to do so, we’ll end up with the MST for the graph.

Question 17

Prim’s Algorithm

Answer 17

• Create a priority queue Q that contains the vertices (v-a) where:
• The weight of a node in Q is the lightest node going to a vertex in A
• Initially A is empty
• The weight of each node in Q will be ∞

So far…
- Q contains all of V (V-A actually, but A is empty)
- All weight of the nodes in Q ∞

• Pick any node in Q and set its weight zero

Question 18

Total running time (Prim’s Algorithm)

Answer 18

O(V) x TimeTo(DequeueMin) + O(E) x TimeTo(UpdateKey). TimeTo() depends on the data structure we use to implement the queue