Posted by: atri | September 28, 2012

## Lect 12: Trees

Today we proved that a tree with $n$ nodes has exactly $n-1$ 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.

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 $G=(V,E)$, a subset $S\subseteq V$ is called a connected component if the following are true

1. For any two vertices $u,w\in S$, $u$ and $w$ are connected; and
2. For any vertices $u\in S$ and $x\in V\setminus S$, $u$ and $x$ 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.