*(Guest post by Yogesh Patel)*

Announcements

Final Exam Room and Time posted Dec 14^{th} 2010 at 3:30pm-6:30pm in Knox 104

Midterm Oct 18^{th} 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 4^{th} 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:

L_{0} = {s} where L_{0} is the layer index and {s} is the set of nodes connected at that layer.

This means that in a general sense L_{j} 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 L_{0},…,L_{j} have been constructed, then

L_{j+1} is the set of vertices that have not yet been chosen but are connected to L_{j}

You then stop when the new layer is empty.

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

BFS Tree

BFS naturally defines a tree rooted at s.

L_{j} forms the j^{th} “Level” in the tree.

U in L_{j+1} is ca child if v in L_{j} 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 L_{0}={1}, and all nodes connected to node 1 are at L_{1}. This means L_{1}={2, 3}. Similarly for the next layers, L_{2 }= {4, 5, 7, 8}, and L_{3}={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_{j} 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 L_{j} 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 L_{j} 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 L_{i} and v is an element of L_{j} then i and j are within 1 of each other. Namely, |i-j|<=1.

Proof idea: By contradiction

Consider (u,v) is an element of E, u is an element of L_{i }, and v is an element of L_{j }

(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 L_{i }

v has to be added in L_{i }+ 1. This is a contradiction because if |i-j|>1 then j does not equal i+1 and v cannot exist in both L_{i+1} and L_{j }at the same time. This is a similar case if v is in L_{i} and u is in L_{j}.

## Leave a Reply