Graphs

Relevant Course:  Advanced Data Structures and Algorithms

Relevant Department : Electrical Engineering

Relevant Semester: 5th

Pre-requisite: Knowledge of Data Structures and Algorithm is Preferable.

Course Description & Outline :

  • Elementary Graph Algorithms: Representations of Graphs 
  • Breadth First Search and Depth-First Search. Strongly Connected Components
  • Minimum Spanning Trees: Growing a Minimum Spanning Tree; Kruskal and Prim
  • Problem sheet based on BFS, DFS, MST and shortest path algorithms (Dijkstra and Bellman Ford).
  • Maximum Flow: Flow Networks; The Ford-Fulkerson method; Maximum Bipartite Matching

Schedule for Lecture Delivery

Session 1 : 07-Sep-2015 (10-12 noon)

Session 2 : 08-Sep-2015 (10-12 noon)

Session 3 : 10-Sep-2015 (10-12 noon)

Teacher Forum

Slides for Session 1

Session 1

Introduction:How Graphs fits into the Study of Algorithms and Data Structures

Graph Traversal : Breadth First Search

Applications of Breadth Breadth First Search
Graph Traversal : Depth First Search
Applications of Depth First Search
Directed Graphs : Applications of Depth First Search 

 

Forum for Session 1

Forum for Session 1

Forum not available

Slides for Session 2

Session 2

Summary

Greedy Algorithm

Graphs with Negative Edge Weights

Bellman-Ford Algorithm

Minimun Spanning Trees (MST)

Problem Set

Forum for Session 2

Forum for Session 2

Forum not available

Slides for Session 3

Session 3

Summary

S-t flow

Ford-Fulkerson Algorithm

Example of an Application of Network Flow.

Forum for Session 3

Forum for Session 3

Forum not available

Problem Set

Quiz I

Quiz I 

Quiz not avilable

Quiz II

Quiz II

Quiz not avilable

Quiz III

Quiz III

Quiz not avilable

Assignment

Find all cut vertices in a graph

A cut-vertex of a graph is a vertex   such that if it is removed from the   graph, it will disconnect the graph (or if the   graph is already  connected, then it increases the   number of connected   components by

1) l Find all the cut vertices using DF S

Hint: A vertex v will be a cut vertex if there is no back edge from a descendant of v to a proper ancestor of v

Find all the SCCs in a directed graph

Find all the SCCs in a directed graph   using DF S

Hint: cross edges ruin the low value counts   If we can ignore cross edges, we should be able to use low value count

Currency trading

  • Given a set of n currencies 1,2,...,n,
    • A currency  trader can exchange a fixed quantity of  money from one currency  to  another

    • rij is the exchange rate for converting i to j (i.e. 1 unit of  i will give rij  units of j)

    • An opportunity cycle for the trader is a sequence of currency trades which start from a currency k and returns back to the same currency k but with a larger sum of  money that the trader started with.

    • Write an algorithm to detect if there is an  opportunity cycle in a set of currencies

  • Write an algorithm to detect if there is an opportunity cycle in a set of currencies

Hint: Does n't this problem look like the Bellman-Ford algorithm?

Assignment not available

Solutions

Page view resticted for students

Exercises

DF S = BF S

  • Suppose we do a BFS of a graph starting at s and get the tree T (of non dotted edges)
  • Then we run DFS on the same graph starting again at s, and we get the same tree T (of non dotted edges)
  • Show that the graph must be exactly equal to T, i.e. that there are no dotted edges at all when we  run BF S or DF S

Hint: Look at the BF S level structure.

Determine if an edge is in any MST

  • Given a graph G = (V,E) with n vertices and m  edges.
  • Assume that the  edges have  costs which are all distinct
  • We are given a specific edge e.
  • How would you write an algorithm that determines whether e is part of any MST?
  • Algorithm returns false if e is not part of any MST, else  returns true

Hint: An edge e=(u,v) is not in any MST if there is a path from u to v that is made up entirely of edges with costs less than the cost of e

Constraint solving using Bellman-Ford

Hint: Write as constraint graph and use Bellman-Ford

Max matching using network flow

For the bipartite graph G = (V,E) with

V = {a1, a2, a3, a4, b1, b2, b3, b4} and
E = { (a1,b1), (a1,b4), (a2,b2), (a2,b3), (a3,b2), (a4,b1), (a4,b2) },
show how you can use network flow to find the maximum bipartite matching. If the first two augmentation paths resulted in the matching (a1,b1), (a2,b2), illustrate the subsequent augmentation steps and how the matching is modified at each of these steps. 

Solutions

Page view resticted for students
Table of Contents