Posted by: yogeshpa | October 5, 2010

## Lecture on 10-4-10

(Guest post by Yogesh Patel)

Announcements

Final Exam Room and Time posted Dec 14th 2010 at 3:30pm-6:30pm in Knox 104
Midterm Oct 18th 2010 in class
Dr Rudra post sample Midterm Exam online this week
Graded Homework #2 will be returned on Wednesday.
New Category on course blog “Not Student Posts”

Lecture Oct 4th 2010

We started off today’s lecture by trying to find a way to know if two nodes s and t are connected in a graph.  We remember from previous lectures that if we try a “brute-force” approach to solving this problem, we could list all possible paths between s and t, then check to see if there actually exists a path starting at s and ending at t (or vice versa). However, this approach yields n! sequences. Therefore we must find a more efficient way of doing so.

Then, to continue our definitions of graph notation, we defined the Distance between u and v as being the length of the shortest path between u and v, where the length is the number of edges.

This lead us into the discussion of Breath First Searches (BFS). This is an answer to the question “is s connected to t?” To answer this question, a BFS will build layers of vertices connected to s. The notation is as follows:

L0 = {s} where L0 is the layer index and {s} is the set of nodes connected at that layer.
This means that in a general sense L is the layer index of all nodes that have a distance j from s.

Here’s how the tree is constructed:

If you are to assume that the layer indices L0,…,Lj have been constructed, then
Lj+1­ is the set of vertices that have not yet been chosen but are connected to Lj
You then stop when the new layer is empty.

If starting from scratch, you would only have L0 = {s} where s is the root node, therefore j=0 in this instance and Lj+1 would be all the nodes connected to s with a distance of 1.

BFS Tree

BFS naturally defines a tree rooted at s.

Lj forms the jth “Level” in the tree.

U in Lj+1 is ca child if v in Lj from which it was “Discovered”

The following graph has 8 vertices.

We then built the BFS tree from this graph starting at root = {1}
Therefore L0={1}, and all nodes connected to node 1 are at L1. This means L1={2, 3}. Similarly for the next layers, L2 = {4, 5, 7, 8}, and L3={6}. The tree stops here because there are no more nodes in the graph connected to any of the nodes in the lowest layer.

There are a couple of ideas you can draw from making a BFS Tree:
1. If node t is in a BFS tree rooted at node s, then s is connected to t.
2. If there are n vertices in the original graph, the layer index j can be at most n-1 (because there can be at most n-1 edges in a graph—an edge connects two vertices)
3. A BFS Tree rooted at s will give all of the connected components of s.

As one of the puzzles presented, we were asked to prove that L has all nodes at distance j from s. This leads us into our next discussion where we actually did prove this in class.

We stated two propositions:

First, For all j >= 0 Lj consists of ALL vertices at distance j from s. t is connected to s if and only if there exists a j such that t is an element of Lj for 0 <= j =< n-1.

Secondly, Let T be a BFS tree for G = (V, E) when the root is s. There can also be a T for (V’, E’) where V’ is a subset of V and E’ is a subset of E (in the case that the subsets are not connected to the root). Then for all (u,v) element of E such that u is an element of Li and v is an element of Lj then i and j are within 1 of each other. Namely, |i-j|<=1.

Consider (u,v) is an element of E, u is an element of Li , and v is an element of Lj

(i)                  i = j we do not need to check because the distance is 0 therefore they are the same node

(ii)                 |i – j| =1 we do not need to check because the distance between the nodes is 1

(iii)               | i – j| > 1 we do check because this it means the distance between the two “adjacent” nodes is greater than 1

There exists an edge between u & v
v has to be in Li
v has to be added in Li + 1. This is a contradiction because if |i-j|>1 then j does not equal i+1 and v cannot exist in both Li+1 and Lj at the same time. This is a similar case if v is in Li and u is in Lj.