15 251 Great Theoretical Ideas in Computer Science Upcoming Events Review Session on Saturday 5 pm Wean 5409 Test on Monday Election Day Graphs Lecture 18 October 23 2008 What s a tree What s a tree A tree is a connected graph with no cycles Tree Not aTree Not a Tree Tree How Many n Node Trees How Many n Node Trees 1 How Many n Node Trees 1 How Many n Node Trees 1 2 How Many n Node Trees 1 2 How Many n Node Trees 1 2 3 How Many n Node Trees 1 2 3 How Many n Node Trees 1 2 3 4 How Many n Node Trees 1 2 3 4 How Many n Node Trees 1 2 3 4 How Many n Node Trees 1 2 3 4 5 How Many n Node Trees 1 2 3 4 5 How Many n Node Trees 1 2 3 4 5 How Many n Node Trees 1 2 3 4 5 We ll pass around a piece of paper Draw a new 8 node tree and put your name next to it There are 23 of them The Shy People Party At the shy people party people enter one by one and as a person comes in s he shakes hand with only one person already at the party The Shy People Party At the shy people party people enter one by one and as a person comes in s he shakes hand with only one person already at the party Prove that at a shy party with n people n 2 at least two people have shaken hands with only one other person The Shy People Party Notation Notation In this lecture Notation In this lecture n will denote the number of nodes in a graph Notation In this lecture n will denote the number of nodes in a graph e will denote the number of edges in a graph Theorem Let G be a graph with n nodes and e edges Theorem Let G be a graph with n nodes and e edges The following are equivalent Theorem Let G be a graph with n nodes and e edges The following are equivalent 1 G is a tree connected acyclic Theorem Let G be a graph with n nodes and e edges The following are equivalent 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path Theorem Let G be a graph with n nodes and e edges The following are equivalent 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Theorem Let G be a graph with n nodes and e edges The following are equivalent 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 4 G is acyclic and n e 1 Theorem Let G be a graph with n nodes and e edges The following are equivalent 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 4 G is acyclic and n e 1 5 G is acyclic and if any two non adjacent points are joined by a line the resulting graph has exactly one cycle To prove this it suffices to show 1 2 3 4 5 1 1 2 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path 1 2 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path Proof by contradiction 1 2 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path Proof by contradiction Assume G is a tree that has two nodes connected by two different paths 1 2 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path Proof by contradiction Assume G is a tree that has two nodes connected by two different paths 1 2 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path Proof by contradiction Assume G is a tree that has two nodes connected by two different paths Then there exists a cycle 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Proof by induction 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Proof by induction Assume true for every graph with n nodes 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Proof by induction Assume true for every graph with n nodes Let G have n nodes and let x and y be adjacent 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Proof by induction Assume true for every graph with n nodes Let G have n nodes and let x and y be adjacent G1 x y G2 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Proof by induction Assume true for every graph with n nodes Let G have n nodes and let x and y be adjacent G1 x y G2 Let n1 e1 be number of nodes and edges in G1 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Proof by induction Assume true for every graph with n nodes Let G have n nodes and let x and y be adjacent G1 x y G2 Let n1 e1 be number of nodes and edges in G1 Then n n1 n2 e1 e2 2 e 1 3 4 3 G is connected and n e 1 4 G is acyclic and n e 1 3 4 3 G is connected and n e 1 4 G is acyclic and n e 1 Proof by contradiction 3 4 3 G is connected and n e 1 4 G is acyclic and n e 1 Proof by contradiction Assume G is connected with n e 1 and G has a cycle containing k nodes 3 4 3 G is connected and n e 1 4 G is acyclic and n e 1 Proof by contradiction Assume G is connected with n e 1 and G has a cycle containing k nodes k nodes 3 4 3 G is connected and n e 1 4 G is acyclic and n e 1 Proof by contradiction Assume G is …
View Full Document
Unlocking...