Lecture on 10-4-10

(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₀ = {s} where L₀ 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₀,…,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₀ = {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₀={1}, and all nodes connected to node 1 are at L₁. This means L₁={2, 3}. Similarly for the next layers, L₂ = {4, 5, 7, 8}, and L₃={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.