This preview shows page 1-2-3-4-5-6-7-8-9-10-11-78-79-80-81-82-83-84-85-86-87-88-157-158-159-160-161-162-163-164-165-166-167 out of 167 pages.
15-251Great Theoretical Ideas in Computer ScienceTest on MondayUpcoming EventsElection Day Review Session on Saturday (5 pm, Wean 5409)GraphsLecture 18, October 23, 2008What’s a tree?A tree is a connected graph with no cyclesWhat’s a tree?TreeNot aTreeNot a TreeTreeHow 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…)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 PartyAt 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 PartyThe Shy People PartyNotationNotationIn this lecture:NotationIn this lecture:n will denote the number of nodes in a graphNotationIn this lecture:n will denote the number of nodes in a graphe will denote the number of edges in a graphTheorem: Let G be a graph with n nodes and e edgesTheorem: Let G be a graph with n nodes and e edgesThe following are equivalent:Theorem: Let G be a graph with n nodes and e edgesThe following are equivalent:1. G is a tree (connected, acyclic)Theorem: Let G be a graph with n nodes and e edgesThe following are equivalent:1. G is a tree (connected, acyclic)2. Every two nodes of G are joined by a unique pathTheorem: Let G be a graph with n nodes and e edgesThe following are equivalent:1. G is a tree (connected, acyclic)3. G is connected and n = e + 1 2. Every two nodes of G are joined by a unique pathTheorem: Let G be a graph with n nodes and e edgesThe following are equivalent:1. G is a tree (connected, acyclic)3. G is connected and n = e + 1 4. G is acyclic and n = e + 12. Every two nodes of G are joined by a unique pathTheorem: Let G be a graph with n nodes and e edgesThe following are equivalent:1. G is a tree (connected, acyclic)3. G is connected and n = e + 1 4. G is acyclic and n = e + 15. G is acyclic and if any two non-adjacent points are joined by a line, the resulting graph has exactly one cycle2. Every two nodes of G are joined by a unique pathTo prove this, it suffices to show 1 => 2 => 3 => 4 => 5 => 11 => 2 1. G is a tree (connected, acyclic)2. Every two nodes of G are joined by a unique path1 => 2 1. G is a tree (connected, acyclic)2. Every two nodes of G are joined by a unique pathProof: (by contradiction)1 => 2 1. G is a tree (connected, acyclic)2. Every two nodes of G are joined by a unique pathProof: (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 pathProof: (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 pathProof: (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 path3. G is connected and n = e + 12 => 3 2. Every two nodes of G are joined by a unique pathProof: (by induction)3. G is connected and n = e + 12 => 3 2. Every two nodes of G are joined by a unique pathProof: (by induction)Assume true for every graph with < n nodes3. G is connected and n = e + 12 => 3 2. Every two nodes of G are joined by a unique pathProof: (by induction)Assume true for every graph with < n nodes3. G is connected and n = e + 1 Let G have n nodes and let x and y be adjacent2 => 3 2. Every two nodes of G are joined by a unique pathProof: (by induction)Assume true for every graph with < n nodes3. G is connected and n = e + 1 Let G have n nodes and let x and y be adjacentxyG1G22 => 3 2. Every two nodes of G are joined by a unique pathProof: (by induction)Assume true for every graph with < n nodes3. G is connected and n = e + 1 Let G have n nodes and let x and y be adjacentLet n1,e1 be number of nodes and edges in G1xyG1G22 => 3 2. Every two nodes of G are joined by a unique pathProof: (by induction)Assume true for every graph with < n nodes3. G is connected and n = e + 1 Let G have n nodes and let x and y be adjacentLet n1,e1 be number of nodes and edges in G1Then n = n1 + n2 = e1 + e2 + 2 = e + 1 xyG1G23 => 4 3. G is connected and n = e + 1 4. G is acyclic and n = e + 13 => 4 Proof: (by contradiction)3. G is connected and n = e + 1 4. G is acyclic and n = e + 13 => 4 Proof: (by contradiction)Assume G is connected with n = e + 1, and G has a cycle containing k nodes3. G is connected and n = e + 1 4. G is acyclic and n = e + 13 => 4 Proof: (by contradiction)Assume G is connected with n = e + 1, and G has a cycle containing k nodes3. G is connected and n = e + 1 4. G is acyclic and n = e + 1k nodes3 => 4 Proof: (by contradiction)Assume G is connected with n = e + 1, and G has a cycle containing k nodes3. G is connected and n = e + 1 4. G is acyclic and n = e + 1k nodesNote that the cycle has k nodes and k edges3 => 4 Proof: (by contradiction)Assume G is connected with n = e + 1, and G has a cycle containing k nodes3. G is connected and n = e + 1 4. G is acyclic and n = e + 1k nodesNote that the cycle has k nodes and k edgesStart adding nodes and edges until you cover the whole graph3 => 4 Proof: (by contradiction)Assume G is connected with n = e + 1, and G has a cycle containing k nodes3. G is connected and n = e + 1 4. G is acyclic and n = e + 1k …
View Full Document