Posted by: jpend9 | October 3, 2010

Trees recap

(Guest post by JP Endaya)

On Friday’s lecture we began discussing more about trees. We said that a tree is a connected undirected graph with no cycles.

We took a look at a rooted tree, which is an upside down tree,  for the structure of a tree.


We pick any vertex as root and let the rest of the tree hang under gravity.

On the lecture slide graph, we declared a vertex a parent if it directly precedes another vertex(which in turn is a child).

  • SG’s parent = AC
  • AC’s child = SG

We were then presented with a question: How many rooted trees can an n vertex tree have?

The answer is n because, as mentioned earlier, we can pick any vertex as a root.

For the rest of the discussion we tried to “Prove n vertex tree has n-1 edges.”

CLAIM: Let G=(V,E) be a tree with |V|=n. Then |E|=n-1.

Proof idea:

  • Root G at some vertex
  • Direct each edge towards the root
  • Each (directed) uniquely corresponds (“starts” off) from a non-root
  • => |E| = # non-roots = n-1

Proof:

  • Pick any r ϵ V as root
  • Root G at r
  • Direct each edge towards r

Lemma:

  • Each directed edge has a unique “starting” point and vice versa
  • => for every e ϵ E → v ϵ V \ {r}
  • => for every v ϵ V\ {r} → e ϵ E
  • => |E| = |V\ {r} | = n-1

Proof idea for Lemma: By contradiction

  • Every edge has one vertex, r in our example, as its starting point.
  • Contradiction: a cycle u, x~r~y, u where “~” represents a path between x and r and y and r and both x and y are connected to u.

We did not prove the Lemma but began looking at connection on large graphs and on the slide were asked if s and t are connected  . We considered the brute-force algorithm where we list all possible vertex sequences between s and t and check if any is a path between s and t. We also agreed that there is n^n such sequences.






Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: