Report

DISCRETE MATHEMATICS I LECTURES CHAPTER 10 Some material adapted from lecture notes provided by Dr. Chungsim Han and Dr. Sam Lomonaco Dr. Adam Anthony Spring 2011 2 Section 10.1 Introduction to Graphs 3 Definition: A simple graph G = (V, E) consists of V, a nonempty set of vertices, and E, a set of unordered pairs of distinct elements of V called edges. For each eE, e = {u, v} where u, v V. An undirected graph (not simple) may contain: Loops: An edge e is a loop if e = {u, u} for some uV Duplicate edges: A graph is called a multi-graph if there is at least one duplicate edge. Introduction to Graphs 4 Definition: A directed graph G = (V, E) consists of a set V of vertices and a set E of edges that are ordered pairs of elements in V. For each eE, e = (u, v) where u, v V. An edge e is a loop if e = (u, u) for some uV. A simple graph is just like a directed graph, but with no specified direction of its edges. Graph Models 5 Example I: How can we represent a network of (bidirectional) railways connecting a set of cities? We should use a simple graph with an edge {a, b} indicating a direct train connection between cities a and b. Boston Toronto Lübeck New York Washington Hamburg Graph Models 6 Example II: In a round-robin tournament, each team plays against each other team exactly once. How can we represent the results of the tournament (which team beats which other team)? We should use a directed graph with an edge (a, b) indicating that team a beats team b. Bruins Maple Leafs Penguins Lübeck Giants Exercise 1 7 What might the nodes/edges be if we modeled the following data? Would the graph be best undirected or directed? Acquaintance Graph: Identifying people are mutually acquainted Influence Graph: Identifying data where one person has influence over another. Computer network Road Map The World Wide Web Graph Terminology 8 Definition: Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if {u, v} is an edge in G. If e = {u, v}, the edge e is called incident with the vertices u and v. The edge e is also said to connect u and v. The vertices u and v are called endpoints of the edge {u, v}. Graph Terminology 9 Definition: The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. In other words, you can determine the degree of a vertex in a displayed graph by counting the lines that touch it. The degree of the vertex v is denoted by deg(v). Graph Terminology 10 A vertex of degree 0 is called isolated, since it is not adjacent to any vertex. Note: A vertex with a loop at it has at least degree 2 and, by definition, is not isolated, even if it is not adjacent to any other vertex. A vertex of degree 1 is called pendant. It is adjacent to exactly one other vertex. Graph Terminology 11 Example: Which vertices in the following graph are isolated, which are pendant, and what is the maximum degree? What type of graph is it? f h d a e g f b c j Solution: Vertex f is isolated, and vertices a, d and j are pendant. The maximum degree is deg(g) = 5. This graph is a non-simple undirected graph. Graph Terminology 12 Determine the number of its edges and the sum of the degrees of all its vertices: f h d a e g f b c j Result: There are 9 edges, and the sum of all degrees is 18. This is easy to explain: Each new edge increases the sum of degrees by exactly two. Graph Terminology 13 The Handshaking Theorem: Let G = (V, E) be an undirected graph with e edges. Then 2e = vV deg(v) Corrolary: The total degree of any undirected graph is always even! Example: How many edges are there in a graph with 10 vertices, each of degree 6? Solution: The sum of the degrees of the vertices is 610 = 60. According to the Handshaking Theorem, it follows that 2e = 60, so there are 30 edges. Graph Terminology 14 Theorem: An undirected graph has an even number of vertices of odd degree. Proof: Let V1 and V2 be the set of vertices of even and odd degrees, respectively (Thus V1 V2 = , and V1 V2 = V). Then by Handshaking theorem 2|E| = vV deg(v) = vV1 deg(v) + vV2 deg(v) Since both 2|E| and vV1 deg(v) are even, vV2 deg(v) must be even. Since deg(v) is odd for all vV2, |V2| must be even. QED Exercise 2 15 Draw a graph with the specified properties or show that no such graph exists: A graph with 6 vertices with the following degrees: 1,1,2,2,3,4 A graph with 4 vertices of degrees 1,2,3,4 A simple graph with 4 vertices of degrees 1,2,3,4 Exercise 3 16 A graph has 5 vertices of degrees 1,1,4,4, and 6. How many edges does the graph have? Is it possible in a group of 13 people for each to shake hands with exactly 7 others? Is it possible to have a graph with 15 edges where each vertex has degree 4? Is it possible to have a simple graph with 10 edges where each vertex has degree 4? Graph Terminology 17 Definition: When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v, and v is said to be adjacent from u. The vertex u is called the initial vertex (or source) of (u, v), and v is called the terminal vertex (or target) of (u, v). The initial vertex and terminal vertex of a loop are the same. Graph Terminology 18 Definition: In a graph with directed edges, the indegree of a vertex v, denoted by deg-(v), is the number of edges with v as their terminal vertex. The out-degree of v, denoted by deg+(v), is the number of edges with v as their initial vertex. Question: How does adding a loop to a vertex change the in-degree and out-degree of that vertex? Answer: It increases both the in-degree and the outdegree by one. Graph Terminology 19 Example: What are the in-degrees and out-degrees of the vertices a, b, c, d in this graph: deg-(a) = 1 deg-(b) = 4 a + b deg+(b) = 2 deg (a) = 2 deg-(d) = 2 deg+(d) = 1 d c deg-(c) = 0 deg+(c) = 2 Graph Terminology 20 Theorem: Let G = (V, E) be a graph with directed edges. Then: vV deg-(v) = vV deg+(v) = |E| This is easy to see, because every new edge increases both the sum of in-degrees and the sum of out-degrees by one. Exercise 4 21 What is the maximum number of edges possible in a simple graph on n vertices? What is the maximum number of edges possible in a directed graph on n vertices (loops included)? Special Graphs 22 Definition: The complete graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices. K1 K2 K3 K4 K5 Exercise 5 23 What is the degree of each vertex in the complete graph K9? What is the total degree of K9? How many edges are there in K9? How many edges are there in Kn? What is the degree of a vertex in Kn? What is the total degree of Kn? Special Graphs 24 Definition: The cycle Cn, n 3, consists of n vertices v1, v2, …, vn and edges {v1, v2}, {v2, v3}, …, {vn-1, vn}, {vn, v1}. C3 C4 C5 C6 Special Graphs 25 Definition: We obtain the wheel Wn when we add an additional vertex to the cycle Cn, for n 3, and connect this new vertex to each of the n vertices in Cn by adding new edges. W3 W4 W5 W6 Special Graphs 27 Definition: A simple graph is called bipartite if its vertex set V can be partitioned into two disjoint nonempty sets V1 and V2 such that every edge in the graph connects a vertex in V1 with a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2). For example, consider a graph that represents each person in a village by a vertex and each marriage by an edge. This graph is bipartite, because each edge connects a vertex in the subset of males with a vertex in the subset of females (if we think of traditional marriages). Special Graphs 28 Example I: Is C3 bipartite? v1 v2 v3 No, because there is no way to partition the vertices into two sets so that there are no edges with both endpoints in the same set. Example II: Is C6 bipartite? v1 v6 Yes, because v2 v5 we can display C6 like this: v3 v4 v1 v5 v3 v6 v2 v4 Special Graphs 29 Definition: The complete bipartite graph Km,n is the graph that has its vertex set partitioned into two subsets of m and n vertices, respectively. Two vertices are connected if and only if they are in different subsets. K3,2 K3,4 Exercise 6 30 Draw the complete bipartite graphs for K2,2, K2,3, and K3,4 Exercise 8 32 What is the degree of each vertex in the complete bipartite graph K4,5? Operations on Graphs 33 Definition: A subgraph of a graph G = (V, E) is a graph H = (W, F) where WV and FE. Note: Of course, H is a valid graph, so we cannot remove any endpoints of remaining edges when creating H. Example: K5 subgraph of K5 Operations on Graphs 34 Definition: The union of two simple graphs G1 = (V1, E1) and G2 = (V2, E2) is the simple graph with vertex set V1 V2 and edge set E1 E2. The union of G1 and G2 is denoted by G1 G2. G1 G2 G1 G2 = K5 Exercise 9 35 Let G be a simple graph with V = {a,b,c,d,e} and E = {{a,a},{a,b},{a,c},{b,c},{c,d}}. Is H = (VH,EH) with VH={a,b,c,d} and EH={{a,c},{b,c},{c,d}} a subgraph of G? If so, find a second subgraph L such that H L = G 36 Section 10.2 Representing Graphs, Walks, Paths and Circuits, Connectedness Representing Graphs 37 a d b d c Vertex a b c d Adjacent Vertices b, c, d a, d a, d a, b, c a b c Initial Vertex a b c d Terminal Vertices c a a, b, c Representing Graphs 38 Definition: Let G = (V, E) be a simple graph with |V| = n. Suppose that the vertices of G are listed in arbitrary order as v1, v2, …, vn. The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the nn zero-one matrix with 1 as its (i, j)th entry when vi and vj are adjacent, and 0 otherwise. In other words, for an adjacency matrix A = [aij], a =1 aij = 0 ij if {vi, vj} is an edge of G, otherwise. Representing Graphs 39 Example: What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ? a 0 1 1 1 1 0 0 1 b Solution: AG d 1 0 0 1 c 1 1 1 0 Note: Adjacency matrices of undirected graphs are always symmetric. Graph Walks 40 Definition: A walk of length n from u to v, where n is a positive integer, in an undirected graph is a sequence of edges e1, e2, …, en of the graph such that e1 = {x0, x1}, e2 = {x1, x2}, …, en = {xn-1, xn}, where x0 = u and xn = v. When the graph is simple, we denote this path by its vertex sequence x0, x1, …, xn, since it uniquely determines the path. The path or circuit is said to pass through or traverse x1, x2, …, xn-1. Paths and Circuits 41 A trivial walk from v to v consists of the single vertex v, and no edges. The path is a closed-walk if it begins and ends at the same vertex, that is, if u = v. The length of a walk is the number of edges in the walk A trail is a walk with no repeated edges A path is a walk with no repeated vertices A circuit is a closed walk with no repeated edges A path or circuit is simple if it has no repeated vertices (except the first and last in a circuit). A non-trivial simple circuit is called a cycle Exercise 1 42 1. 2. 3. 4. 5. 6. 7. 8. In the given graph, determine whether each of the following is a path, simple path, circuit, or simple circuit abcfb abcf A F E fabfcdf fabcdf abfb B C D cfbbc bb e Connectivity 43 Let us now look at something new: Definition: An undirected graph is called connected if there is a walk (or a path, or a simple path) between every pair of distinct vertices in the graph. For example, any two computers in a network can communicate if and only if the graph of this network is connected. Note: A graph consisting of only one vertex is always connected, because it does not contain any pair of distinct vertices. Exercise 2: Connected or not? 44 a b c b c b a e d c d Yes. a e No. b a e d Yes. c d f No. e Connectivity 45 A graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. A subgraph H is a connected component of a graph G if: H is connected H is not a proper subgraph of any connected subgraph of G It follows that a graph is connected G has only one connected component Exercise 3 46 Example: What are the connected components in the following graph? g h d a e b c f i j Solution: The connected components are the graphs with vertices {a, b, c, d}, {e}, {f}, {g, h, i, j}. Exercise 4 47 What is the minimum number of edges possible in a connected graph on 4 vertices? Mathematical Induction 48 Let p(n) be a statement in an integer variable n. Suppose: i. ii. p(1) is true [base step] For all integers k 2, if p(k – 1) is true (induction hypothesis) To be shown: Given i and ii above, prove that p(k) must also be true Exercise 5 49 Use induction on n to prove that a connected graph on n vertices has at least n – 1 edges. 50 Section 10.5 Trees What is a Tree? 51 A graph is called acyclic if it has no non-trivial circuits A tree is an acyclic, connected graph A trivial tree is a graph with a single vertex A forest is an acyclic, disconnected graph A tree is a special kind of simple graph Exercise 1 52 Which of the following is a tree? Tree Example—Decision Tree 53 Tree Example: Directory Structures 54 C:\ Program Files\ WINDOWS\ Documents and Settings\ apanthon\ My Documents\ Desktop\ katchins\ Tree Example: Parse Tree 55 “The young man caught the ball” Sentence Noun Phrase Verb Phrase Article Adjective noun verb Noun Phrase The young man caught the ball Every Graph Contains A Tree 56 Let G be any graph If G has no cycles, then it is a tree! If G does have cycles, for each cycle Remove The one edge from the cycle G will still be connected. Why? resulting graph G’ will be an acyclic tree Cyclical Proofs 57 How do we prove a b? Prove a b and b a a b a b means “a and b are equivalent” What if we say “a, b, and c are equivalent? a bc a b c a b c Tree Properties 58 Let T = {V,E} be a graph. The following are equivalent: a) b) c) T is connected and removing any edge from T disconnects T into two subgraphs that are trees (subtrees) There is a unique path between any two distinct vertices v and w in T T is a tree Use a cyclical proof to show this is true Proof: ab 59 Prove that if T is connected and removing any single edge results in two disconnected subgraphs, both of which are trees, then there is a unique path between any two vertices u and v Proof by contraposition: Prove that if there exists at least one alternative path between u and v, then either T is not connected or removing any edge will not result in two disconnected subgraphs. Proof ab (continued) 60 Suppose T is any graph, such that there are two distinct paths between some vertices u and v. If there are two distinct paths, then there must be a cycle in the graph, found by following the first path from u to v, then reversing the second path to get back from v to u. We have already observed that removing an edge in a cycle will not disconnect a graph. Therefore, there is at least one edge which can be removed from this graph that will not disconnect T, which is what was to be shown. Proof bc 61 Prove that if there exists a unique path between all pairs of vertices in T, then T must be a tree. Proof by contraposition that if T is not a tree, then there is not a unique path between all pairs of vertices in T There T are two cases: is not connected T has a cycle Proof of bc (continued) 62 Case 1: T is not connected Then there must not be a path between at least two vertices u and v, which is what was to be shown. Case 2: T has a cycle Pick any edge {u,v} on the cycle. This represents a path from u to v. Now follow a path the ‘long way around’ the cycle, starting at v and ending at u. This path is distinct from the first, which is what was to be shown. Proof of ca 63 Prove that if T is a tree, then T is connected and removing any edge results in two disconnected subgraphs that are themselves trees. Suppose T is a graph that is a tree Then T is, by definition, connected and has no cycles Remove any one edge {u,v} from T. Since T has no cycles, then this edge represents a unique path from u to v because if there were another path, then {u,v} would complete a cycle Therefore, removing {u,v} disconnects the graph into two distinct components. The two subgraphs have no cycles, and since only one edge was removed, they are connected. Thus they are trees. More tree properties! 66 A tree T with n vertices has n-1 edges. Proof (by induction): A tree with n = 1 vertex has n – 1 = 0 edges. For a graph with n 2 vertices, suppose that any graph with n – 1 or fewer vertices has one less edge than it does vertices. Take a tree with n vertices and remove a single edge from the tree. This results in two smaller subtrees T1 = (V1,E1) and T2 = (V2 E2). n = |V| = |V1| + |V2| |E| = |E1| + |E2| + 1 By the induction hypothesis, |E1| = |V1| - 1 and |E2| = |V2| - 1 Then |E| = (|V1| - 1) + (|V2| - 1) + 1 = |V1| + |V2| - 1 = |V| - 1, which is what was to be shown Exercise 2 67 Prove by contradiction that a finite tree with more than 1 vertex has at least 1 vertex of degree 1 Exercise 3 68 Is a graph with 12 vertices and 12 edges a tree? Is any graph with 5 vertices and 4 edges a tree? Is any connected graph with 5 vertices and 4 edges a tree? Exercise 4 69 Let T be a graph on n vertices. Prove that the following are all equivalent: a) b) c) T is a tree T is connected and has n – 1 edges T is acyclic and has n – 1 edges 70 Section 10.6 Rooted Trees and Tree Traversals What is a rooted tree? 71 Parent Root(level = 0) Child Internal Vertex (level = 1) Leaf(level = 2) Tree Definitions 72 The root is any vertex in a tree that is selected to be the root Level(v) = #edges it takes to reach v from the root height(T) = the maximum level of any vertices in T Children(v) all vertices adjacent to v whose level is Level(v) + 1 Parent(v) The unique vertex that is adjacent to v whose level is Level(v) – 1 A leaf is a node with no children. An ancestor v is any vertex w that lies on the path from the root to v. v would be considered a descendant of all such vertices. Exercise 1 73 Find the: a) Level of e b) Height of the tree c) Children of t d) Parent of t e) Ancestors of g f) Descendants of t a g) Leaves of the tree r t s v w c b f g x u y z e d h i Exercise 2 74 Design a tree to represent the table of contents of a book: C1 S1.1 S1.2 S1.3 C2 S2.1 S2.2 S2.2.1 S2.2.2 C3 S3.1 S3.2 Binary Trees 75 A Binary Tree is a rooted tree in which each internal vertex has at most two children Since there are only two, they get special names: Subtrees get special names too! Left child Right child If there is only one, call it the left child The left subtree of a vertex v is the subtree rooted at the left child of v The right subtree of a vertex v is the subtree rooted at the right child of v A full (or complete) binary tree is a binary tree in which each internal vertex has exactly two children Exercise 3 76 Use a complete binary tree to represent the following mathematical expressions: a +b (a + b) ((c * d) – e) M-ary Trees 77 An m-ary tree is a rooted tree in which each internal vertex has at most m children A full m-ary tree is an m-ary tree in which each internal vertex has exactly m children m = 2 (binary tree), m = 3 (ternary tree) Theorem 1 78 Let T be a full m-ary tree with n vertices, i internal vertices, and L leaves. Then each of the following is true: a) n m i 1 b) L i (m 1) 1 L 1 n 1 c) i m 1 m Corollary to Theorem 1 79 Let T be a full binary tree with n vertices, i internal vertices, and L leaves. Then each of the following is true: a) n 2i 1 n 1 b) L i 1 2 n 1 c) i L 1 2 Exercise 4 80 How many vertices does a full ternary tree with 11 leaves have? Is there a full binary tree with 12 vertices? How many edges does a full 5-ary tree with 100 internal vertices have? Is there a full binary tree that has 10 internal vertices and 13 leaves? Exercise 5 81 The Wimbledon tennis championship is a singleelimination tournament in which a player is eliminated after a single loss. If 31 women compete in the championship, how many matches must be played to determine the champion? Exercise 6 82 Suppose someone starts a chain letter. Each person who receives the letter is asked to send it to 5 other people. If everyone who receives the letter follows the instructions, how many people can be reached in a tree of height 2? If 125 people received the letter, but did not send it, determine the following: How many people sent the letter? How many people in total have seen the letter, including the person who started it? Exercise 7 83 A computer lab has a single wall socket with 6 outlets in it. Using power strips with 6 connections each, how many extension cords do we need to power 46 all-in-one computers? Balanced Trees 84 An m-ary tree of height h is balanced if every leaf is at level h or h – 1. Which of the following trees are balanced? 85 Number of Vertices in a Binary Tree Based on Height If we have binary a tree of height h, what is the maximum number of vertices n we can have in that tree? Hint: it’s when every internal vertex has as many children as possible! Given the solution to the above, how many leaves are in the tree, given the height? 86 Minimum Binary Tree Height Based on Number of Vertices If a binary tree has n vertices, what is the maximum height? More interesting, what is the minimum height? n < 21, h 0 21 n < 22, h 1 22 n < 23, h 2 23 n < 24, h 3 2k n < 2k+1, h k (Now let’s solve this for k!) h log(n) 20 M-Ary Tree Version 87 In an m-ary tree of height h, what is the maximum number of vertices n? #V at Level 0: m0, #V at Level 1: m1, #V at Level 2: m2, #V at Level 3: m3, #V at Level k: mk, n1 n m + 1 = (m2 – 1)/(m – 1) n m2 + m + 1 = (m3 – 1)/(m – 1) n m3 + m2 + m + 1 = (m4 – 1)/(m – 1) n mk + … + m2 + m + 1 = (mk – 1)/(m – 1) Back to the chain-letter example, now how many vertices would there be if the letter was sent by everybody for 10 levels? Theorem 88 Prove by induction that if T is an m-ary tree of height h, then the number of leaves l mh Then prove the corrolary that if T is an m-ary tree with l leaves, then logm l h Exercise 8 89 A full binary tree has 500 leaves What is the minimum height of the tree? Is there a ternary tree of height 4 with 100 leaves? 90 Binary Tree Traversals YES THIS MATERIAL WILL BE ON THE EXAM!!! Tree Traversals 91 In mathematics, we’re always studying tree properties, and they are useful In computing, we’re not just studying trees, we are storing and processing trees A tree traversal is a method for efficiently retrieving information from a tree There are three different traversals that have different applications: Pre-order In-order Post-order Preorder Traversal of a Binary Tree 92 Let T be a rooted binary tree with root R, and left subtree TL and right subtree TR. The Preorder traversal of T is as follows: ‘Visit’ R (print value, perform computation, etc.) Perform a preorder traversal on TL Perform a preorder traversal on TR A B ABC C About Recursion 93 Recursion is weird…but really cool! The pre-order procedure is very easy to define because it uses itself as part of the definition! ‘Visit’ R (print value, perform computation, etc.) Perform a preorder traversal on TL Perform a preorder traversal on TR If we follow this precisely, then it will gradually take us throughout the entire tree! Exercise 1 94 Find the pre-order traversal of the following tree (ROOT-L-R): Your Turn! Finish the traversal by performing a preorder traversal of the right subtree. r a b c f j n Result: d g e h k o i l p m q s Post-Order and In-Order Traversals 95 As before, let T be a rooted binary tree with root R, and left subtree TL and right subtree TR. The post-order traversal of T is: Perform a post-order traversal of TL Perform a post-order traversal of TR ‘Visit’ R A BCA B C The in-order traversal of T is: Perform ‘Visit’ a post-order traversal of TL R B Perform a post-order traversal of TR A BAC C Exercise 2 96 Find the Post-Order (L-R-Root) traversal: r a b c f j n d g e h k o i l p m q s Exercise 3 97 Find the in-order (L-Root-R) traversal: r a b c f j n d g e h k o i l p m q s Arithmetic Trees, Revisited 98 Consider the tree for ((a + b) * (c – d)): * + a b c d Perform an in-order (L-Root-R) traversal of the tree How can we get the parentheses back? Arithmetic Trees, Revisited 99 Consider the tree for ((a + b) * (c – d)): * + a b c d Perform a pre-order traversal Such an expression is called the prefix form of an arithmetic computation Arithmetic Trees, Revisited 100 Consider the tree for ((a + b) * (c – d)): * + a b c d Perform a post-order traversal Such an expression is called the postfix form of an arithmetic computation Why pre-fix, post-fix matter 101 You don’t need parentheses!!! Consider the prefix notation: * +ab–cd Scan rightleft. When you reach an operator, apply it to the two values to the right Then Try * replace the three items with the single answer it! + - 4 6 8 16 4 Computing Post-fix Expressions 102 Similarly, compute post-fix expressions from leftright: You’ll always have two values, then an operand Apply the operand to the values, then replace all three with the answer you get. Try again! 4 6 – 8 + 16 4 * Exercise 4 103 Try some more! Pre-fix: +432^8* Post-fix: 3 5 * 2 + 4 2 ^ 8 – How about logic (works similarly)? Let a = TRUE, b = FALSE Prefix: a b a b Postfix: a b a ~ b Thought exercise: postfix is easier for humans, but prefix is easier for computers. Why?