Posted by: **atri** | September 28, 2012

## Lect 12: Trees

Today we proved that a tree with nodes has exactly edges. We then started with designing an algorithm to decide whether two given vertices are connected or not. This material is from Section 3.1 and 3.2 in the book. Next lecture, we are going to formally state the Breath First search and prove some interesting properties about the algorithm (and its correctness).

The slides and notes for the lecture have been uploaded.

Here is the link to sign up mock interviews that Andy talked about at the beginning of the lecture.

Also I did not get around to defining (connected) component in class today. It is needed for the first question on HW 4: please go ahead and read up the definition from the book. In short here is the definition: given a graph , a subset is called a connected component if the following are true

- For any two vertices , and are connected; and
- For any vertices and , and are
**not** connected.

In the news caster graph that we have seen in the slides, there are two connected components: one with the American newscasters and the other with the Indian newscasters.

If you have any questions, please post them on piazza.

### Like this:

Like Loading...

*Related*

## Leave a Reply