Scribd
Upload
12 views2 pages

Tut - 2 Graphs

tutorial on graphs

Uploaded by

saem habeeb
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views2 pages

Tut - 2 Graphs

tutorial on graphs

Uploaded by

saem habeeb
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Week 2: Graphs, BFS, DFS, and their applications

Specific topics:
Introduction to Graphs, BFS, DFS, Applications of BFS and DFS: connectivity, strong connectivity, bipar-
tite testing, topological ordering etc.
1. Consider the following directed graph G and answer the following:

(a) Is G a DAG?
(b) Find the number of Strongly Connected Components of G.
(c) Also, find all the Strongly Connected Components.
2. A binary tree is a rooted tree in which each node has at most two children. Show that in any binary
tree, the number of nodes with two children is exactly one less than the number of leaves.
3. For an undirected simple graph G = (V, E), let δ(G) = minv ∈V d(v ). Prove the following:
(a) If δ(G) ≥ k then G has a simple path of length at least k.
(b) If δ(G) ≥ k ≥ 2 then G contains a cycle of length at least k + 1.
4. Design and analyze an algorithm for the following: Given a tree T , rooted at a vertex r , determine
the relationship between any pair of vertices u and v (ancestor/descendant/none) in T .
5. Prove that a directed graph G is strongly connected if and only if each partition of the vertex set of
G into nonempty sets S and T has an edge from S to T .

1
6. Prove that every tree with maximum degree ∆ > 1 has at least ∆ vertices of degree 1.
7. Given an undirected, connected graph G = (V, E), a bridge in G is an edge whose removal disconnects
the graph. Design an O(|V |+|E|)-time algorithm for finding all bridges of G. Prove that the algorithm
is correct.
8. Let G be a directed acyclic graph and let s and t be two vertices G. Design an efficient algorithm to
determine whether the number of paths in G from s to t is odd or even. Prove that the algorithm
is correct and analyze its running time in terms of |V | and |E|.

You might also like