DISCRETE MATHMATC II
DISCRETE MATHMATC II MAD 3105
Popular in Course
Popular in Mathematics Discrete
This 152 page Class Notes was uploaded by Duncan Hills on Thursday September 17, 2015. The Class Notes belongs to MAD 3105 at Florida State University taught by Staff in Fall. Since its upload, it has received 136 views. For similar materials see /class/205562/mad-3105-florida-state-university in Mathematics Discrete at Florida State University.
Reviews for DISCRETE MATHMATC II
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
Florida State University Course Notes MAD 3105 Discrete Mathematics II Florida State University Tallahassee7 Florida 32306 4510 Copyright 2004 Florida State ULniversity Written by Dr John Bryant and Dr Penelope Kirby All rights reserved No part of this publication may be reproduced7 stored in a retrieval systern7 or transmitted in any form or by any means without permission from the authors or a license from Florida State University Contents Chapter 1 Relations 1 Relations and Their Properties 11 De nition of a Relation 12 Directed Graphs 13 Representing Relations with Matrices 14 Example 141 15 lnverse Relation 16 Special Properties of Binary Relations 17 Examples of Relations and their Properties 18 Theorem 181 Connection Matrices vs Properties 19 Combining Relations 110 Example 1101 111 De nition of Composition 112 Example 1121 113 Theorem 1131 Characterization of Transitive Relations 114 Connection Matrices vs Composition 2 Closure of Relations 21 De nition of the Closure of Relations 22 Re exive Closure 23 Symmetric Closure 24 Examples 25 Relation Identities 26 Characterization of Symmetric Relations 27 Paths 28 Paths vs Composition 29 Characterization of a Transitive Relation 210 Connectivity Relation 211 Characterization of the Transitive Closure 212 Example 213 Cycles 214 Corollaries to Theorem 2131 215 Example 10 216 Properties vs Closure 3 Equivalence Relations 31 De nition of an Equivalence Relations 32 Example 310 413 414 415 416 417 418 419 CONTENTS Equivalence Classes Partition Intersection of Equivalence Relations Example Example lsomorphism is an Equivalence Relation Equivalence Relation Generated by a Relation R Using Closures to nd an Equivalence Relation Partial Orderings De nition of a Partial Order Examples Pseudo Orderings Well Ordered Relation Examples Lexicographic Order Examples 471 and 472 Strings Hasse or Poset Diagrams Example 4101 Maximal and Minimal Elements Least and Greatest Elements Upper and Lower Bounds Least Upper and Greatest Lower Bounds Lattices Example 4161 Topological Sorting Topological Sorting Algorithm Existence of a Minimal Element Chapter 2 Graphs 1 11 12 13 14 15 16 17 18 19 110 111 112 2 Introduction to Graphs and Graph lsomorphism The Graph Menagerie Representing Graphs and Graph lsomorphism lncidence Matrices Example 141 Degree The Handshaking Theorem Example 171 Theorem 181 Handshaking Theorem for Directed Graphs Graph lnvariants Example 1111 Proof of Section 110 Part 3 for simple graphs Connectivity CONTENTS 21 Connectivity 22 Example 221 23 Connectedness 24 Examples 25 Theorem 251 26 Example 261 27 Connected Component 28 Example 281 29 Cut Vertex and Edge 210 Examples 211 Counting Edges 212 Connectedness in Directed Graphs 213 Paths and lsomorphism 214 Example 2141 215 Theorem 2151 3 Euler and Hamilton Paths 31 Euler and Hamilton Paths 32 Examples 33 Necessary and Suf cient Conditions for an Euler Circuit 34 Necessary and Suf cient Conditions for an Euler Path 35 Hamilton Circuits 36 Examples 37 Suf cient Condition for a Hamilton Circuit 4 Introduction to Trees 41 De nition of a Tree 42 Examples 43 Roots 44 Example 441 45 lsomorphism of Directed Graphs 46 lsomorphism of Rooted Trees 47 Terminology for Rooted Trees 48 m ary Tree 49 Counting the Elements in a Tree 410 Level 411 Number of Leaves 412 Characterizations of a Tree 5 Spanning Trees 51 Spanning Trees 52 Example 521 53 Example 531 54 Existence 55 Spanning Forest 56 Distance 6 Search and Decision Trees CONTENTS Binary Tree Example 621 Decision Tree Example 641 Tree Traversal Ordered Trees Universal Address System Tree Traversal Preorder Traversal lnorder Traversal Postorder Traversal ln x Form Chapter 3 Boolean Algebra 1 11 12 13 14 15 16 2 312 313 314 4 Boolean Functions Boolean Functions Example 121 Binary Operations Example 141 Boolean ldentities Dual Representing Boolean Functions Representing Boolean Functions Example 221 Example 231 Functionally Complete Example 251 NAND and NOR Abstract Boolean Algebras Abstract Boolean Algebra Examples of Boolean Algebras Duality More Properties of a Boolean Algebra Proof of ldempotent Laws Proof of Dominance Laws Proof of Theorem 341 Property 4 Proof of DeMorgan7s Law lsomorphism Atoms Theorem 3111 Theorem 3121 Basis Theorem 3141 Logic G ates 101 102 103 103 106 106 106 107 107 109 110 111 115 115 115 115 116 117 117 118 119 119 119 120 121 121 122 123 123 123 126 126 127 127 128 129 130 131 133 133 134 135 139 CONTENTS Logic Gates Example 421 NOR and NAND gates Example 441 Half Adder Full Adder Minimizing Circuits Minimizing Circuits Example 521 Karnaugh Maps Two Variables Three Variables Four Variables Quine MCCluskey Method 139 139 141 142 143 143 146 146 146 146 146 148 149 151 CHAPTER 1 Relations 1 Relations and Their Properties 11 De nition of a Relation DEFINITION 111 A binary relation from a set A to a set E is a subset R Q A gtlt B If Lab 6 R we say a is Related to b by R A is the domain of R and B is the codomain of R IfA B R is called a binary relation on the set A Notation o If 17 b E R7 then we write 11 o If a7b Z R7 then we write a b Discussion We recall the basic de nitions and terminology associated with the concept of a relation from a set A to a set B You should review the notes from MAD 2104 whenever you wish to see more examples or more discussion on any of the topics we review here A relation is a generalization of the concept of a function7 so that much of the terminology will be the same Speci cally7 if f A a B is a function from a set A to a B7 then the graph of f7 graphf Q7 6 A is a relation from A to B Recall7 however7 that a relation may differ from a function in two essential ways If R is an arbitrary relation from A to B7 then 0 it is possible to have both Lab 6 R and a7b E R7 where b 31 b that is7 an element a in A may be related to any number of elements of B or 8 1 RELATIONS AND THEIR PROPERTIES 9 o it is possible to have some element a in A that is not related to any element in B at all EXAMPLE 111 Suppose R C Z gtlt Z4r is the relation de ned by ab E R if and only if alb Recall that Z4r denotes the set of positive integers and alb read quota divides b means that b no for some integer Then R fails to be a function on both counts listed above Certainly 72l2 and 72 4 so that 72 is related to more than one positive integer In fact it is related to in nitely many integers On the other hand OXb for any positive integer b REMARK 111 It is often desirable in computer science to relacc the requirement that a function be de ned at every element in the domain This has the bene cial e ect of reducing the number of sets that must be named and stored In order not to cause too much confusion with the usual mathematical de nition of a function a relation such as this is called a partial function That is a partial function f A a B is a relation such that for all a E A fa is a uniquely determined element ofB whenever it is de ned For epample the formula fp 171M de nes a partial function f R a R with domain R and codomain R f is not de ned at z 71 and p 1 but otherwise fp is uniquely determined by the formula EXERCISE 111 Let n be a positive integer How many binary relations are there on a set A if lAl n Hintx How many elements are there in lA gtlt Al 12 Directed Graphs DEFINITIONS 121 o A directed graph or a digraph D from A to B is a collection of vertices V Q A U B and a collection ofedges R Q A gtlt B o If there is an ordered pair e zy in R then there is an arc or edge from x to y in D o The elements z and y are called the initial and terminal vertices of the edge e Ly respectively Discussion A digraph can be a useful device for representing a relation especially if the relation isn7t too large77 or complicated If R is a relation on a set A we simplify the digraph G representing R by having only one vertex for each a E A This results however in the possibility of having loops that is edges from a vertex to itself and having more than one edge joining distinct vertices but with opposite orientations A digraph for the relation R in Example 111 would be dif cult to illustrate and impossible to draw completely since it would require in nitely many vertices and edges We could draw a digraph for some nite subset of R 1 RELATIONS AND THEIR PROPERTIES 10 EXAMPLE 121 Suppose R is the relation on 0172374576 de ned by mRn if and only ifm E nmod 3 The digraph that represents R is 13 Representing Relations With Matrices DEFINITION 131 LetR be a relation from A a1a2am to B b17b2 bn An in gtlt n connection matrix MR for R is de ned by H i l ahbj E R m 7 0 otherwise 14 Example 141 EXAMPLE 141 Let A abe7 B efgh7 and R a7 e7 eg then the connection matrico 1 0 0 0 MR 0 0 0 0 0 0 1 0 Discussion Recall the connection matrix for a nite relation is a method for representing a relation using a matrix REMARK 141 The ordering of the elements in A and B is important If the elements are rearranged the matrico would be di erent If there is a natural order to the elements of the sets like numerical or alphabetical you would ELEPCCt to use this order when creating eonneetion matriees To nd this matrix we may use a table as follows First we set up a table labeling the rows and columns with the vertices efgh 16 1 RELATIONS AND THEIR PROPERTIES 11 Since a e E R we put a 1 in the row a and column e and since 0 g E R we put a 1 in row 0 and column 9 efgh a1 b c 1 Fill in the rest of the entries with Us The matrix may then be read straight from the table 15 Inverse Relation DEFINITION 151 Let R be a relation from A to B Then R l balab E R is a relation from B to A R 1 is called the inverse of the relation R Discussion The inverse of a relation R is the relation obtained by simply reversing the ordered pairs of R The inverse of a relation is also called the converse of a relation EXAMPLE 151 LetA abc andB 1 234 andletR a 1 a2 04 Then R 1lt1agtlt2agtlt4agt EXERCISE 151 Suppose A and B are sets and f A a B is a function The graph of f graphf E A is a relation from A to B a What is the inverse of this relation b Does f have to be invertible as a function for the inverse of this relation to exist 0 If f is invertible nd the inverse of the relation graphf in terms of the inverse function f l 16 Special Properties of Binary Relations De nitions Let A be a set and let R be a binary relation on A 1 R is re exive if Vxz E A a E 2 R is irre exive if we 6 A a ltltmgt 1 3 R is symmetric if vmwm e R a W e 1 1 RELATIONS AND THEIR PROPERTIES 12 4 R is antisymmetric if VWilW 6 PM we 6 R v 96 ml 5 R is asymmetric if VWilW E R v 11795 RN 6 R is transitive if VszVzxy 6 RA y72 E R a E Discussion The de nition above recalls six special properties that a relation may or may not satisfy Notice that the de nitions of re exive and irre exive relations are not complementary That is7 a relation on a set may be both re exive and irre exive or it may be neither The same is true for the symmetric and antisymmetric properties7 as well as the symmetric and asymmetric properties The terms re exive7 symmetric7 and transitive is generally consistent from author to author The rest are not as consistent in the literature EXERCISE 161 Before reading further nd a relation on the set a7b7c that is neither a refleccive nor irrefleccive b symmetric nor antisymmetric c symmetric nor asymmetric 17 Examples of Relations and their Properties EXAMPLE 171 Suppose A is the set of all residents of Florida and R is the relation given by aRb ifa and b have the same last four digits of their Social Security Number This relation is refleccive not irreflepive symmetric not antisymmetric not asymmetric transitive EXAMPLE 172 Suppose T is the relation on the set of integers given by pTy if 2x 7 y 1 This relation is 0 not refleccive 0 not irreflepive 1 RELATIONS AND THEIR PROPERTIES not symmetric antisymmetric not asymmetric not transitive EXAMPLE 173 Suppose A abcd and R is the relation aa This relation is not reflecciye not irreflepiye symmetric antisymmetric not asymmetric transitive Discussion When proving a relation R on a set A has a particular property the property must be shown to hold for all appropriate combinations of members of the set When proving a relation B does not have a property however it is enough to give a coun terexample EXAMPLE 174 Suppose T is the relation in Encample 172 in Section 17 This relation is not reflecciye PROOF 2 is an integer and 2 2 7 2 2 31 1 This shows that Vph E Z 7 Lz E T is not true D not irreflepiye PROOF 1 is an integer and 2 1 71 1 This shows that Vph E Z 7 zx Z T is not true D not symmetric PROOF Both 2 and 3 are integers 22 7 3 1 and 23 7 2 4 31 1 This shows 2R3 but 332 that is VpVyKLy E Z 7 yz E T is not true D antisymmetric PROOF Let 77171 6 Z be such that 77171 6 T and nm E T By the de nition of T this implies both equations 2m 7 n 1 and 2n 7 m 1 must hold We may use the rst equation to solve for n n 2m 7 1 and substitute this in for n in the second equation to get 22m 7 1 7 m 1 We 1 RELATIONS AND THEIR PROPERTIES 14 may use this equation to solve for m and we nd in 1 Now solve for n and we get n 1 This shows that the only integers in and n such that both equations 2min 1 and 2n 7m 1 hold are m n 1 This shows that VmVnmn E T nm E T a m 0 not asymmetric PROOF 1 is an integer such that 11 6 T Thus Vszxy E T a ba Z T is not true counterexample is a b 1 D 0 not transitive PROOF 2 3 and 5 are integers such that 23 6 T 35 6 T but 25 Z T This shows VxVszKLy E T yz E T oz 6 T is not true D EXERCISE 171 Verify the assertions made about the relation in Example 171 in Section 17 EXERCISE 172 Verify the assertions made about the relation in Example 173 in Section 17 EXERCISE 173 Suppose R C Z4r gtlt Z4r is the relation de ned by 77171 6 R if and only ifmln Prove that R is a reflepive b not irrefleccive c not symmetric d antisymmetric e not asymmetric f transitive 18 Theorem 181 Connection Matrices Vs Properties THEOREM 181 Let R be a binary relation on a set A and let MR be its connection matrip Then 0 R is refleccive i mi 1 for all i o R is irreflepive i mi 0 for alli o R is symmetric i M is a symmetric matrip o R is antisymmetric i for each i 31 j 7m 0 or m 0 o R is asymmetric i for everyi andj ifmlj 1 then m 0 Discussion Connection matrices may be used to test if a nite relation has certain properties and may be used to determine the composition of two nite relations 1 RELATIONS AND THEIR PROPERTIES 15 EXAMPLE 181 Determine which of the properties reflepiye irreflemiye symmet ric antisymmetric asymmetric the relation on a bc d represented by the following matricc has I OHO HOOD OOOH HOO Solution The relation is irreflecciye asymmstric and antisymmetric only EXERCISE 181 Determine which of the properties reflepiye irreflemiye symmet ric antisymmetric asymmetric the relation on a bc d represented by the following matricc has 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 19 Combining Relations Suppose property P is one of the properties listed in Section 16 and suppose R and S are relations on a set A each having property P Then the following questions naturally arise 1 Does R necessarily have property P 2 Does RU S have property P 3 Does R S have property P 4 Does R 7 S have property P Discussion Notice that when we combine two relations using one of the binary set operations we are combining sets of ordered pairs 110 Example 1101 EXAMPLE 1101 Let R and S be transitive relations on a set A Does it follow that R U S is transitive Solution No Here is a counterexample 1 RELATIONS AND THEIR PROPERTIES 16 A 17 2 R 1727 S 271 Therefore7 RUS 1221 Notice that R and S are both transitive vacuously7 since there are no two elements satisfying the hypothesis of the conditions of the property However R U S is not transitive If it were it would have to have 11 and 22 in RU S Discussion The solution to Example 1101 gives a counterexample to show that the union of two transitive relations is not necessarily transitive Note that you could nd an example of two transitive relations whose union is transitive The question7 however7 asks if the given property holds for two relations must it hold for the binary operation of the two relations This is a general question and to give the answer yes we must know it is true for every possible pair of relations satisfying the property Here is another example EXAMPLE 1102 Suppose R and S are transitive relations on the set A Is R S transitive Solution Yes PROOF Assume R and S are both transitive and suppose ab7 he 6 R S Then abbc E R and abbc E S It is given that both R and S are transitive7 so a70 E R and ac E S Therefore a70 E R S This shows that for arbitrary ab7 he 6 R S we have a70 E R S Thus R S is transitive D As it turns out7 the intersection of any two relations satisfying one ofthe properties in Section 16 also has that property As the following exercise shows7 sometimes even more can be proved EXERCISE 1101 Suppose R and S are relations on a set A a Prove that ifR and S are reflepive then so is R S b Prove that ifR is irreflecoive then so is R S EXERCISE 1102 Suppose R and S are relations on a set A 1 RELATIONS AND THEIR PROPERTIES 17 a Prove that ifR and S are symmetric then so is Pi S b Prove that ifR is antisymmetric then so is R S c Prove that ifR is asymmetric then so is R S EXERCISE 1103 Suppose R and S are relations on a set A Prove or disprove a IfR and S are reflepive then so is RU S b IfR and S are irreflepive then so is R U S EXERCISE 1104 Suppose R and S are relations on a set A Prove or disprove a IfR and S are symmetric then so is RU S b IfR and S are antisymmetric then so is R U S c IfR and S are asymmetric then so is R U S 111 De nition of Composition DEFINITION 1111 I Let 0 R be a relation from A to B and o S be a relation from B to 0 Then the composition ofR with S denoted S o R is the relation from A to 0 de ned by the following property 2 E S o R if and only if there is a y E B such that zy E R and 272 E S 2 Let R be a binary relation on A Then Pi is de ned recursively as follows Basis R1 R Recurrence Pi 1 R o R ifn 2 1 Discussion The composition of two relations can be thought of as a generalization of the composition of two functions as the following exercise shows EXERCISE 1111 Prove If f A a B and g B a C are functions then grapho 0 f amp19 0 ampW EXERCISE 1112 Prove the composition of relations is an associative operation EXERCISE 1113 Suppose R is a relation on A Using the previous eccercise and mathematical induction prove that R o R R o R EXERCISE 1114 Prove an ordered pair zy E R if and only if in the digraph D of B there is a directed path of length n from x to y Notice that if there is no element of B such that ab E R1 and b c E R2 for some a E A and c E C then the composition is empty 1 RELATIONS AND THEIR PROPERTIES 18 112 Example 1121 EXAMPLE 1121 Let A ab c B 1234 and o IIIIIIIV o IfRa4b 1 and o S 1II 11V2I then SoRbIIbIV Discussion It can help to consider the following type of diagram when discussing composition of relations such as the ones in Example 1121 shown here a 1 I 2 II b 3 III c 4 IV EXAMPLE 1122 IfR and S are transitive binary relations on A is R0 S tran sitive Solution No Here is a countereccarnple Let R 12 34 and S 23 4 Both R and S are transitive vacuously but R0 S 24 4 2 is not transitive EXAMPLE 1123 Suppose R is the relation on Z4r de ned by aRb if and only if alb Then R2 R EXERCISE 1121 Suppose R is the relation on the set of real numbers given by pRy if and only if 2 a Describe the relation R2 b Describe the relation R n 2 1 EXERCISE 1122 Suppose R and S are relations on a set A that are reflepive Prove or disprove the relation obtained by combining R and S in one of the following ways is reflepive Recall R 69 S RU S 7 RF 1 RELATIONS AND THEIR PROPERTIES 19 a REDS bRiS c RoS d R 1 e R n 2 2 EXERCISE 1123 Suppose R and S are relations on a set A that are symmetric Prove or disprove the relation obtained by combining R and S in one of the following ways is symmetric a R B S b R 7 S c R o S d 3 1 e R n 2 2 EXERCISE 1124 Suppose R and S are relations on a set A that are transitive Prove or disprove the relation obtained by combining R and S in one of the following ways is transitive a REDS bRiS e R n22 113 Theorem 1131 Characterization of Transitive Relations THEOREM 1131 Let R be a binary relation on a set A R is transitive if and only ifR Q R forn 21 PROOF To prove R transitive a Rn Q R we assume R is transitive and prove R Q R for n 2 1 by induction Basis Step n 1 R1 R7 so the statement is vacuously true when n 17 since R1 R Q R whether or not B is transitive Induction Step Prove R Q R a R 1 Q R Assume R Q R for some n 2 1 Suppose Ly E Rn By de nition7 R 1 R 0 R7 so there must be some a E A such that La 6 R and ay E B By the induction hypothesis7 R Q R7 so ay E R Since R is transitive ca7 a7y E R implies Ly E R Since Ly was an arbitrary element of Rn we have shown Rn Q R 1 RELATIONS AND THEIR PROPERTIES 20 We now prove the reverse implication R Q R for n 2 1 implies R is transitive We prove this directly using only the hypothesis for n 2 Assume Ly y z E R The de nition of composition implies zz E R2 But R2 Q B so 2 E R Thus R is transitive D Discussion Theorem 1131 gives an important characterization of the transitivity property Notice that since the statement of the theorem was a property that was to be proven for all positive integers induction was a natural choice for the method of proof EXERCISE 1131 Prove that a relation R on a set A is transitive if and only if R2 Q R Hintx Eparnine not only the statement but the proof of the Theorem 1131 114 Connection Matrices Vs Composition Recall The boolean prod uct of an m gtlt h matrix A ahl and a h gtlt n matrix B blj denoted AQB clj is de ned by CH an A blj V am A bgj V 39 39 39 V 1 A THEOREM 1141 Let X Y and Z be nite sets Let R1 be a relation from X to Y and R2 be a relation from Y to Z If M1 is the connection matrip for R1 and M2 is the connection matricc for R2 then M1 6 M2 is the connection matricc for R2 0 R1 We write IWRWR1 MR1 QMRT COROLLARY 11411 MR MRYL the boolean nth power of MR EXERCISE 1141 Let the relation R on abcd be represented by the matricc 1 1 1 0 1 0 0 0 1 0 0 1 39 l0 0 1 OJ Find the matrip that represents R3 2 CLOSURE OF RELATIONS 21 2 Closure of Relations 21 De nition of the Closure of Relations DEFINITION 211 Given a relation R on a set A and a property P of relations the closure ofR with respect to property P denoted ClpR is smallest relation on A that contains R and has property P That is ClpR is the relation obtained by adding the minimum number of ordered pairs to R necessary to obtain property P Discussion To say that ClpR is the smallest77 relation on A containing R and having property P means that R g OlpR o ClpR has property P and o if S is another relation with property P and R Q S then ClpR Q S The following theorem gives an equivalent way to de ne the closure of a relation THEOREM 211 IfR is a relation on a set A then ClpR m S where Se P S R Q S and S has property P EXERCISE 211 Prove Theorem 21 Recall that one way to show two sets A and B are equal is to show A Q B and B Q A 2 2 Re exive Closure DEFINITION 221 Let A be a set and let A E A A is called the diagonal relation on A THEOREM 221 Let R be a relation on A The re exive closure of R denoted rR is the relation R U A PROOF Clearly R U A is re exive since aa E A Q RU A for every a E A On the other hand if S is a re exive relation containing R then aa E S for every a E A Thus A Q S and so RUA Q S Thus by de nition R U A Q S is the re exive closure of R 2 CLOSURE OF RELATIONS 22 Discussion Theorem 221 in Section 22 gives a simple method for nding the re exive closure of a relation R REMARKS 221 1 Sometimes A is called the identity or equality relation on A 2 A is the smallest refleccive relation on A 3 Given the digraph of a relation to nd the digraph of its refleccive closure add a loop at each vertep for which no loop already epists 4 Given the connection matricc M of a nite relation the matrip of its refleccive closure is obtained by changing all zeroes to ones on the main diagonal of M That is form the Boolean sum M V I where I is the identity matricc of the appropriate dimension 23 Symmetric Closure THEOREM 231 The symmetric closure of R denoted 5R is the relation RU R l where R 1 is the inverse of the relation R Discussion REMARKS 231 I To get the digraph of the inverse of a relation R from the digraph of R reverse the direction of each of the arcs in the digraph of R 2 To get the digraph of the symmetric closure of a relation R add a new arc if none already eccists for each directed arc in the digraph for R but with the reverse direction 3 To get the connection matricc of the inverse of a relation R from the connec tion matrip M of R take the transpose Mt 4 To get the connection matrip of the symmetric closure of a relation R from the connection matricc M of R take the Boolean sum M V Mt 5 The composition of a relation and its inverse is not necessarily equal to the identity A bijective function composed with its inverse however is equal to the identity 24 Examples EXAMPLE 241 IfA Z and R is the relation my 6 R i x 31 y then MR Z gtlt Z 0 8R R EXAMPLE 242 IfA ZJV and R is the relation my 6 R i z lt y then 2 CLOSURE OF RELATIONS 23 o rR is the relation my 6 rR i x S y o 5R is the relation my 6 5R i z 74 y EXAMPLE 243 Let R be represented by the digraph a b o The digraph of rR is o The digraph of 5R is Discussion In Section 24 we give several re exive and symmetric closures of relations Here is another example using the connection matrix of a relation EXAMPLE 244 Suppose R is a relation with eonneetion matrico 1 0 1 M 1 0 0 0 1 0 2 CLOSURE OF RELATIONS 24 o The connection matrip of the reflecciue closure is 1 0 1 M 1 1 0 0 1 1 o The connection matrip for the symmetric closure is 1 1 1 MS 1 0 1 1 1 0 25 Relation Identities THEOREM 251 Suppose R and S are relations from A to B Then 3 R S1 R l 8 1 4 AXB 1BgtltA 501 0 6 E 1Prl R srl R l 5 1 7 s IfA B then R0 S 1 8 1 0 PH 9 UR g S then R 1 g 5 1 Discussion The properties given in Theorem 251 may be useful when trying to nd the inverse of a relation EXAMPLE 251 Suppose R is the relation on the real numbers de ned by pRy iff xy 1 orxiy 1 R is the union of the two relations R1 and R2 de ned by ley iffxy 1 and ngy iffz 7y 1 Since Rfl is de ned by foly iffy 1 and Pig1 is de ned by foy iffy in 1 we apply the property R1 URZ 1 Rfl UR1L to see xR ly is de ned by y z 1 ory 7 z 1 EXERCISE 251 Describe the symmetric closure of the relation R in Encample 251 PROOF THAT R U S 1 Pr1 U 54 my 6 RU S 1 gt y7 a E R U S7 by the de nition of the inverse relation7 gt yz E R or ya 6 S7 by the de nition of union7 2 CLOSURE OF RELATIONS 25 gt my E R 1 or my 6 5 1 by the de nition of inverse relations7 gt my 6 Pfl U S l by the de nition of union EXERCISE 252 Prove Property 1 in Theorem 25 EXERCISE 253 Prove Property 3 in Theorem 25 EXERCISE 254 Prove Property 4 in Theorem 25 EXERCISE 255 Prove Property 5 in Theorem 25 PROOF OF PROPERTY 6 IN THEOREM 251 Let a e A and b e B Then a R by the de nition of the inverse of a relation by the de nition of the complement by the de nition of the inverse of a relation R 1 by the de nition of the complement b 19MB R 1 6 fiftitit eeso Q a 7 EXERCISE 256 Prove Property 7 in Theorem 25 EXERCISE 257 Prove Property 8 in Theorem 25 EXERCISE 258 Prove Property 9 in Theorem 25 26 Characterization of Symmetric Relations THEOREM 261 Let R be a relation on a set A TherzR is symmetric z R R l PROOF First we show that if R is symmetric7 then R R l Assume R is my 6 R gt yz E R since R is symmetric gt MI 6 R l by de nition of R 1 Conversely7 Assume R R l and show R is symmetric To show R is symmetric we must show the implication if my 6 R then yz E R holds Assume my 6 R Then yx E R 1 by the de nition of the inverse But7 since R R l we have D 2 CLOSURE OF RELATIONS 26 Discussion Theorem 261 in Section 26 gives us an easy way to determine if a relation is symmetric 27 Paths DEFINITION 271 I A path of length n in a digraph G is a sequence of edges 07 z117 2 27 3 nily nl 2 If 0 xn the path is called a cycle or a circuit 3 UR is a relation on a set A and a and b are in A then a path of length n in R from a to b is a sequence of ordered pairs 07 1172273 39 39 39 nih 5 from R Discussion The re exive and symmetric closures are generally not hard to nd Finding the transitive closure can be a bit more problematic It is not enough to nd RoR R2 R2 is certainly contained in the transitive closure7 but they are not necessarily equal De ning the transitive closure requires some additional concepts Notice that in order for a sequence of ordered pairs or edges to be a path7 the terminal vertex of an arc in the list must be the same as the initial vertex of the next arc EXAMPLE 271 IfR aaabbd7 db7 ba is a relation on the set A abcd7 then dibbiaaiaaia is a path in R of length 4 28 Paths Vs Composition THEOREM 281 IfR be a relation on a set A then there is a path of length n from a to b in A if and only if ab 6 R PROOF by induction on n Basis Step An arc from a to b is a path of length 17 and it is a path of length 1 in R iff ab 6 RR1 2 CLOSURE OF RELATIONS 27 Induction Hypothesis Assume that there is a path of length n from a to b in R iff ab E R for some integer 71 Induction Step Prove that there is a path of length n 1 from a to b in R iff a b E Rn Assume a7 z117 2 39 39 39 niiwn 7175 is a path of length n 1 from a to b in R Then 07117 2 39 39 39 71717 in is a path of length n from a to an in R By the induction hypothesis a z E R and we also have pmb E R Thus by the de nition of Rn ab E Rn Conversely assurne ab E Rn R o R Then there is a 0 E A such that a0 E R and 0b E B By the induction hypothesis there is a path of length n in R from 0 to 1 Moreover a0 is a path of length 1 from a to 0 By concatenating a0 onto the beginning of the path of length n from 0 to b we get a path of length 71 1 from a to b This completes the induction step This shows by the principle of induction that There is a path of length n from a to 1 iff a b E R for any positive integer 71 Discussion Notice that since the statement is stated for all positive integers induction is a natural choice for the proof 29 Characterization of a Transitive Relation THEOREM 291 Let R S T U be relations on a set A 11fRQS andTQU thenRoTQSoU 2 UR Q S then R Q S for every positive integer n 3 UR is transitive then so is R for every positive integer n 4 If Rk Rj for somej gt k then RH RH for every positive integer in 5 R is transitive i R is contained in R for every positive integer 71 Discussion Theorem 291 in Section 29 give several properties that are useful in nding the transitive closure The most useful are the last two The second to the last property 2 CLOSURE OF RELATIONS 28 stated in the theorem tells us that if we nd a power of R that is the same as an earlier power7 then we will not nd anything new by taking higher powers The very last tells us that we must include all the powers of R in the transitive closure PROOF OF PROPERTY 1 Assume T and U are relations from A to B7 R and S are relations from B to C and R Q S and T Q U Prove RoT Q So U Let my 6 R o T Then by the de nition of cornposition7 there exists a b E B such that ab 6 T and b7 y E R Since R Q S and T Q U we have ab 6 U and b7 y E S This implies my 6 So U Since Ly was an arbitrary element of RoT we have shownRoT Q SoU D EXERCISE 291 Prove property 2 in Theorem 29 Hint use induction and property 1 EXERCISE 292 Prove property 3 in Theorem 291 Hint use induction on n EXERCISE 293 Prove property 4 in Theorem 291 EXERCISE 294 Prove property 5 in Theorem 29 210 Connectivity Relation DEFINITION 2101 The connectivity relation of the relation R denoted Pi is the set of ordered pairs ab such that there is a path in R from a to b P j R n1 211 Characterization of the Transitive Closure THEOREM 2111 Given a relation R on a set A the transitive closure of R tR Pi PROOF Let S be the transitive closure of R We will prove S P by showing that each contains the other 1 Proof of P Q S By property 5 of Theorem 2917 S Q S for all n7 since S is transitive Since R Q S7 property 2 of Theorem 291 irnplies R Q S for all n Hence7 R Q S for all n7 and so P OR Q S n1 2 CLOSURE OF RELATIONS 29 2 Proof of S Q Pi We will prove this by rst showing that P is transitive Suppose ab and bc are in Pi Then ab E R for some in 2 1 and bc E R for some n 2 1 This means there is a path of length m in R from a to b and a path of length n in R from b to c Concatenating these two paths gives a path of length m n in R from a to c That is ac E Rm Q Pi Thus Pi is transitive Since S is the transitive closure of B it must be contained in any transitive relation that contains R Thus S C Pi Discussion Theorem 2111 in Section 211 identi es the transitive closure tR of a relation R In the second part of the proof of Theorem 2111 we have used the de nition of the closure of a relation with respect to a property as given in Section 21 See also the discussion immediately following Section 21 212 Example EXAMPLE 2121 Let R be the relation on the set of integers given by ii1li E Z Then the transitive closure ofR is P ii E Z and h E ZJV EXAMPLE 2122 S is the relation The transitive closure is 2 CLOSURE OF RELATIONS 3O Discussion Here is another example EXAMPLE 2123 Let A be the set of all people and R the relation person z is a parent of person Then Pi is the relation person z is an ancestor of person 213 Cycles THEOREM 2131 IfR is a relation on a set A and 1A1 n then any path of length greater than or equal to n must contain a cycle PROOF Suppose x0x1z2 pm is a sequence in A such that xiAmi E R for i 1m7 where m 2 ii That is7 there is a path in R of length greater than or equal to n Since lAl n7 the pigeon hole principle implies that 1 pj for some i 31 j Thus7 assuming i lt j the path contains a cycle from 1 to pj D Discussion An easy way to understand what Theorern 2131 in Section 213 is saying is to look at a digraph Take the digraph 2 CLOSURE OF RELATIONS 31 Take any path of length greater than 4 Say7 abbd cl7 b baab By the theorem the path must have a cycle contained within it a path that begins and ends at the same vertex In this particular example there are several cycles eg7 a7b bdd7 b b7 a Notice if you eliminate this cycle you will have a shorter path with same beginning and ending vertex as the original path One of the points of Theorem 2131 is that if lAl n then Rk for h 2 n does not contain any arcs that did not appear in at least one of the rst n powers of R 214 Corollaries to Theorem 2131 COROLLARY 21401 If lAl n the transitive closure of a relation R on A is Pi RURZURSUuUR COROLLARY 21402 We can nd the connection matrip of P by computing the join of the rst n Boolean powers of the connection matricc of R Discussion The corollaries of Theorem 2131 in Section 214 give us powerful algorithms for computing the transitive closure of relations on nite sets Now7 it is possible for P RU R2 U U Rk for some h lt n7 but the point is that you are guaranteed that RROR2OOR if 1A1 71 215 Example 10 EXAMPLE 2151 LetR be the relation a7b7 c7 b7 cl7 a7 cc inA a7 bc7 d We nd the transitive closure by using the corollary in Section 214 The connectivity matrip for R is 0100 0000 0000 0000 2 M0110 M 01107 l1000 l0100l 2 CLOSURE OF RELATIONS 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 4 M OIIO andM 0110 0 0 0 0 0 0 0 0 Therefore the cormectivity matricc for P is 010 0 21 a 4 7 0 0 0 0 MVM VM VM 7 0110 110 0 Discussion In this example we use the basic algorithm to nd the transitive closure of a relation Recall MM QZ1M After taking the Boolean powers of the rnatrix7 we take the join of the four rnatrices While it did not happen on this exarnple7 it is possible for a Boolean power of the matrix to repeat before you get to the cardinality of A If this happens you may stop and take the join of the powers you have7 since nothing new will be introduced after that 216 Properties Vs Closure EXERCISE 2161 Suppose R is a relatiori ori a set A that is reflepive Prove or disprove a 5R is re eccive b tR is re eccive EXERCISE 2162 Suppose R is a relatiori ori a set A that is symmetric Prove or disprove a rR is symmetric b tR is symmetric EXERCISE 2163 Suppose R is a relatiori ori a set A that is trarisitive Prove or disprove a rR is trarisitive b 5R is trarisitive 3 EQUIVALENCE RELATIONS 33 3 Equivalence Relations 31 De nition of an Equivalence Relations DEFINITION 311 A relation R on a set A is an equivalence relation if and only ifR is o refleaive o symmetric and o transitive Discussion Section 31 recalls the de nition of an equivalence relation In general an equiv alence relation results when we wish to identify two elements of a set that share a common attribute The de nition is motivated by observing that any process of identi cation must behave somewhat like the equality relation and the equality relation satis es the re exive x z for all z symmetric x y implies y z and transitive x y and y 2 implies z 2 properties 32 Example EXAMPLE 321 Let R be the relation on the set R real numbers de ned by aRy i x 7 y is an integer Prove that R is an equivalence relation on R PROOF l Re exive Suppose z E R Then z 7 z 0 which is an integer Thus sz ll Symmetric Suppose my 6 R and ny Then z 7 y is an integer Since y 7 z 7x 7 y y 7 z is also an integer Thus sz lll Suppose my 6 R aRy and sz Then z 7 y and y 7 z are integers Thus the sum x 7 y y 7 z z 7 z is also an integer and so sz Thus R is an equivalence relation on R D Discussion EXAMPLE 322 Let R be the relation on the set of real numbers R in Example 1 Prove that if sz and yRy then x yR y PROOF Suppose sz and yRy In order to show that xyRz y we must show that x y 7 x y is an integer Since y y 96796 y7y 7 3 EQUIVALENCE RELATIONS 34 and since each of z 7 x and y 7 y is an integer by de nition of R x 7 x y 7 y is an integer Thus x yRz y D EXERCISE 321 In the eccarnple above show that it is possible to have sz and yRy but 969396 9 EXERCISE 322 Let V be the set of vertices ofa simple graph G De ne a relation R on V by va iffv is adjacent to w Prove or disprove R is an equivalence relation on V 33 Equivalence Classes DEFINITION 331 I Let R be an equivalence relation on A and let a E A The set a diaRx is called the equivalence class of a 2 The element in the bracket in the above notation is called the Representa tive of the equivalence class THEOREM 331 Let R be an equivalence relation on a set A Then the following are equivalent 1aRb 2 0115 3101 lbl7 0 PROOF 1 7 2 Suppose ab E A and aRb We must show that a Suppose z E a Then by de nition of a aRz Since R is symmetric and aRb bRa Since R is transitive and we have both bRa and aRx bRx Thus z E Suppose z E b Then bRx Since aRb and R is transitive aRz Thus z E a We have now shown that z E a if and only if z E Thus a 2 7 3 Suppose ab E A and a Then 1 b 1 Since R is re exive aRa that is a E 1 Thus a a W b 739 Q 3 7 1 Suppose 1 b 31 0 Then there is an x E 1 By de nition aRz and bRx Since R is symmetric sz Since R is transitive and both aRz and sz aRb D Discussion 3 EQUIVALENCE RELATIONS 35 The purpose of any identi cation process is to break a set up into subsets consist ing of mutually identi ed elements An equivalence relation on a set A does precisely this it decomposes A into special subsets7 called equivalence classes Looking back at the example given in Section 327 we see the following equivalence classes 0 0 Z the set of integers o is an odd integer o if 7T nln is an integer 7T n for any integer n Notice that 7 The number i is a representative of i but 7 is also a representative of lndeed7 any element of an equivalence class can be used to represent that equivalence class These ideas are summed up in Theorem 331 in Section 33 When we say several statements7 such as P1 P2 and P3 are equivalent7 we mean P1 lt gt P2 lt gt P3 is true Notice that in order to prove that the statements are mutually equivalent7 it is suf cient to prove a circle of implications7 such as P1 a P2 a P3 a P1 This is how we set up the proof of Theorem 331 34 Partition DEFINITION 341 A collection 5 of nonempty subsets of a set A is a partition ofA if I S S ifS andS are inS andSy S and 2 AUSlS S THEOREM 341 The equivalence classes of an equivalence relation on A form a partition of A Conversely given a partition on A there is an equivalence relation with equivalence classes that are emactly the partition given Discussion The de nition in Section 34 along with Theorem 341 describe formally the prop erties of an equivalence relation that motivates the de nition Such a decomposition is called a partition For example7 if we wish to identify two integers if they are either both even or both odd7 then we end up with a partition of the integers into two sets7 the set of even integers and the set of odd integers The converse of Theo rem 341 allows us to create or de ne an equivalence relation by merely partitioning a set into mutually exclusive subsets The common attribute then might just be that elements belong to the same subset in the partition 3 EQUIVALENCE RELATIONS 36 the notation used in the second part of Theorem 341 means that we take the union of all the sets that are members of the set to the far right and this union is de ned to be set A DEFINITION 342 IfR is an equivalence relation on a set A the set of equivalence classes ofR is denoted AR Theorem 341 follows fairly easily from Theorem 331 in Section 33 Here is a proof of one part of Theorem 341 PROOF Suppose R is an equivalence relation on A and S is the set of equivalence classes of R If S is an equivalence class7 then S a for some a E A hence7 S is nonempty7 since aRa by the re exive property of B By Theorem 3317 if S a and S b are in 57 then a b iff a b 74 0 Since this is a biconditional7 this statement is equivalent to a 74 b iff a b Q Since each equivalence class is contained in A7 USlS E S Q A But7 as we just saw7 every element in A is in the equivalence class it represents7 so A Q UfSlS E S This shows USlS E S A EXERCISE 341 Prove the converse statement in Theorem 341 35 Intersection of Equivalence Relations THEOREM 351 If R1 and R2 are equivalence relations on a set A then R1 R2 is also an equivalence relation on A Discussion To prove Theorem 3517 it suf ces to show the intersection of o re exive relations is re exive7 o symmetric relations is symmetric7 and o transitive relations is transitive But these facts were established in the section on the Review of Relations 36 Example EXAMPLE 361 Let in be a positive integer The relation a E b mod m is an equivalence relation on the set of integers 3 EQUIVALENCE RELATIONS 37 PROOF Re exive If a is an arbitrary integer then a 7 a 0 0 m Thus a E a mod Symmetric If a E brnod m then a 7 b k m for some integer k Thus b 7 a 7k m is also divisible by m and so b E arnod Transitive Suppose a E b rnod m and b E c rnod Then a 7 b k m and b 7 c Z m for some integers k and Z Then a7ca7bb7ckmlmklm is also divisible by in That is aEcrnod D Discussion Recall the congruence relations on the set Z of integers Given an positive integer in and integers a and b a E b rnod in read a is congruent to b rnodulo m iff mla 7 b that is a 7 b k m for some integer k EXERCISE 361 What are the equivalence classes for the congruence relation 1aEbmod2 2 aEbmod 3 3 aEbmod 5 Given a positive integer in the equivalence classes under the relation a E b rnod m have canonical representatives If we use the Division Algorithm to divide the integer a by the integer in we get a quotient q and rernainder r 0 S r lt in satisfying the equation a mq r Recall that r amodm and that a E rrnod Thus a r and so there are exactly in equivalence classes 01m71 If R is the congruence rnodulo in relation on the set Z of integers the set of equivalence classes ZR is usually denoted by either Zm or ZmZ That is Zm l0l7 l1l7 lm ll REMARK 361 IfA is an in nite set and R is an equivalence relation on A then AR may be nite as in the example above or it may be in nite As the following exercise shows the set of equivalences classes may be very large indeed EXERCISE 362 Let R be the equivalence relation de ned on the set of real num bers R in Example 32 Section That is ny iffx 7 y is an integer Prove that every equivalence class has a unique canonical representative r such that 0 S r lt 1 That is for every x there is a unique r such that r and 0 S r lt 1 Hint39 You might recall the floor function fx 3 EQUIVALENCE RELATIONS 38 37 Example EXAMPLE 371 Let R be the relation on the set of ordered pairs of positive inte gers such that abRcd if and only if ad bc 0 R is an equivalence relation 0 The equivalence class of 23 273 2k73k k E Z 0 There is a natural bijection between the equivalence classes of this relation and the set of positive rational numbers Discussion Notice that the relation R in Example 371 is a relation on the set Z4r gtlt Z4 and so R Q Z4r gtlt Z4 gtlt Z4r gtlt Zt PROOF R IN EXAMPLE 371 IS AN EQUIVALENCE RELATION We must show that R is re exive7 symmetric7 and transitive l Re exive Let a7b be an ordered pair of positive integers To show R is re exive we must show ab7 ab E R Multiplication of integers is commutative7 so ab ba Thus a7 b7 ab E R Symmetric Let a7b and ed be ordered pairs of positive integers such that abRcd recall this notation is equivalent to abcd E R Then ad be This equation is equivalent to cb da7 so cdRab This shows R is symmetric Transitive Let db7 cd7 and e7f be ordered pairs of positive integers such that abRcd and cdRef Then ad be and cf de Thus7 adf bcf and bcf bde7 which implies adf bde Since d 31 07 we can cancel it from both sides of this equation to get of be This shows a7 bRe7 f7 and so R is transitive gt lt gt lt l gt lt gt lt B One of the points of this example is that there is a bijection between the equiva lence classes of this relation and the set of positive rational numbers In other words7 the function f Z4r gtlt ZR ablab is an equivalence class of R a Q4r de ned by fab ab is well de ned and is a bijection This follows from the fact that a C ab cd gt abRcd gt ad bc gt 3 3 EQUIVALENCE RELATIONS 39 EXERCISE 371 Let R be the relation de ned on the set of ordered pairs Z4r gtlt Z4r of positive integers de ned by abRcd gt ad bc I Prove that R is an equivalence relation on Z4r gtlt Z4 2 List 5 different members of the equivalence class 14 EXERCISE 372 Let R be the relation de ned on the set of ordered pairs Z4r gtlt Z4r of positive integers de ned by abRcd gt ad bc Prove that the function f Z4r gtltZR a Z de ned by fa bl aib is well de ned and a bijection 38 Isomorphism is an Equivalence Relation THEOREM 381 Let S be a set of simple graphs De ne a relation R on S as follows IfGH S then GH ERifand only iszH This is equivalent to G H E R if and only if there epists an isomorphism f VG a VH that preserves adjacencies Then R is an equivalence relation on S PROOF Re exive Suppose G E S We need to show G G E R De ne the function f VG a VG by fv v for every vertex v E VG Then f is the identity function on VG hence f is a bijection f 1L f Clearly v and u are adjacent in G if and only if fv v and fu u are adjacent Thus GG E R Symmetric Suppose G H E S and G H E R Then there exists an isomorphism f VG a We need to nd an isomorphism g VH a VG Since f is abijection f is invertible Thus the map f l VH a VG is de ned and we shall show it is an isomorphism We know the inverse of a bijection is itself a bijection so all we need to show is that f 1 preserves adjacency Suppose uv E Then f 1u z and f 1v y are vertices of G 3 EQUIVALENCE RELATIONS 4O Now7 we know f preserves adjacency7 so z and y are adjacent in G if and only if fd u and fy i are adjacent in H Use the previous equations to rewrite this statement in terms ofu and i f 1u and f 1o y are adjacent in G if and only if u and i are adjacent in H Thus f l preserves adjacency7 and so H7 G E R Transitive Suppose GHK E S are graphs such that GH7 H7K E R We need to prove G7K E R Since G7 H and HK are in R7 there are isomorphisms f VG a VH and g VH a We need to nd an isomorphism h VG a Notice that we have used di erent letters for the functions here The function g is not necessarily the same as the function f so we cannot call it f as well Let h g o f We will show h is an isomorphism Since the composition of bijections is again a bijection7 g o f VG a VK is a bijection What we still need to show is that the composition preserves adjacency Let u and i be vertices in G Recall that f must preserve adjacency Therefore7 u and i are adjacent in G if and only if fu and fo are adjacent in H But since 9 preserves adjacency7 fu and fi are adjacent in H if and only if gfu and gfo are adjacent in K Using the fact that if and only if7 is transitive7 we see that u and i are adjacent in G if and only if g o and g o fi are adjacent in K This implies that gof preserves adjacency7 and so gof VG a VK is an isomorphism D Discussion Section 38 recalls the notion of graph isomorphism Here we prove that graph isomorphism is an equivalence relation on any set of graphs It is tempting to say that graph isomorphism is an equivalence relation on the set of all graphs7 but logic precludes the existence of such a set 39 Equivalence Relation Generated by a Relation R DEFINITION 391 Suppose R is a relation on a set A The equivalence relation on A generated by a R denoted R5 is the smallest equivalence relation on A that contains R Discussion 3 EQUIVALENCE RELATIONS 41 There are occasions in which we would like to de ne an equivalence relation on a set by starting with a primitive notion of equivalence which in itself may not satisfy one or more of the three required properties For example consider the set of vertices V of a simple graph G and the adjacency relation R on V uRv iff u is adjacent to v You would have discovered while working through Exercise 322 that for most graphs R is neither re exive nor transitive EXERCISE 391 Suppose V is the set of vertices of a simple graph G and R is the adjacency relation on V39 uRv iffu is adjacent to v Prove that R5 is the relation uRev iff either u v or there is a path in G from u to v 310 Using Closures to nd an Equivalence Relation THEOREM 3101 Suppose R is a relation on a set A Then R5 the equivalence relation on A generated by R is the relation tsrR That is Rs may be obtained from R by taking 1 the refleccive closure rR of R then 2 the symmetric closure srR of rR and then 3 the transitive closure tsrR of srR PROOF Suppose R is a relation on a set A We must show 1 tsrR is an equivalence relation containing R and 2 if S is an equivalence relation containing R then tsrR Q S Proof of l Re exive If a E A then aa E rR hence aa E tsrR since MR g tow ll Symmetric Suppose a b E tsrR Then there is achain a 1 12 pmb in srR Since srR is symmetric bpnx2x1x1a are in srR Hence ba E tsrR since tsrR is transitive Transitive tsrR being the transitive closure of srR is transitive by de nition 1 gt lt gt lt Proof of Suppose S is an equivalence relation containing R gt lt Since S is re exive S contains the re exive closure of R That is rR Q S Since S is symmetric and rR Q S S contains the symmetric closure of rR That is srR Q S III Since S is transitive and srR Q S S contains the transitive closure of srR That is tsrR S gt lt gt lt D 3 EQUIVALENCE RELATIONS 42 Discussion Theorem 3101 in Section 310 describes the process by which the equivalence relation generated by a relation R can be constructed using the closure operations discussed in the notes on Closure As it turns out7 it doesnt matter whether you take the re exive closure before you take the symmetric and transitive closures7 but it is important that the symmetric closure be taken before the transitive closure EXERCISE 3101 Given a relation R on a set A prove that R5 RUAUR UR See the lecture notes on Closure for de nitions of the terminology EXERCISE 3102 Suppose A is the set of all people alive or dead and R is the relation quotis a parent of Describe the relation R5 in words What equivalence class do you represent EXERCISE 3103 Give an eccarnple of a relation R on a set A such that R5 31 800030 4 PARTIAL ORDERINGS 43 4 Partial Orderings 41 De nition of a Partial Order DEFINITION 411 I A relation R on a set A is a partial order i R is o reflepive o antisymmetric and o transitive 2 AR is called a partially ordered set or a poset 3 If in addition either aRb or bRa for every ab E A then R is called a total order or a linear order or a simple order In this case AR is called a chain 4 The notation a j b is used for aRb when R is a partial order Discussion The classic example of an order is the order relation on the set of real numbers aRb iff a S b which is in fact a total order It is this relation that suggests the notation a j b but this notation is not used exclusively for total orders Notice that in a partial order on a set A it is not required that every pair of elements of A be related in one way or the other That is why the word partial is used 42 Examples EXAMPLE 421 Z S is a poset Every pair of integers are related via 3 so 3 is a total order and Z S is a chain EXAMPLE 422 IfS is a set then PS Q is a poset EXAMPLE 423 Z is a poset The relation all means quota divides b Discussion Example 422 better illustrates the general nature of a partial order This partial order is not necessarily a total order that is it is not always the case that either A Q B or B Q A for every pair of subsets of S Can you think of the only occasions in which this would be a total order Example 423 is also only a partial order There are many pairs of integers such that a and bXa 4 PARTIAL ORDERINGS 44 43 PseudoOrderings DEFINITION 431 A relation 4 on S is called a pseudoorder if 0 the relation is irre epive and o transitive Some teccts call this a quasiorder Rosen uses quasi order to mean a di erent type of relation though THEOREM 431 Theorems and Notation 1 Given a poset S 5 we de ne a relation 4 on S by z 4 y if and only if z j y and z 74 y The relation 4 is a pseudo order 2 Given a set S and a pseudo order 4 on S we de ne a relation 5 on S by z j y if and only ifz 4 y or z y The relation 5 is a partial order 3 Given a poset S 5 we de ne the relation on S by z i y i y j x S i is a poset and i is the inverse off 4 Given a set S and a pseudo order 4 on S we de ne the relation gt on S by z gt y i y 4 x gt is a pseudo order on S and gt is the inverse of 4 5 In any discussion of a partial order relation j we will use the notations 4 i and gt to be the relations de ned above depending on j Similarly if we are given a a pseudo order 4 then 5 will be the partial order de ned in part 2 Discussion The notation above is analogous to the usual 3 gt lt and gt notations used with real numbers We do not require that the orders above be total orders though Another example you may keep in mind that uses similar notation is Q Q C D on sets These are also partial and pseudo orders EXERCISE 431 Prove a pseudo order 4 is antisymmetric EXERCISE 432 Prove Theorem 431 part 1 EXERCISE 433 Prove Theorem 431 part 2 44 WellOrdered Relation DEFINITION 441 Let R be a partial order on A and suppose S Q A I An elements 6 S is a least element ofS i 51 for every b E S 2 An element 5 E S is a greatest element ofS i st for every b E S 4 PARTIAL ORDERINGS 45 3 A chain AB is wellordered i every nonempty subset ofA has a least element Discussion Notice that if s is a least greatest element of S 5 must be an element of S and 5 must precede be preceded by all the other elements of S Confusion may arise when we de ne a partial order on a well known set7 such as the set Z4r of positive integers7 that already has a natural ordering One such ordering on Z4r is given in Example 423 As another example7 one could perversely impose the relation 5 on Z4r by de ning a j b iff b S a With respect to the relation j Z4r would have no least element and its greatest77 element would be 11 This confusion may be alleviated somewhat by reading a j b as a precedes b77 instead of a is less than or equal to b 7 especially in those cases when the set in question already comes equipped with a natural order different from j 45 Examples EXAMPLE 451 Z7 3 is a chain but it is not well ordered EXAMPLE 452 NS is well ordered EXAMPLE 453 Z17 2 is a chain but is not well ordered Discussion In Example 4517 the set of integers does not have a least element If we look at the set of positive integers7 however7 every nonempty subset including Z has a least element Notice that if we reverse the inequality7 the least element77 is now actually the one that is larger than the others 7 look back at the discussion in Section 44 7 and there is no least element77 of Z5 Pay careful to the de nition of what it means for a chain to be well ordered It requires every nonempty subset to have a least element7 but it does not require that every nonempty subset have a greatest element EXERCISE 451 Suppose A7 5 is a poset such that every nonempty subset ofA has a least element Prove that j is a total ordering on A 4 PARTIAL ORDERINGS 46 46 Lexicographic Order DEFINITION 461 Given two posets 1151 and 1252 we construct an in duced or lexicographic partial order jL on A1 gtlt A2 by de ning phyl jL x2y2 of 0 p1 lt1 2 or 0 1 2 andyl 52 12 This de nition is emtended recursively to Cartesian products of partially ordered sets A1 gtltA2gtltgtltAL Discussion EXERCISE 461 Prove that if each of the posets A1 51 and 1252 is a chain and jL is the ledicographic order on A1 gtlt A2 then A1 gtlt A2 5L is also a chain EXERCISE 462 Suppose for each positive integer n Ampreceqn is a poset Give a recursive de nition for the ledicographic order on A1 gtlt A2 gtlt gtlt An for all positive integers n 47 Examples 471 and 472 EXAMPLE 471 Let A1 A2 ZJI and j1jg 1 divides Then 274 5L 278 0 o 24 is not related under jL to 2 6 o 24 5L 45 EXAMPLE 472 Let A ZJI and 5 1 fori 1234 Then 0 2345 jL 2382 0 2345 is not related under jL to 36810 0 2345 is not related under jL to 23510 Discussion Notice that 24 does not precede 2 6 although their rst entries are equal 4 does not divide 6 In fact the pairs 24 and 26 are not related in any way On the other hand since 214 and 2 31 4 we do not need to look any further than the rst place to see that 24 jL 45 Notice also in Example 472 the rst non equal entries determine whether or not the relation holds 4 PARTIAL ORDERINGS 47 48 Strings We extend the leXigraphic ordering to strings ofelements in a poset A7 5 as follows 0102 39am 5L b1b2quot39bn iff 0 117027 7at jL b17b27 7b where t minmn7 or o a17a2am b17b2bm andm ltn Discussion The ordering de ned on strings gives us the usual alphabetical ordering on words and the usual order on bit string EXERCISE 481 Put the bit strings 01101001 and 010 in increasing order using I numerical order by considering the strings as binary numbers 2 leccicographic order using 0 lt 1 There are numerous relations one may impose on products Lexicographical order is just one partial order EXERCISE 482 Let 1151 and 1252 be posets De ne the relation 5 on A1 gtlt A2 by 11702 5 b1L7 b2 if and only ifaL jl b1 and a2 jg b2 Prove j is a partial order This partial order is called the product order 49 Hasse or Poset Diagrams DEFINITION 491 To construct a Hasse or poset diagram for a poset AR 1 Construct a digraph representation of the poset AR so that all arcs point up ecccept the loops 2 Eliminate all loops 3 Eliminate all arcs that are redundant because of transitiuity 4 Eliminate the arrows on the arcs Discussion The Hasse diagram of a poset is a simpler version of the digraph representing the partial order relation The properties of a partial order assure us that its digraph can be drawn in an oriented plane so that each element lies below all other elements it precedes in the order Once this has been done7 all redundant information can be removed from the digraph and the result is the Hasse diagram 4 PARTIAL ORDERINGS 48 410 Example 4101 EXAMPLE 4101 The Hasse diagram for Pabc is Discussion The following steps could be used to get the Hasse diagram above 1 You can see that even this relatively simple poset has a complicated digraph 2 Eliminate the loops 4 PARTIAL ORDERINGS 4 Finally eliminate the arrows 4 PARTIAL ORDERINGS 50 EXERCISE 4101 Construct the Hasse diagram for the poset 1 2 34 6 9 12 1 where 1 is the divides relatiori EXERCISE 4102 Is the diagram the Hasse diagram for a partial order If so give the partial order arid if riot edplairi why a b 411 Maximal and Minimal Elements DEFINITION 4111 Let AR be a poset I Art elemerit a E A is a minimal element if there does riot ecoist art elemerit bEA by a such thatbja 2 Art elemerit a E A is a maximal element if there does riot ecoist art elemerit bEA by a such thatajb Discussion 4 PARTIAL ORDERINGS 51 Another useful way to characterize minimal elements of a poset A j is to say that a is a minimal element of A iff b j a implies b a A similar characterization holds for maximal elements It is possible for a poset to have more than one maximal and minimal element In the poset in Exercise 4101 for example 1 is the only minimal element but both 9 and 12 are maximal elements These facts are easily observable from the Hasse diagram 412 Least and Greatest Elements DEFINITION 4121 Let A j be a poset I An element a E A is the least element ofA ifa j b for every element b e A 2 An element a E A is the greatest element ofA ifb j a for every element b e A THEOREM 4121 A poset A 5 can have at most one least element and at most one greatest element That is least and greatest elements are unique if they eaist Discussion We revisit the de nition of greatest and least elements which were de ned in Section 44 As with minimal and maximal elements Hasse diagrams can be helpful in illustrating least and greatest elements Although a poset may have many minimal or maximal elements Theorem 4121 guarantees that it may have no more than one least or greatest element We ask you to explore the relationship among these concepts in the following exercise EXERCISE 4121 Let A j be a poset a Prove that ifa is the least element of A then a is a minimal element of A b Prove that ifb is the greatest element of A then b is a mawimal element of e Prove that ifA has more than one minimal element then A does not have a least element d Prove that ifA has more than one mamimal element then A does not have a greatest element 413 Upper and Lower Bounds DEFINITION 4131 Let S be a subset ofA in the poset A j I If there ecoists an element a E A such that s j a for all s E S then a is called an upper bound on S 4 PARTIAL ORDERINGS 52 2 If there exists an element a E A such that a j s for all s E S then a is called an lower bound on S 414 Least Upper and Greatest Lower Bounds DEFINITION 4141 Suppose A j is a poset S a is subset ofA and a E A I a is the least upper bound ofS if 0 a is an upper bound ofS and o ifs is another upper bound of S then a j s 2 a is the greatest lower bound ofS if 0 a is an lower bound ofS and o ifs is another lower bound of S then s j a Discussion In Section 413 we extend the concepts upper and lower bound as well as least upper bound and greatest lower bound to subsets of a poset The difference between a least element of a subset of A and a lower bound for the subset of A is that the least element is required to be in the subset and the lower bound is not Here are a few facts about lower bounds and minimal elements to keep in mind You should rephrase each statement replacing lower with upper etc o For a to be a lower bound for a subset S a need not be in S but it must precede every element of S o A minimal element a of a subset S is a lower bound for the set of all elements in S preceded by a o A subset may have more than one lower bound or it may have none 0 A subset may have lower bounds but no greatest lower bound EXAMPLE 4141 Suppose we are given the poset A l where A 1 2 34 68 9 12 I The subset 2346 has no greatest or least element 2 1 is the greatest lower bound for 2346 and 12 is its least upper bound 3 The subset 1 238 has no upper bound in A 4 Every subset ofA has a greatest lower bound EXERCISE 4141 Consider the poset A Q where A PS is the power set of a set S Prove that every nonempty subset ofl has a least upper bound and a greatest lower bound in A 415 Lattices DEFINITION 4151 A poset Aj is a lattice if every pair of elements has a least upper bound and a greatest lower bound in A 4 PARTIAL ORDERINGS 53 Discussion To check if a poset is a lattice you must check every pair of elements to see if they each have a greatest lower bound and least upper bound If you draw its Hasse diagram7 you can check to see whether some pair of elements has more than one upper or lower bound on the same level If so7 then the poset is not a lattice 416 Example 4161 EXAMPLE 4161 The poset given by the following Hasse diagram is not a lattice 6 Discussion In Example 4161 notice that a7 b has upper bounds c7 d and e Since e is larger than either c or d7 it cannot be the least upper bound But c and d are not related in any way Thus there is no least upper bound for the subset a7 b EXERCISE 4161 Prove that the poset 138 C is a lattice 7 7 417 Topological Sorting DEFINITION 4171 I A total ordering S on a set A is said to be compatible with a partial ordering j on A ifa j b implies a S b for all ab 6 A 2 A topological sorting is a process of constructing a compatible total order for a given partial order Discussion A topological sorting is a process of creating a total order from a partial order Topological sorting has a number of applications For example 4 PARTIAL ORDERINGS 54 o It can be useful in PERT charts to determine an ordering of tasks o It can be useful in graphics to render objects from back to front to expose hidden surfaces 0 A painter often uses a topological sort when applying paint to a canvas Heshe paints parts of the scene furthest from the view rst There may be several total orders that are compatible with a given partial order 418 Topological Sorting Algorithm procedure topological sort A7 5 nite poset While A 31 Q begin ak a minimal element of A A A 7 ak k k 1 end 11 12 an is a compatible total ordering of A Discussion In order to justify the existence of a minimal element of S at each step in the topological sorting algorithm7 we need to prove Theorem 4191 in Section 419 419 Existence of a Minimal Element THEOREM 4191 Suppose Aj is a nite nonempty poset Then A has a minimal element PROOF Suppose Aj is a nite nonempty poset7 where A has n elements7 n 2 1 We will prove that A has a minimal element by mathematical induction BASIS STEP n 1 Then A a and a is a minimal least element of A INDUCTION STEP Suppose that every poset having n elements has a minimal element Suppose Aj is a poset having n 1 elements Let a be an arbitrary element of A7 and let S A 7 1 Then S7 together with the partial order 5 restricted to S7 is a poset with n elements By the inductive hypothesis7 S has a minimal element b There are two possibilities 1 a j b Then a is a minimal element of A Otherwise7 there is an element 0 in A7 different from 17 such that c j 1 But then c is in S7 0 is different from b why7 and c 5 b7 which contradicts the fact that b is a minimal element of S 4 PARTIAL ORDERINGS 55 2 a f b Suppose b is not a minimal element of A Then there is a c E A with c j b Since a f b we have 0 7E a Thus 0 E S and we then conclude b is not minimal in S This is a contradiction so there are no elements of A that preceed b Hence b is a minimal element of A in this case Thus7 in any case A has a minimal element7 and so by the principle of induction every nite poset has a minimal element EXERCISE 4191 Let A7514 be a poset and let S Q A De ne jg on S by Va7b E Sla jgb a 5A b Prove S7 55 is a poset The partial order jg is the Restriction of 5A to S and we usually use the same notation for both partial orders EXAMPLE 4191 Consider the set of rectangles T and the relation R given by tRs ift is more distant than 5 from the viewer Here are some ofthe relations that we ndfrorn the gure 1R27 1147 1R7 ABS7 3127 BBQ7 3R6 The Hasse diagram for R is 4 PARTIAL ORDERINGS 56 4 3 If we draw 1 it would also be rte to use 8 out of the diagram artd delete it we get 4 3 Th ert draw 8 4 PARTIAL ORDERINGS 57 and so on By drawing minimal elements you may get the following total order there are many other total orders compatible with the partial order 4 m b W U1 G Nl CHAPTER 2 Graphs 1 Introduction to Graphs and Graph Isomorphism 11 The Graph Menagerie DEFINITION 111 o A simple graph G V E consists of a set V of uertices and a set E of edges represented by unordered pairs of elements of V o A multigraph consists ofa set V of uertices a set E of edges and afunction fE uoui Vandu7 o Ife1 e2 6 E are such that fe1 fe2 then we say el and e2 are multiple or parallel edges 0 A pseudograph consists of a set V of uertices a set E of edges and a function f E a uo uo E V Ife E E is such that fe uu u then we say e is a loop 0 A directed graph or digraph G V E consists of a set V of uertices and a set E of directed edges represented by ordered pairs of uertices Discussion In Section 11 we recall the de nitions of the various types of graphs that were introduced in MAD 2104 In this section we will revisit some of the ways in which graphs can be represented and discuss in more detail the concept of a graph isomor phisrn 12 Representing Graphs and Graph Isomorphism DEFINITION 121 The adjacency matrix A aw for a simple graph G V E where V 111112 on is de ned by H 7 1 if yinj is an edge ofG 0 7 0 otherwise Discussion 58 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 59 We introduce some alternate representations which are extensions of connection matrices we have seen before7 and learn to use them to help identify isomorphic graphs REMARKS 121 Here are some properties of the adjacency matricc of an undirected graph 1 The adjacency matricc is always symmetric 2 The uertices must be ordered and the adjacency matricc depends on the order chosen 3 An adjacency matricc can be de ned for multigraphs by de ning aij to be the number of edges between uerticesi and j 4 If there is a natural order on the set of uertices we will use that order unless otherwise indicated V1 V2 V5 V4 EXAMPLE 121 An adjacency matrip for this graph is 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 Discussion As with connection matrices7 an adjacency matrix can be constructed by using a table with the columns and rows labeled with the elements of the vertex set Here is another example 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 6O EXAMPLE 122 The adjacency matricc for the graph 1 U2 u5 U3 u4 0 0 1 1 1 0 0 1 0 1 is the matrid M 1 1 0 1 1 1 0 1 0 1 L1 1 1 1 OJ 13 Incidence Matrices DEFINITION 131 The incidence matrix A aw for the undirected graph G V7 E is de ned by 7 1 if edgej is incident with uertecci 0 7 0 otherwise Discussion The incidence matrix is another way to use matrices to represent a graph REMARKS 131 I This method requires the edges and uertices to be labeled and the matricc de pends on the order in which they are written 2 Every column will have eccactly two 1 s 3 As with adjacency matrices if there is a natural order for the uertices and edges that order will be used unless otherwise speci ed 14 Example 141 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 61 V1 61 V2 e5 62 e 5 e 5 V3 37 e3 V5 64 V4 EXAMPLE 141 The incidence matricc for this graph is 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 Discussion Again you can use a table to get the matrix List all the vertices as the labels for the rows and all the edges for the labels of the columns 15 Degree DEFINITION 151 I Let G V7 E be an undirected graph 0 Two uertices um E V are adjacent or neighbors if there is an edge e between u and o i The edge e connects u and o i The uertices u ando are endpoints of e o The degree of a uertem o denoted dego is the number of edges for which it is an endpoint A loop contributes twice in an undirected graph Ifdego 0 then i is called isolated Ifdego 1 then i is called pendant 2 Let G V7 E be a directed graph 0 Let uo be an edge in G Then u is an initial vertex and is adjacent to o The uertem i is a terminal vertex and is adjacent from u o The in degree of a uertem o denoted deg o is the number of edges which terminate at o 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 62 0 Similarly the out degree ofu denoted degi is the number of edges which initiate at 1 Discussion We now recall from MAD 2104 the terminology we use with undirected and di rected graphs Notice that a loop contributes two to the degree of a vertex 16 The Handshaking Theorem THEOREM 161 The Handshaking Theorem Let G V7 E be an undirected graph Then 2lEl Zdegw 116V PROOF Each edge contributes twice to the sum of the degrees of all vertices D Discussion The handshaking theorem is one of the most basic and useful combinatorial for mulas associated to a graph It lets us conclude some facts about the numbers of vertices and the possible degrees of the vertices Notice the immediate corollary COROLLARY 1611 The sum of the degrees of the uertiees in any graph must be an even number In other words7 it is impossible to create a graph so that the sum of the degrees of its vertices is odd try itl 17 Example 171 EXAMPLE 171 Suppose a graph has 5 uertiees Can eaeh uertep haue degree 3 degree 4 o The sum of the degrees of the uertiees would be 35 if the graph has 5 uertiees of degree 3 This is an odd number though so this is not possible by the handshahing Theorem 0 The sum of the degrees of the uertiees if there are 5 uertiees with degree 4 is 20 Since this is even it is possible for this to equal 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 63 Discussion If the sum of the degrees of the vertices is an even number then the handshaking theorem is not contradicted In fact you can create a graph with any even degree you want if multiple edges are permitted However if you add more restrictions it may not be possible Here are two typical questions the handshaking theorem may help you answer EXERCISE 171 Is it possible to have a graph S with 5 vertices each with degree 4 arid 8 edges EXERCISE 172 A graph with 21 edges has 7 vertices of degree 1 three of degree 2 severi of degree 3 arid the rest of degree 4 How mariy vertices does it have 18 Theorem 181 THEOREM 181 Every graph has ari everi number of vertices of odd degree PROOF Let V2 be the set of vertices of odd degree and let V5 be the set of vertices of even degree Since V V2 U V5 and V2 V5 Q the handshaking theorem gives us 2lEl Zdegp Z deg1 Z degi 116V HEVO UEVE Z degi 2lEl 7 Z degi ueVO veVg Since the sum of any number of even integers is again an even integer the right hand side of this equations is an even integer So the left hand side which is the sum of a collection of odd integers must also be even The only way this can happen however is for there to be an even number of odd integers in the collection That is the number of vertices in V2 must be even D 01 Discussion Theorem 181 goes a bit further than our initial corollary of the handshaking theorem If you have a problem with the last sentence of the proof consider the following facts 0 odd odd even 0 odd even odd 0 even even even If we add up an odd number of odd numbers the previous facts will imply we get an odd number Thus to get an even number out of End0 degi there must be an even number of vertices in V2 the set of vertices of odd degree 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 64 While there must be an even number of vertices of odd degree7 there is no restric tions on the parity even or odd of the number of vertices of even degree This theorem makes it easy to see7 for example7 that it is not possible to have a graph with 3 vertices each of degree 1 and no other vertices of odd degree 19 Handshaking Theorem for Directed Graphs THEOREM 191 For my directed graph G EV 1E1 Edam Edam 116V 116V Discussion When considering directed graphs we differentiate between the number of edges going into a vertex verses the number of edges coming out from the vertex These numbers are given by the in degree and the out degree Notice that each edge contributes one to the in degree of some vertex and one to the out degree of some vertex This is essentially the proof of Theorem 191 110 Graph Invariants The following are invariants under isomorphism of a graph G G has 7 vertices G has 5 edges G has degree sequence d17d27 dn G is a bipartite graph 5 G contains 7 complete graphs Kn as a subgraphs G contains 7 complete bipartite graphs Km G contains 7 n cycles G contains 7 n wheels G contains 7 n cubes Discussion Recall that two simple graphs G1 V1L7 E1 and G2 V27E2 are isomorphic if there is a bijection f3 V1 V2 such that vertices u and 1 in V1 are adjacent in G1 if and only if u and f1 are adjacent in G2 If there is such a function7 we say f is an isomorphism and we write G1 2 G2 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 65 It is often easier to determine when two graphs are not isomorphic This is some times made possible by comparing invariants of the two graphs to see if they are different We say a property of graphs is a graph invariant or just invariant if whenever a graph G has the property any graph isomorphic to G also has the prop erty The degree sequence a graph G with n vertices is the sequence d1 d2 d where d1d2dn are the degrees of the vertices of G and d1 2 d2 2 2 d Note that a graph could conceivably have in nitely many vertices If the vertices are countable then the degree sequence would be an in nite sequence If the vertices are not countable then this degree sequence would not be de ned The invariants in Section 110 may help us determine fairly quickly in some ex amples that two graphs are not isomorphic EXAMPLE 1101 Show that the following two graphs are not isomorphic 1 2 a b G1 G2 The two graphs have the same number of vertices the same number of edges and same degree sequences 33 3 3 2 2 2 2 Perhaps the easiest way to see that they are not isomorphic is to observe that G1 has three 4 cycles whereas G2 has two 4 cycles In fact the four vertices of G1 of degree 3 lie in a 4 cycle in G1 but the four vertices of G2 of degree 3 do not Either of these two discrepancies is enough to show that the graphs are not isomorphic Another way we could recognize the graphs above are not isomorphic is to consider the adjacency relationships Notice in G1 all the vertices of degree 3 are adjacent to 2 vertices of degree 3 and Z of degree 2 However in graph G2 all of the vertices of degree 3 are adjacent to Z vertep of degree 3 and 2 vertices of degree 2 This discrepancy indicates the two graphs cannot be isomorphic EXAMPLE 1102 The following two graphs are not isomorphic Can you nd an invariant that is di erent on the graphs 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 66 1 2 a b G1 G2 111 Example 1111 EXAMPLE 1111 Determine whether the graphs G1 arid G2 are isomorphic v5 v4 Solution We go through the following checklist that might tell us immediately if the two are riot isomorphic 0 They have the same number of vertices7 5 0 They have the same number of edlges7 8 0 They have the same degree sequence 4437 37 2 Since there is no obvious reason to think they are not isomorphic7 we try to construct an isomorphism7 f Note that the above does riot tell us there is an isomorphism7 only that there might be one 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 67 The only vertex on each that have degree 2 are 113 and u2 so we must have 03 U2 Now7 since deg111 degv5 degu1 degu47 we must have either 0 f111 ul and f115 u4 or o f111 U4 and f115 ul It is possible only one choice would work or both choices may work or neither choice may work7 which would tell us there is no isomorphism We try f111 U1 and 05 4 Similarly we have two choices with the remaining vertices and try f12 us and f114 U5 This de nes a bijection from the vertices of G1 to the vertices of G2 We still need to check that adjacent vertices in G1 are mapped to adjacent vertices in G2 To check this we will look at the adjacency matrices The adjacency matrix for G1 when we list the vetices of G1 by 1117112703711405 is 01011 10111 A01010 11101 11010 We create an adjacency matrix for G2 using the bijection f as follows since f111 ul f112 us f113 u2 f114 U5 and f115 U4 we rearrange the order of the vertices of G2 to ulU3u2u5u4 With this ordering7 the adjacency matrix for G2 is 01011 10111 B01010 11101 11010 Since A B7 adjacency is preserved under this bijection Hence the graphs are isomorphic Discussion In this example we show that two graphs are isomorphic Notice that it is not enough to show they have the same number of vertices7 edges7 and degree sequence In fact7 if we knew they were isomorphic and we were asked to prove it7 we would 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 68 proceed directly to try and nd a bijection that preserves adjacency That is the check list is not necessary if you already know they are isomorphic On the other hand having found a bijection between two graphs that doesnt preserve adjacency doesn7t tell us the graphs are not isomorphic because some other bijection might work If we go down this path we would have to show that every bijection fails to preserve adjacency The advantage of the checklist is that it will give you a quick and easy way to show two graphs are not isomorphic if some invariant of the graphs turn out to be different If you examine the logic however you will see that if two graphs have all of the same invariants we have listed so far we still wouldnt have a proof that they are isomorphic Indeed there is no known list of invariants that can be ef ciently checked to determine when two graphs are isomorphic The best algorithms known to date for determining graph isomorphism have exponential complexity in the number n of vertices EXERCISE 1111 Determine whether the following two graphs are isomorphic 1 2 a b G1 G2 EXERCISE 1112 How many di erent isomorphism that is bijections that pre serve adjacencies are possible from G2 to itself in Example 1101 EXERCISE 1113 There are 14 nonisomorphic pseudographs with 3 vertices and 3 edges Draw all of them EXERCISE 1114 Draw all nonisomorphic simple graphs with 6 vertices 5 edges and no cycles EXERCISE 1115 Recall the equivalence relation on a set S of graphs given by G1 is related to G2 if and only if G1 2 G2 How many equivalence classes are there ifS is the set of all simple graphs with 6 vertices 5 edges and no cycles Emplain 112 Proof of Section 110 Part 3 for simple graphs PROOF Let G1 and G2 be isomorphic simple graphs having degree sequences By part 1 of Section 110 the degree sequences of G1 and G2 have the same number 1 INTRODUCTION TO GRAPHS AND GRAPH ISOMORPHISM 69 of elements nite or in nite Let f VG1 a VG2 be an isomorphism and let i E VG1 We claim degGo degG2fi If we show this then f de nes a bijection between the vertices of G1 and G2 that maps vertices to vertices of the same degree This will imply the degree sequences are the same Proof of claim Suppose d69011 h Then there are k vertices adjacent to i say u1u2 uk The isomorphism maps each of the vertices to h distinct ver tices adjacent to fu in G2 since the isomorphism is a bijection and preserves adja cency Moreover fu will not be adjacent to any vertices other than the k vertices fu1fu2fuk Otherwise u would be adjacent to the preimage of such a vertex and this preimage would not be one of the vertices u1u2 uk since f is an isomorphism This would contradict that the degree of u is k This shows the degree of fu in G2 must be h as well proving our claim D EXERCISE 1121 Prove the remaining properties listed in Section 110 for simple graphs using only the properties listed before each and the de nition of isomorphism 2 CONNECTIVITY 70 2 Connectivity 21 Connectivity DEFINITION 211 I A path iri a graph G V7 E is a sequertce 0f uertices 000102 1 such that plAmi is art edge ofG fori 171 The edge plAmi is art edge of the path 2 A path with n edges is said to have length n 3 A path begiririirig arid eridirig with same uertem that is 110 1 is a circuit 4 A path is simple if rio uertem or edge is repeated with the possible CLECCptiOTZ that the rst uertem is the same as the last 5 A simple path that begirts arid erids with the same uertem is a simple circuit or a cycle Discussion This section is devoted to de ning what it means for a graph to be connected and the theorems about connectivity In the de nition above we use a uertem sequertce to de ne a path We could also use an edge sequertce to de ne a path as well In fact7 in a multigraph a path may not be well de ned by a vertex sequence In this case an edge sequence must be used to clearly de ne a path A circuit must begin and end at the same vertex7 but this is the only requirement for a circuit A path that goes up one vertex and then right back is a circuit Our de nition of a simple path may be different than that found in some texts some writers merely require that the same edge not be traversed more than once ln addition7 our de nition of a simple circuit does not include the circuit that goes up an edge and travels back by the same edge Some authors also allow the possibility of a path having length 0 the path consists of a single vertex and no edges We will require that paths have length at least 1 Notice that a path must also be nite It is possible for a graph to have in nitely many vertices andor edges and one could also imagine a kind of path with in nitely many edges but our de nition of a path requires the path be nite 22 Example 221 EXAMPLE 221 Let G1 be the graph below 2 CONNECTIVITY 71 V1 V2 V3 V5 V4 1 01704702703 is a simple path of length 3from pl to 113 2 01714 04112 112113 is the edge sequence that describes the same path in part 1 3 0170570470170203 is a path of length 5from pl to 113 4 1110511401 is a simple circuit of length 3 5 U1ygygy4y2y5yl is a circuit of length 6 but it is not simple Discussion This example gives a variety of paths and Circuits You can certainly come up with many more EXERCISE 221 In this eacercise consider two cycles di erent if they begin at a di erent uertem andor if they trauerse uertices in a di erent direction Eccplain your answer a How many di erent cycles are there in the graph K4 b How many di erent circuits are there in the graph K4 EXERCISE 222 In this eacercise consider two cycles di erent if they begin at a di erent uertem andor if they trauerse uertices in a di erent direction How many di erent cycles are there in the graph Kn where n is some integer greater than 2 EXERCISE 223 Uses combinations from counting principles In this eccercise consider two cycles are the same if they begin at a di erent uertem andor if they trauerse uertices in a di erent direction but they use the same uertices and edges Eccplain your answer a How many di erent cycles are there in the graph K4 b How many di erent circuits are there in the graph K4 2 CONNECTIVITY 72 EXERCISE 224 Uses combinations from counting principles In this eccercise consider two cycles are the same if they begin at a di erent vertem andor if they traverse vertices in a di erent direction but they use the same vertices and edges How many di erent cycles are there in the graph Kn where n is some integer greater than 2 EXERCISE 225 Prove a nite graph with all vertices of degree at least 2 contains a cycle EXERCISE 226 Prove a graph with n vertices and at least n edges contains a cycle for all positive integers n You may use Epercise 225 23 Connectedness DEFINITION 231 A simple graph is connected if there is a path between every pair of distinct vertices Discussion When looking at a sketch of a graph just look to see if each vertex is connected to each of the other vertices by a path If so7 this graph would be connected If it has two or more distinct pieces with no edge connecting them then it is disconnected 24 Examples EXAMPLE 241 This graph is connected V1 V2 V5 V4 EXAMPLE 242 2 CONNECTIVITY 73 This graph is not connected V1 V2 o o V5 V3 V5 V4 EXAMPLE 243 The following graph is also not connected There is no edge between Us and any of the other vertices V1 V2 5 V5 V4 25 Theorem 251 THEOREM 251 There is a simple path between every pair of distinct vertices in a connected graph PROOF Suppose u and i are arbitrary7 distinct vertices in a connected graph7 G Because the graph is connected there is a path between it and 1 Among all paths between it and i choose a path it 110111 mm i of shortest length That is7 there are no paths in G of length lt n Suppose this path contains a circuit starting and ending with7 say7 1 This circuit must use at least one edge of the path hence7 after removing the circuit we will have a path from u to i of length lt n7 contradicting the minimality of our initial path D 2 CONNECTIVITY 74 Discussion Theorem 251 implies that if we need a path between two vertices in a connected graph we may use a simple path This really simpli es no pun intended the types of paths we need to consider when examining properties of connected graphs Certainly there are many paths that are not simple between any two vertices in a connected graph7 but this theorem guarantees there are nicer paths to work with 26 Example 261 V1 V2 V5 V4 EXAMPLE 261 The path o1o5o4o1o2o3 is apath between o1 andog However 111115114111 is a circuit Remove the circuit except the endpoint to get from the original path 111112113 This is still a path between U1 and 113 but this one is simple There are no edges in this last path that are used more than one time Discussion In many examples it is possible to nd more than one circuit that could be removed to create a simple path Depending on which circuit is chosen there may be more than one simple path between two given vertices Let us use the same graph in Example 2617 but consider the path o17o27o5o1o4o2 We could either remove the circuit 111112115111 or the circuit o2o5o1o4o2 If we removed the rst we would be left with ohmwg while if we removed the latter we would get 11112 Both of these are parts of the original path between U1 and 112 that are simple 2 7 Connect ed Component DEFINITION 271 The maccimally connected subgraphs ofG are called the con nected components or just the components 2 CONNECTIVITY 75 Discussion Another way we could express the de nition of a component of G is A is a component of G if 1 A is a connected subgraph of G and 2 if B is another subgraph of G containing A then either B A or B is disconnected 28 Example 281 EXAMPLE 281 In the graph below the vertiees 116 and 113 are in one component while the vertiees o1o2o4 and 115 are in the other component V1 V2 o o V5 V3 V5 V4 If we looked at just one of the components and consider it as a graph by itself7 it would be a connected graph If we try to add any more from the original graph7 however7 we no longer have a connected graph This is what we mean by largest Here are pictures that may help in understanding the components of the graph in Example 281 2 CONNECTIVITY 76 V1 V2 V5 V4 Above is a connected component of the original graph V1 V2 v5 v4 Above is not a connected component of the original We are missing an edge that should have been in the component 29 Cut Vertex and Edge DEFINITION 291 I If one can remove a vertep and all incident edges from a graph and produce a graph with more components than the original graph then the vertep that was removed is called a cut vertex or an articulation point 2 If one can remove an edge from a graph and create more components than the original graph then the edge that was removed is called a cut edge or bridge 2 CONNECTIVITY 77 Note When removing a vertex7 you must remove all the edges with that vertex as an endpoint When removing an edge we do not remove any of the vertices Remember7 edges depend on vertices7 but vertices may stand alone EXERCISE 291 Prove that every connected graph has at least two non cut ver tices Hintx Use the second principle of mathematical induction on the number of vertices EXERCISE 292 Prove that if a simple connected graph has eccactly two non cut vertices then the graph is a simple path between these two non cut vertices Hintx Use induction on the number of vertices and Eccercise 291 210 Examples EXAMPLE 2101 There are no cut vertices nor cut edges in the following graph V1 v2 v5 v4 EXAMPLE 2102 v2 and 114 are cut vertices e1 eg and e5 are cut edges in the following graph 2 CONNECTIVITY 78 Discussion EXERCISE 2101 In each case nd how many cut edges and how many cut yer tices there are for each integer n for which the graph is de ned 1 Star Network 2 Cycle 3 Complete Graphs 211 Counting Edges THEOREM 2111 A connected graph with n vertices has at least n 7 1 edges Discussion Notice the Theorem states there are at least n 7 1 edges7 not exactly n 7 1 edges In a proof of this theorem we should be careful not to assume equality lnduction is the natural choice for a proof of this statement7 but we need to be cautious of how we form the induction step Recall in the induction step we must show that a connected graph with n 1 vertices has at least n edges if we know every connected graph with n vertices has at least n 7 1 edges It may seem like a good idea to begin with an arbitrary graph with n vertices and add a vertex and edges to get one with n1 vertices However7 the graph with n 1 vertices would depend on the one we started with We want to make sure we have covered every possible connected graph with n 1 vertices7 so we would have to prove every connected graph with n 1 vertices may be obtained this way to approach the proof this way On the other hand7 if we begin with an arbitrary graph with n 1 vertices and remove some vertex and adjacent edges to create a graph with n vertices the result may no longer be connected and we have to consider this possibility The proof of this theorem is a graded exercise 212 Connectedness in Directed Graphs DEFINITION 2121 I A directed graph is strongly connected if there is a directed path between every pair of vertices 2 A directed graph is weakly connected if the underlying undirected graph is connected 2 CONNECTIVITY 79 Discussion Recall that the underlying graph of a directed graph is the graph obtained by eliminating all the arrows So the weakly connected means you can ignore the direc tion of the edges when looking for a path Strongly directed means you must respect the direction when looking for a path between vertices To relate this to something more familiar if you are a pedestrian you do not have to worry about the direction of one way streets This is not the case however if you are driving a car EXERCISE 2121 Are the following graphs strongly connected weakly connected both or neither a 5 V1 V2 V4 V3 213 Paths and Isomorphism THEOREM 2131 Let M be the adjacency matrip for the graph G Then the ijth entry of MT is the number ofpaths of length r from vertepi to vertepj where M7 is the standard matricc product ofM by itselfr times not the Boolean product PROOF The proof is by induction on the length of the path r Let p be the number of vertices in the graph so the adjacency matrix is p gtlt p Basis The adjacency matrix represents paths of length one by de nition so the basis step is true Induction Hypothesis Assume each entry say my in M equals the number of paths of length n from the i th vertex to the j th vertex Inductive Step Prove each entry say in ll in M my ll equals the number of paths of length n 1 from the i th vertex to the j th vertex 2 CONNECTIVITY 80 We begin by recalling Mquot1 M M and by the de nition of matrix multiplication the entry mlgl l in Mquot1 is i l l p l l n1 i n mij E mik mkj k1 where M and M By the induction hypothesis7 is the number of paths of length 71 between the 24th vertex and the k th vertex7 while mkj is the number of paths of length 1 from the k th vertex to the j th vertex Each of these paths may be combined to create paths of length n 1 from the 24th vertex to the j th vertex Using counting principles we see that the number of paths of length n 1 that go through the k th vertex just before reaching the j th vertex is mkj 1 The above sum runs from k 1 to k p which covers all the possible vertices in the graph Therefore the sum counts all the paths of length n 1 from the 24th vertex to the j the vertex 214 Example 2141 V1 V2 V5 V4 EXAMPLE 2141 The adjacency matrice for the graph above is 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 l1 1 0 1 OJ 2 CONNECTIVITY 81 We get the following powers of M M2 DMMMW MWHAgtM DHMHM MAgtHOOM WMMMM M3 qgt on NOO pwwwib 004 gtJgt N 7 The last matricc tells us there are 4 paths of length 3 between uertices 113 and 111 Find them and convince yourself there are no more Discussion It you recall that the adjacency matrix and all its powers are symmetric7 you will cut your work in half when computing powers of the matrix EXERCISE 2141 Find the pages in the tecct that covers the counting principals used in the sentence referenced as 1 in the proof of Theorem 213 Eccplain how the conclusion of this gives us the result of the sentence 215 Theorem 2151 THEOREM 2151 IfG is a disconnected graph then the compliment of G 5 is connected Discussion The usual approach prove a graph is connected is to choose two arbitrary vertices and show there is a path between them For the Theorem 2151 we need to consider the two cases where the vertices are in different components of G and where the vertices are in the same component of G EXERCISE 2151 Proue Theorem 215 EXERCISE 2152 The compliment of a connected graph may or may not be con nected Find two graphs such that the compliment is a connected and b discon nected 3 EULER AND HAMILTON PATHS 82 3 Euler and Hamilton Paths 31 Euler and Hamilton Paths DEFINITIONS 311 I Art Euler Circuit iri a graph G is a path iri G that uses every edge eccactly orice arid begiris arid erids at the same vertep 2 Art Euler path iri G is a path iri G that uses every edge emactly orice but does riot riecessarily begiri arid erid at the same vertep Discussion There are several special types of paths in graphs that we will study in this section An Euler path or circuit should use every single edge exactly one time The difference between and Euler path and Euler circuit is simply whether or not the path begins and ends at the same vertex Remember a circuit begins and ends at the same vertex If the graph is a directed graph then the path must use the edges in the direction given 32 Examples EXAMPLE 321 This graph has the Euler circuit arid herice Euler path v1 v2 3 U4 2 U4 Us 11 V3 v5 V4 EXAMPLE 322 This graph does riot have art Euler circuit but has the Euler path 2 U4 U1 2 Us 3 EULER AND HAMILTON PATHS 83 V1 V2 V3 Discussion Not all graphs have Euler circuits or Euler paths See page 5787 Example 1 G2 in the text for an example of an undirected graph that has no Euler circuit nor Euler path In a directed graph it will be less likely to have an Euler path or circuit because you must travel in the correct direction Consider7 for exarnple7 u V V3 v5 lt V4 This graph has neither an Euler circuit nor an Euler path It is impossible to cover both of the edges that travel to 113 33 Necessary and Su icient Conditions for an Euler Circuit THEOREM 331 A connected undirected multigraph has an Euler circuit if and only if each of its uertices has even degree Discussion 3 EULER AND HAMILTON PATHS 84 This is a wonderful theorem which tells us an easy way to check if an undirected connected graph has an Euler circuit or not There is an extension for Euler paths which we will soon see This theorem allows us to solve the famous Konigsberg problem The town once called Konigsberg Prussia now Kaliningrad Russia was divided by the river Pregel into parts which were connected by seven bridges as illustrated below I D l C When the people of Konigsberg would walk through the town they wondered whether they could plan their walk so that they would cross each bridge exactly once and end up at their starting point Leonhard Euler a Swiss mathematician solved the problem in the negative by discovering and proving a theorem which is essentially Theorem 331 The problem can be modelled by the multigraph below and the solution depends upon whether the graph has an Euler circuit C PROOF OF THEOREM 331 Assume G is a connected undirected multigraph with an Euler circuit The degree of any given vertex may be counted by considering this circuit since the circuit traverses every edge exactly once While traveling the circuit we move into a vertex by one edge and leave by another edge so there must be an even number of edges adjacent to each vertex Conversely if the graph G is such that every edge has an even degree then we can build an Euler circuit by the following algorithm We begin at some arbitrary vertex and travel an edge out from that vertex to another Then travel to another 3 EULER AND HAMILTON PATHS 85 vertex using an unused edge Since each vertex has even degree there will always be an unused edge to travel out if we have traveled into the vertex until we reach the beginning vertex and have used all the edges D Try your hand at the following exercise before you read further EXERCISE 331 Is it possible for the people in Konigsberg to plan a walk that crosses each bridge eccactly once and ends up in a part of town di erent from where they started That is is there an Euler path Either show that this is possible or eccplain why it is not There is another algorithrn one may use to nd an Euler circuit given a graph with all vertices of even degree The algorithm is written in pseudocode in the text7 but the general idea is to start with some arbirtary circuit which we consider the 77main circuit Now nd a circuit that uses edges not used in the main circuit but begins and ends at some vertex in the main circuit Insert this circuit into the main circuit Repeat until all edges are used 34 Necessary and Su icient Conditions for an Euler Path THEOREM 341 A connected undirected rnultigraph has an Euler path but not an Euler circuit if and only if it has emactly two vertices of odd degree Discussion Now you can determine precisely when a graph has an Euler path If the graph has an Euler circuit7 then it has an Euler path why If it does not have an Euler circuit7 then we check if there are exactly two vertices of odd degree PROOF OF THEOREM 341 Suppose G is a connected rnultigraph that does not have an Euler circuit If G has an Euler path7 we can make a new graph by adding on one edge that joins the endpoints of the Euler path If we add this edge to the Euler path we get an Euler circuit Thus there is an Euler circuit for our new graph By the previous theorern7 this implies every vertex in the new graph has even degree However7 this graph was obtained from G by adding the one edge between distinct vertices This edge added one to the degrees of these two vertices Thus in G these vertices must have odd degree and are the only vertices in G with odd degree Conversely7 suppose G has exactly two vertices with odd degree Again7 add an edge joining the vertices with odd degree The previous theorern tells us there is an Euler circuit Since it is a circuit7 we could consider the circuit as one which begins and ends at one of these vertices where the degree is odd in G Now7 remove the edge 3 EULER AND HAMILTON PATHS 86 we added earlier and we get G back and an Euler path in G 35 Hamilton Circuits DEFINITIONS 351 I A Hamilton path is a path in a graph G that passes through every uertem emactly once 2 A Hamilton circuit is a Hamilton path that is also a circuit Discussion The difference between a Hamilton path and an Euler path is the Hamilton path must pass through each uertem exactly once and we do not worry about the edges7 while an Euler path must pass through every edge exactly once and we do not worry about the vertices 36 Examples EXAMPLE 361 The circuit o1o2ogo4o5o1 is a Hamilton circuit and so apath V V3 v5 V4 too EXAMPLE 362 This graph has no Hamilton circuit but 01702703704705 is a Hamilton path VI V3 V5 V2 V4 3 EULER AND HAMILTON PATHS 87 37 Su icient Condition for a Hamilton Circuit THEOREM 371 Let G be a connected simple graph with N vertices where N 2 3 If the degree of each vertem is at least n2 then G has a Hamilton circuit Discussion Unfortunately7 there are no necessary and suf cient conditions to determine if a graph has a Hamilton circuit andor path Fortunately7 there are theorems that give suf cient conditions for the existence of a Hamilton circuit Theorem 371 above is just one example 4 INTRODUCTION TO TREES 88 4 Introduction to Trees 41 De nition of a Tree DEFINITION 411 A tree is a connected undirected graph with no simple circuits Discussion For the rest of this chapter7 unless speci ed7 a graph will be understood to be undirected and simple Recall that a simple circuit is also called a cycle A graph is acyclic if it does not contain any cycles A tree imposes two conditions on a simple graph that is be connected and acyclic 42 Examples EXAMPLE 421 The following are emamples of trees 0 Family tree 0 Filedirectory tree 0 Decision tree 0 Organizational charts Discussion You have most likely encountered examples of trees your family tree7 the directory or folder tree in your computer You have likely encountered trees in other courses as well When you covered counting principals and probability in precalculus you probably used trees to demonstrate the possible outcomes of some experiment such as a coin toss EXERCISE 421 Which of the following graphs are trees G1 G2 G3 G4 THEOREM 421 A graph is a tree i there is a unique simple path between any two of its uertices 4 INTRODUCTION TO TREES 89 PROOF Suppose T is a tree and suppose u and 1 are distinct vertices in T T is connected since it is a tree and so there is a simple path between u and 1 Suppose there are two different simple paths between u and 1 say P1u u0u1u2um 1 and P2u Uo11121n 1 Which type of proof do you think we are planning to use Since the paths are different and since P2 is a simple path P1 must contain an edge that isnt in P2 Let j 2 1 be the rst index for which the edge uj1uj of P1 is not an edge of P2 Then Uj1 074 Let uk be the rst vertex in the path P1 after Uj1 that is k 2 j that is in the path P2 Then uk w for some Z 2 j We now have two simple paths Q1 uj1 uk using edges from P1 and Q2 iii1 w using edges from P2 between Uj1 074 and uk w The paths Q1 and Q2 have no vertices in common other than the rst and last and no edges in common Thus the path from uj391 to uk along Q1 followed by the path from w to 074 along the reverse of Q2 is a simple circuit in T which contradicts the assumption that T is a tree Thus the path from u to 1 must be unique proving a tree has a unique path between any pair of vertices Conversely assume G is not a tree What kind of proof are we setting up for the reverse direction Then either a G is not connected so there is no path between some pair of vertices or b G contains a simple circuit a Suppose G is not connected Then there are two vertices u and 1 that can not be joined by a path hence by a simple path b Suppose G contains a simple circuit C 110 mm where 00 1 If n 1 then G would be a loop which is not possible since G is simple Thus we have n 2 2 But since 71 2 2 01 31 110 and so we have two different simple paths from 00 to 111 one containing the single edge 0001 and the other the part of the reverse of G from 1 110 back to 111 Thus we have proved the statement If a graph G is not a tree then either there is no simple path between some pair of vertices of G or there is more than one simple path between some pair of vertices of G77 This is the contrapositive of the statement If there is a unique simple path between any two vertices of a graph G then G is a tree77 D 4 INTRODUCTION TO TREES 90 43 Roots DEFINITION 431 A rooted tree is a tree T together with a particular yertem designated as it root Any yertem may a priori serve as the root A rooted tree provides each edge with a direction by traveling away from the root 44 Example 441 EXAMPLE 441 Consider the tree below Discussion A rooted tree has a natural direction on its edges given the root7 i an edge e Ly lies in the unique simple path from either i to z or from i to y7 but not both Say e is in the simple path from i to y Then we can direct e from x to y 45 Isomorphism of Directed Graphs DEFINITION 451 Let G and H be a directed graphs G and H are isomorphic if there is a bijection f VG a VH such that ui is an edge in G if and only if u7 fi is an edge in H We call the map f and isomorphism and write G 2 H 4 INTRODUCTION TO TREES 91 Discussion Notice the notation for ordered pairs is used for the edges in a directed graph and that the isomorphism must preserve the direction of the edges EXERCISE 451 Let 9 be a set of directed graphs Prove that isomorphism of directed graphs de ries ari equivalence relatiori oh 9 46 Isomorphism of Rooted Trees DEFINITION 461 Rooted trees T1 arid T2 are isomorphic if they are isomorphic as directed graphs Discussion EXERCISE 461 Give ari eccample of rooted trees that are isomorphic as uridi rected simple graphs but riot isomorphic as rooted trees EXERCISE 462 How mariy di ererit isomorphism types are there of a trees with four vertices b rooted trees with four vertices 47 Terminology for Rooted Trees DEFINITION 471 1 Ife uv is a directed edge theri u is the parent ofv aridv is the child ofu The root has rio parerit arid some of the vertices do riot have a child 2 The vertices with rio childreri are called the leaves of the rooted tree 3 If two vertices have the same parerit they are siblings 4 If there is a directed simple path from u to v theri u is art ancestor ofv aridv is a descendant of u 5 Vertices that have childreri are internal vertices Discussion Much of the terminology you see on this slide comes directly from a family tree There are a few exceptions For example on a family tree you probably would not say cousin Freddy who has never had kids is a leaf 4 INTRODUCTION TO TREES 92 48 m ary Tree DEFINITION 481 1 Ah m ary tree is one in which every internal veitem has no more than in children 2 A full m ary tree is a tree in which every internal vertem has emaetly in children Discussion Notice the distinction between an m ary tree and a full m ary tree The rst may have fewer than in children off of some internal vertex7 but a latter must have exactly in children off of each internal vertex A full m ary tree is always an m ary tree More generally7 if h S m then every k ary tree is also an m ary tree Caution terminology regarding m ary trees differs arnong authors 49 Counting the Elements in a Tree THEOREM 491 A tree with n vertices has n 7 1 edges THEOREM 492 A full m ary tree withi internal veitiees has n mi 1 veitiees If afull m ary tree has n veitiees i ihtemal vertices and L leaves then a i n 71m b L 711m e Lim711 d n 7 mm 71mm 71 e 239 7 L 71mm 71 161 Discussion PROOF OF THEOREM 491 Select a root v and direct the edges away from v Then there are as many edges as there are terrninal vertices of the edges and every vertex except v is a terminal vertex of some edge PROOF OF THEOREM 492 PART 1 Every internal vertex hasmchildren hence7 there are mi children Only the root is not counted7 since it is the only vertex that is not a child EXERCISE 491 Prove Theorem 492 Part 2 Hihtx What is L i N 316 1 16 4 INTRODUCTION TO TREES 410 Level DEFINITION 4101 The level of a veitem in a rooted tree is the length of the shortest path to the root The root has level 0 The height of a rooted tree is the madimal level of any verted A rooted tree of height h is balanced if each leaf has level h or h 7 1 Discussion EXAMPLE 4101 Consider the rooted tree below fa is the root of the tree above then the level ofb and c is Z The level ofg and h is 3 The height of the tree is 3 This is also a balanced tree since the level of every leaf is either 2 or 3 411 Number of Leaves THEOREM 4111 An m ary tree of height h has at most mh leaves COROLLARY 41111 IfT is an m ary tree with L leaves and height h then h 2 lloem L1 IfT is full and balanced then h llogm L1 Discussion Notice the at most in Theorem 4111 4 INTRODUCTION TO TREES 94 PROOF OF THEOREM 4111 We prove the theorem by induction on the height h7 h 2 0 Basis If the height of the tree is 07 then the tree consists of a single vertex7 which is also a leaf7 and m0 1 Induction hypothesis Assume any m ary tree of height h has at most mh leaves for some positive integer in Induction step Prove that an m ary tree of height h 1 has at most 77W l leaves Let T be an m ary tree of height h 17 h 2 0 Remove all the leaves of T to get a tree T T is an m ary tree of height h7 and so by the induction hypothesis it has at most mh leaves We recover T from T by adding back the deleted edges7 and there are at most in edges added to each leaf of T Thus7 T has at most in mh 77W l leaves7 since no leaf of T is a leaf of T By the principle of mathematical induction any m ary tree with height h has at most mh leaves for any positive integers in and h D EXERCISE 4111 Prove Corollary 41111 412 Characterizations of a Tree THEOREM 4121 Let G be a graph with at least two vertices Then the following statements are equivalent 1 G is a tree 2 For each pair of distinct vertices in G there is a unique simple path between the vertices 3 G is connected but if one edge is removed the resulting graph is disconnected 4 G is acyclic but if an edge is added between two vertices in G the resulting graph contains a cycle 5 G is connected and the number of edges is one less than the number of vertices 6 G is acyclic and the number of edges is one less than the number of vertices Discussion Theorem 4121 gives us many different tools for recognizing trees Once we prove this Theorem7 it is enough to prove a graph satis es any one of the statements to show the graph is a tree Equivalently we could show a graph fails to satisfy any of the conditions to show it is not a tree 4 INTRODUCTION TO TREES 95 The equivalence 1 gt2 is actually Theorem 421 which we have already proven The equivalence 1 gt3 will be part of your graded assignment PROOF 14 First we show 1 4 Let G be a tree with at least two vertices By the de nition of a tree G is acyclic7 so what we must show is if an edge is added between two vertices of G then resulting graph contains a cycle Let u and o be two vertices in G and add an edge7 e7 between these vertices Let G be the resulting graph Note that G is not necessarily sirnple By part 2 of this Theorern there must be a unique sirnple path between 1 and u in G Let e17e27e37 7ek be the edge sequence de ning this path The edge sequence e17 e27 e37 7 ek7 e will de ne a path from o to itself in G Moreover7 this is a simple circuit since e17e27e37 7ek de ned a simple path in G and e is not an edge in G This shows G contains a cycle Now we show 4 1 Let G be an acyclic sirnple graph that satis es the property given in part 4 of Theorem 4121 Since we already know G is acyclic7 what we need to show to complete the proof that G is a tree is that it is connected To show a graph is connected we show two arbitrary vertices are connected by a path in G Let u and o be vertices in G Add an edge7 e u7o7 to G and call the resulting graph G By our assurnption7 there must be a cycle in G now In fact7 the edge e must be part of the cycle because without this edge we would not have a cycle Suppose e7 e17 e27 7 ek is the cycle that begins and ends at u Notice that k must be at least 1 for this edges sequence to de ne a cycle Moreover7 the edge sequence e17 e27 7 ek de nes a path between 1 and u in G since all of these edges must be in G This shows G is connected and so is a tree EXERCISE 4121 Prove Z gt5 in Theorem 412 EXERCISE 4122 Prove Z gt6 in Theorem 412 5 SPANNING TREES 96 5 Spanning Trees 51 Spanning Trees DEFINITION 511 Given a connected graph G a connected subgraph that is both a tree and contains all the vertices ofG is called a spanning tree for G Discussion Given a connected graph G one is often interested in constructing a connected subgraph7 which contains all of the vertices of G but has as few the edges of G as possible For example7 one might wish to nd a minimal graph in a connected circuit in which each pair of nodes is connected Such a subgraph will be a spanning tree for G As we will soon see7 if G is not already a tree7 then it will have more than one spanning tree 52 Example 521 EXAMPLE 521 In the gure below we have a graph drawn in red and black and a spanning tree of the graph in red Discussion The spanning tree of a graph is not unique EXERCISE 521 Find at least two other spanning trees of the graph given in Example 52 5 SPANNING TREES 97 53 Example 531 EXAMPLE 531 K5 has 3 nonisornorphic spanning trees Discussion The three nonisornorphic spanning trees would have the following characteristics One would have 3 vertices of degree 2 and 2 of degree 1 another spanning tree would have one vertex of degree three and the third spanning tree would have one vertex of degree four There are more than 3 spanning trees but any other will be isomorphic to one of these three EXERCISE 531 How many nonisomorphic unrooted spanning trees are there of the graph in Example 52 54 Existence THEOREM 541 A graph is connected if and only if it has a spanning tree Discussion One of the key points of Theorem 541 is that any connected graph has a spanning tree A spanning tree of a connected graph can be found by removing any edge that forms a simple circuit and continuing until no such edge exists This algorithm turns out to be very inef cient however since it would be time consuming to look for circuits each time we wish to consider removing an edge There are two recursive algorithms the depth rst search and the breadth rst search algorithms that are fairly ef cient but we will not discuss them here since they will be covered in depth in your computer science courses PROOF OF THEOREM 541 First we let G be a graph that contains a spanning tree T Let u and i be vertices in G Since T is a spanning tree of G u and i are also vertices in T Now T is a tree so it is connected Thus there is a path from u to i in T T is by de nition of a spanning tree a subgraph of G so the path in T from u to i is also a path in G Since u and i were arbitrary vertices in G we see that G is connected Conversely we assume G is a connected graph Notice that if G is not simple we may remove all loops and all but one edge between any pair of vertices that has more than one edge between them and the resulting graph will be a simple connected graph Thus we may assume without loss of generality that G is simple Let n If G has fewer than n 7 1 edges then it would not be connected as a result of an exercise in Connectivity thus 2 n71 Also from Introduction 5 SPANNING TREES 98 to Trees we recall that G is a tree if and only if n 7 1 so we assume G has at least n 7 1 edges say n 71 k We will prove that a connected graph with n vertices and n71k edges contains a spanning tree by induction on k h 2 0 Basis Step h 0 Then G is already a tree by our observation above Induction Step Assume that every connected graph with n vertices and n 7 1 h edges h 2 0 contains a spanning tree Suppose G is a connected graph with n vertices and n 7 1 k 1 edges Since gt n 7 1 G is not a tree so there must be a simple circuit in G Removing any edge from this circuit will result in a connected subgraph G1 of G with the same vertex set and n 7 1 h edges By our induction hypothesis G1 contains a spanning tree But since G1 is a subgraph of G containing all of the vertices of G any spanning tree of G1 is a spanning tree of G Thus G contains a spanning tree Therefore by the principle of mathematical induction every simple con nected graph contains a spanning tree D This proof can be used as a basis of a recursive algorithm for constructing spanning trees It is however nothing more than the inef cient algorithm we alluded to above COROLLARY 5411 A connected subgraph ofG that has the minimum number of edges and still contains all the vertices ofG must be a spanning tree for G Moreover a spanning tree of a graph with n vertices must have emactly n 7 1 edges 55 Spanning Forest DEFINITION 551 A spanning forest of a graph G is the union of a collection of one spanning tree from each connected component of G THEOREM 551 Every nite simple graph has a spanning forest Discussion A graph that is not connected does not have a spanning tree It does however have a spanning forest EXERCISE 551 Prove Theorem 551 5 SPANNING TREES 99 56 Distance DEFINITION 561 Let T1 and T2 be spanning trees of the graph G The distance dT1T2 between T1 and T2 is the number of edges in ET1 EB ET2 That is dT17T2 lET1 EB ET2 Discussion Recall the notation 69 from sets is the symmetric difference of two sets A 69 B A U B 7 A B Consider the spanning tree in Example 521 It is possible to nd another span ning tree of the given graph by removing one edge from the given spanning tree and adding an edge not already in use See Exercise 564 below The distance between this new spanning tree and the old one is 2 since there is 1 edge in the rst that is not in the second and one edge in the second that is not in the rst EXERCISE 561 What is the parity of the distance between any two spanning trees of a graph G Emplain Parity is even or odd EXERCISE 562 Prove that if A B and G are arbitrary nite sets then lA Gl 2 lA BllB Gl 7lBl Hintx IfX andY are nites sets 1X UYl le 1Y1 7 1X YU EXERCISE 563 This one is in your homework Do not post the solution on the discussion board Prove that if T1 T2 and T3 are spanning trees of a simple connected graph G then dT1 T3 3 dT1T2 dT2 T3 Hintx First reduce the inequality to the one in Epercise 562 EXERCISE 564 Suppose T and T are spanning trees of a simple connected graph G and T 31 T Prove that there is an edge e in T that is not in T and an edge e in T that is not in T such that if we remove e from T and then add e to T 7 e the resulting subgraph T ofG is a spanning tree Hintx First show that T U T is a connected subgraph of G that is not a tree EXERCISE 565 In Epercise 564 what is the relationship between dT T and dT T EXERCISE 566 Prove that ifT and T are spanning trees of a simple connected graph G and T 31 T then there are spanning trees T0T1T2 Tk of G h 2 1 such that a T1 T 5 SPANNING TREES 100 b Tk T and c dTl1Ti 27f0ri1h Hintx Use induction on n where dTT 2n and Eaercise 564 EXERCISE 567 Prove that if TT1T27 Tk are are spanning trees of a simple connected graph G h 2 0 such that dTl1Ti 27 fori 17 k then dTOTk 3 2k 6 SEARCH AND DECISION TREES 101 6 Search and Decision Trees 61 Binary Tree DEFINITION 611 A binary tree is a rooted 2 ary tree In a binary tree a child of a parent may be designated as a left child or a right child but each parent has at most one of each The rooted subtree consisting of the right left child of a vertem and all of its descendants is the right left subtree at that verted A binary tree is often called a binary search tree Discussion A binary tree is a rooted tree in which we may impose additional structure namely7 the designation of each child of a vertex as either a left or right child This designation may be fairly arbitrary in general7 although it may be natural in a particular appli cation A tree could be drawn with the left and right subtrees of a vertex reversed7 so it may be unclear which is the left and right without a sketch of the tree or a clear designation from the beginning If a tree has been sketched in the plane with the root at the top and the children of a vertex below the vertex7 then the designation of left or right child should be inferred naturally from the sketch EXERCISE 611 For the binary tree below identify left and right children and sketch the left and right subtrees of each vertem other than the leaves a The tree shown above could have been drawn with the vertices b and c and their subtrees reversed The resulting tree would be isomorphic to the original as rooted trees7 but the isomorphism would not preserve the additional structure The point is that the left and right descendents are not preserved under an isomorphism of rooted trees 6 SEARCH AND DECISION TREES 102 Searching items in a list can often be accomplished with the aid of a binary search tree For example suppose we are given a list of elements X1 X2 X from an ordered set S lt but the elements are not necessarily listed according to their preferred ordering We can establish a recursive procedure for constructing a binary search tree with vertices labeled or keyed by the elements of the list as demonstrated by Example 621 This tree will allow us to search ef ciently for any particular item in the list 62 Example 621 EXAMPLE 621 Suppose X1X2 Xn are elements from an ordered set S lt Form a binary search tree recursively as follows I M Let X1 be the label or key for the root 2 Recursion Assume we have constructed a binary search tree with vertices keyed by X1X 1 S i lt n Starting with the root keyed X1 compare X L with the keys of the vertices already in the tree moving to the left if the vertem key is greater than X L and to the right otherwise We eventually reach a leaf with key X for some j between 1 and i We add a vertem with key X L and edge XjXi1 and designate X L to be either a left child of Xj lei1 lt Xj 07quot a OfXj lt Xi1 Discussion The main characteristic of the binary search tree constructed is that the key of any vertex is greater than the key of any vertex in its left subtree and is less than the key of any vertex in its right subtree EXAMPLE 622 Construct a binary search tree with vertices keyed by the names in the list Jones Paceco Hebert Howard Russo Coke Brown Smithe Randall using alphabetical order Solution Jones Brown Randall Smithe 6 SEARCH AND DECISION TREES 103 Discussion Example 622 is one in which we have assigned the vertices keys from a list of names ordered alphabetically Notice that if we rearrange the list of names say Howard Paceco Jones Hebert Russo Coke Brown Randall Smithe we might get a different tree 63 Decision Tree DEFINITION 631 A decision tree is a rooted tree in which each internal vertep corresponds to a decision and the leaves correspond to the possible outcomes deter mined by a sequence of decisions a path Discussion Decision trees may be used to determine the complexity of a problem or an algo rithm Notice that a decision tree need not be a binary tree 64 Example 641 EXAMPLE 641 Has been featured as a puzzler on Car Talk Suppose you are given a collection of identical looking coins and told one of them is counterfeit The counterfeit coin does not weigh the same as the real coins You may or may not be told the counterfeit coin is heavier or lighter The only tool you have to determine which is counterfeit is a balance scale What is the fewest number of weighings required to nd the counterfeit coin Your answer does depend on the number of coins you are given and whether or not you are told the counterfeit is heavier or lighter than the rest Solution The solution will be obtained by a sequence of weighings as follows 6 SEARCH AND DECISION TREES 104 0 Choose two subsets of the coins of equal number and compare them on the balance 0 There are three possibilities one of the two sets of coins weighs more than less than or is the same as the other set of coins 0 Depending on the outcome of the rst weighing choose another two subsets of the coins and compare them 0 This problem can be modeled with a ternary 3 ary tree where an internal vertex corresponds to a weighing and edge corresponds to an outcome of that weighing and a leaf corresponds to a coin found to be counterfeit In order to determine the minimal number of weighings for a given problem you must be clever in choosing the sets of coins to weigh in order not to require any redundant comparisons Discussion Just think you could have won a t shirt from Car Talk if you had known about this EXAMPLE 642 Suppose there are 8 coins 12345 678 and you know the counterfeit coin is lighter than the rest Solution Use a ternary tree to indicate the possible weighings and their outcomes A uertem labeled with the notation a b 7 L stands for the act of comparing the set of coins a b to L An edge from that yertep will have one of the labels L or H depending on whether the rst of the two sets is lighter than equal in weight to or heavier than the second set 1 23456 1 3 2 7 8 4 6 5 With careful choices of the sets we see that only two weighings are necessary Notice there is a leaffor every possible outcome that is one for each coin It is not di cult but perhaps tedious to see that we cannot get by with only one weighing You would have to argue cases This problem was made a bit easier since we knew the counterfeit coin is lighter 6 SEARCH AND DECISION TREES 105 EXERCISE 641 In the eccarnple above how many weighings are necessary if you don t know whether the counterfeit is lighter or heaver Notice that in this case there would be 16 leaves 7 TREE TRAVERSAL 106 7 Tree Traversal 71 Ordered Trees DEFINITION 711 Ari ordered tree is a rooted tree iri which the set of childreri of each vertem is assigried a total order rt a drawing of art ordered rooted tree with the root shown at the top the childreri of a vertem are shown from left to right Discussion The concept of an ordered tree in some way generalizes the idea of a binary tree in which children of a vertex have been designated as left or right7 if we think of the left child of a vertex as being less than77 the right child The analogy only breaks down for binary trees that are not complete7 however7 since some vertex may have only a left child7 whereas another may only have a right child 72 Universal Address System DEFINITION 721 The set of vertices of art ordered tree T cart be provided with a total order called a universal address system usirig the following recursive process Basis Label the root 0 arid label the n childreri of the root 127 n from left to right Recursion Giveri a vertem v with label L at level Is 2 1 label its childreri L1L27 Lnv from left to right Totally order the vertices ofT usirig the ledicographic orderirig Discussion EXAMPLE 721 The following table gives the uriiversal address system arid the resultirig orderirig of the vertices for the ordered tree shown below a lt b lt e lt f lt c lt 9 0 lt 1 lt 11 lt 12 lt 2 lt 21 g lt h lt i39 lt d lt j lt k lt l 21 lt 22 lt 23 lt 3 lt 31 lt 32 lt 33 7 TREE TRAVERSAL 107 ll e fghijkl 73 Tree Traversal Suppose we have information stored in an ordered rooted tree How do we recover information from the tree That is7 how do we visit the vertices in the tree We shall look at several procedures for visiting7 or listing7 the vertices of the tree Each procedure is de ned recursively on the subtrees7 and each is based on a path that proceeds to the leftmost child of a vertex that has not occurred in the path before moving to a vertex to the right These algorithms only differ as to when the root of a subtree is visited or listed relative to the vertices of its subtrees DEFINITION 731 A procedure used to systematically visit each vertem in a tree is called a traversal algorithm or a traversal Notice that a subtree of T that does not include the root must have fewer vertices Therefore7 the recursive de nition makes sense Just keep applying the recursion step until you get to the leaves Once you are down to a subtree that consists only of a leaf apply the basis step 7 4 Preorder Traversal DEFINITION 741 The preorder traversal of a rooted tree T with n vertices is de ned recursively as follows Basis Ifn 1 then the root is the only UCT tECE so we visit the root Recursive Step When n gt 1 consider the subtrees T 17T2T37 Tk of T whose roots are all the children of the root of T Visit each of these subtrees from left to right Discussion EXAMPLE 741 In the Preorder Traversal of the the vertices in the following tree the vertices are visited in the following order a b d h i c e f j k g 7 TREE TRAVERSAL 108 To begin nding the preorder traversal we begin with 1 Next nd the preorder traversal for the subtree b T1 List that traversal and then nd and list the prerorder traversal for the subtree C k Now to nd the preorder traversal of the subtree7 T1 we start with b and nd the preorder traversal of 7 TREE TRAVERSAL 109 S1 d h i The preorder traversal of this one is d h i The basis step was nally used to nd the preorder traversal of st subtrees The preorder traversal of T2 still needs to be found It is e e f j k 9 By putting all the vertices together in the order in which they were listed we get the preorder traversal a b d h i e e f j k 9 One recommendation is to take the original graph and point to each vertex in the order listed in the preorder traversal to help coordinate the order they are given in the list to their place in the tree Notice that if a tree is ordered using the universal address system7 then a listing of the vertices in increasing77 order is a preorder traversal of the tree 7 5 Inorder Traversal DEFINITION 751 In an inorder traversal of a tree the root of a tree or subtree is visited after the vertices of the leftmost subtree but before the vertices of all other subtrees Note that in the inorder traversal7 if a vertex7 v7 has multiple subtrees originating from it v is placed between the vertices of the leftmost subtree and the vertices of all the other subtrees EXERCISE 751 Give a careful recursive de nition of an inorder traversal EXAMPLE 751 The inorder traversal of this tree below is h d i b a e e k j 1 g 7 TREE TRAVERSAL 110 EXAMPLE 752 Here is another example to look at Again point to each vertem in the order it is listed to develop an understanding of the relationship between inorder traversal and the graph a The inorder traversal is b a e e f g d 76 Postorder Traversal DEFINITION 761 In a postorder traversal ofa tree the root ofa treesubtree is visited after all of the vertiees of its subtrees are visited EXAMPLE 761 The postorder traversal 0f the tree below is h i d b e k j f g C a 7 TREE TRAVERSAL 111 Discussion The postorder traversal is when the root of a subtree is Visited after all its vertices have been Visited EXAMPLE 762 We can nd the postorder traversal of the tree a Postorder Traversal b e f g c d a EXERCISE 761 Give a careful recursive de nition of an postorder traversal 77 In x Form DEFINITIONS 771 I A fully parenthesized ELEPTCSSlOTZ is in in x form 2 The ELEPTCSSlOTZ obtained by traversing the ordered rooted tree by pre d tra versal is pre x form or Polish notation 3 The ELEPTCSSlOTZ obtained by traversing the ordered rooted tree by pOSt CE tra versal is post x form or reverse Polish notation EXAMPLE 771 z 2 3z 7 y M 4 I Find the in d form 2 Draw the rooted tree for the algebraic eccpression 3 Find the pre d form 4 Find the pOSt CE form Solutions 1 The in d form is 3 95 7 11 W 20134 7 TREE TRAVERSAL 112 2 The rooted tree for the algebraic espressizm is 3 The pre s form is gtk37zyTzy24 4 The post s form is 3y7gtkzy2T4 Discussion An algebraic representation consists of a nite number of 0 variables and numbers 0 binary operations addition subtraction 7 multiplication division exponentiation T Pay attention to the fact that the symbol T is used for exponentiation in this material For example 23 2 T 3 In these notes we de ne the in x pre x and post x forms of an algebraic ex pression and give an example The tree referred to in example 771 is found as follows A binary ordered tree can be built having internal vertices labeled by the opera tors and leaves labeled by the variables and numbers We start from the innermost expressions and work our way outward constructing subtrees from the innermost ex pressions These are joined together to form larger subtrees using the operations that join the innermost expressions The ihorder listing ofthe vertices then reproduces the 7 TREE TRAVERSAL 113 expression provided the parentheses are inserted as follows as you begin to traverse a subtree from an internal vertex operation insert an open parenthesis as you leave the subtree insert a closed parenthesis Pre x and post x notation can be found from the tree Notice that the pre x and post x notations do not require parenthesis A algebraic expression in pre x or post x notation is unambiguous ln x form requires parentheses7 however7 in order to resolve ambiguities Despite this fact7 in x notation is pretty much the universally accepted form for writing algebraic expressions We have adopted a convention7 so well known that we take it for granted7 that allows us to reduce7 but not eliminate7 the number of parentheses needed without creating ambiguities Namely7 we agree that7 in the absence of parentheses7 the binary operations are performed in the following order exponentiation7 multiplication7 division7 addition7 subtraction EXERCISE 771 Find the pTC CE and post d forms for the algebraic CCEPTESSlOTZS 0 b CdT3 and a b Cd T3 EXAMPLE 772 Find the in d form of the CCEPTCSSlOTZ given in pTC CE form 7Tzy5gtk2xy3 Solution 1Tzy52zy3 2Tzy529cy3 37 T 9695296y3 of T x y 5 2zy 3 57 T 96 y 5 296y 3 67 T 96 y 5 296y3 77 T 96 y 5 2y3 87 T 96y 5 2y3 97 T 59 5 2y3 10 96yT5 2y3 11 96yT5 2y3 12 96y T5 7 2 96y3 To go from pre x form to in x form7 we read the expression right from left Look for the rightmost operation and the variables or numbers immediately to the right of it Put parenthesis around these and change to in x notation Move to the next right most operation and put parenthesis around it and the expressions just to the right of it Change to in x notation7 and so on EXAMPLE 773 Find the value of the post co CCEPTCSSlOTZ 62T9723T5 Solution 7 TREE TRAVERSAL 114 162l9 23l5 7 2 7 2629 3T5 3369723T5 4369723i5 5369723 i 5 64723T5 74785 84785 This time we look for the left most operation and the numbers immediately to the left of it The exact same procedures may be applied to logical expressions as well as set operation expressions EXAMPLE 774 Given the logical CCEPTCSSiOTZ p V q a r Z Find the in m notation 2 Represent using an ordered rooted tree 3 Find the preorder form 4 Find the postorder form Solution 1 IN 11 r 2 Tree 3 Preorder a Vp q r 4 Postorder pq V r a CHAPTER 3 Boolean Algebra 1 Boolean Functions 11 Boolean Functions DEFINITIONS 111 1 A Boolean variable is a variable that may take on values only from the set B 0 1 2 A Boolean function of degree n or of order n is a function with domain B dlwg E B and codomain B In other words Boolean functions of degree n are functions of the form F B a B 3 Two Boolean functions F and G are equivalent if Fx12d3 7x Gz1x23 7an for every ordered n tuple 17 2 3 7x 6 B Discussion We have already encountered Boolean variables7 namely7 propositional variables7 which must have value 1 true or 0 false Indeed7 the propositional calculus is the motivating concept for the material in this chapter7 and we shall refer to it frequently 12 Example 121 EXAMPLE 121 A Boolean function of degree 2 Fzy B2 a B may be de ned by a chart For edample this function may be de ned as follows 115 1 BOOLEAN FUNCTIONS 116 Discussion There are several ways we may de ne a Boolean function A table of values is one way After we de ne addition multiplication and other operations on B we may also use these operations to de ne functions Notice a Boolean function of two variables must assign to each of the four ordered pairs a value from B This means there are 24 16 different Boolean functions of order 2 EXERCISE 121 Use a table of values to de ne all 16 Boolean functions of order 2 EXERCISE 122 How many Boolean functions of degree n are there 13 Binary Operations DEFINITIONS 131 Let zy e B 1 Addition is de ned by the table z y zy 1 1 1 1 1 QQN QNQ U ication is de ned by the table y 2 Multi C QQNNZ Z QNQN Q QQN U 3 The compliment is de ned by the table Discussion If you think of the 1 as true and the 0 as false as we used in Logic you should notice that Boolean addition corresponds to the logical or Boolean multiplication corresponds to the logical and and complementation corresponds to the logical not In fact many authors use the notation V A and n for and 7 respec tively The notation E x is another common alternative for complimentation We 1 BOOLEAN FUNCTIONS 117 will use this alternative on the discussion board and it may be used in homework When there would be no confusion7 we drop the when denoting a Boolean product7 just as is done is algebra Notice that Boolean addition de ned here on 01 is NOT the same as the addition on the set of integers modulo 2 14 Example 141 EXAMPLE 141 The following functions are equivalent HFwy 2 GYM xi 2y xi PROOF We show the two functions have the same values for every possible or dered pair in B2 z y xy E Ey x17 xyzyz xy 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 D Discussion Example 141 gives an example of equivalent functions that are de ned quite differently7 although both representations are in terms of the algebra we have de ned on 07 1 15 Boolean Identities Below is a table of the Boolean ldentities you should know 1 BOOLEAN FUNCTIONS 118 ldentity Name i z Law of Double Complement z z z and z z z ldempotent Laws z 0 z and z 1 z ldentity Laws z 1 1 and z 0 0 Dominance Laws z y y z zy yz y2yz 96W 96W yz y2 yz xyxz x 39y E 5 DeMorgan7s Laws Commutative Laws Associative Laws Distributive Laws Discussion The distributive law for addition over multiplication and the DeMorgan7s Laws may seem somewhat unusual to you at this stage since they have no counterpart in the operations of addition and multiplication used in our familiar number systems Indeed you should avoid any analogies with ordinary arithmetic and instead use the propositional calculus as your model whenever you feel the need to use a familiar setting in which to exemplify these or any other properties you might encounter EXERCISE 151 Verify the distributive law z yz x 16 Dual DEFINITION 161 The dual ofa Boolean CCEPTCSSlOTZ is the eapression one obtains by interchanging addition and multiplication and interchanging 0 s and 1 s The dual of the function F is denoted Fd THEOREM 161 Duality Principle IfF and G are Boolean functions such that F G then Fd Gd Discussion EXAMPLE 163 The dual of x 12 is x y E Notice that we have implicitly assumed an order of operations for a Boolean ex pression unless grouping is present to indicate otherwise complements are evaluated rst then products and then sums This order conforms to the convention we estab lished earlier for the order of operations in the predicate calculus As the example above shows you must be careful to preserve the correct order of operation when taking the dual of an expression using parentheses wherever necessary 2 REPRESENTING BOOLEAN FUNCTIONS 119 2 Representing Boolean Functions 21 Representing Boolean Functions DEFINITIONS 211 1 A literal is a Boolean variable or the complement of a Boolean variable 2 A minterm is a product of literals More speci cally if there are n variables 12 a a minterm is a product ylyg yn where y is p or ii 3 A sumof products expansion or disjunctive normal form of a Boolean function is the function written as a sum of minterms Discussion Consider a particular element say 001 in the Cartesian product B3 There is a unique Boolean product that uses each of the variables x y z or its complement but not both and has value 1 at 001 and 0 at every other element of B3 This product is Eyz This expression is called a minterm and the factors E y and z are literals This observation makes it clear that one can represent any Boolean function as a sum of products by taking Boolean sums of all minterms corresponding to the elements of B that are assigned the value 1 by the function This sum of products expansion is analogous to the disjunctive normal form of a propositional expressions discussed in Propositional Equivalences in MAD 2104 22 Example 221 EXAMPLE 221 Find the disjunctive normal form for the Boolean function F de ned by the table a y z Fpyz U U U U U U I U U I U I U I I U I U U I I U I Z Z I U U I Z I U Solution Fpy z EyE m 172 2 REPRESENTING BOOLEAN FUNCTIONS 120 Discussion The disjunctive normal form should have three rninterrns corresponding to the three triples for which F takes the value 1 Consider one of these F010 1 In order to have a product of literals that will equal 17 we need to multiply literals that have a value of 1 At the triple 010 the literals we need are E y7 and 2 since E y E 1 when x 07 y 17 and z 0 The corresponding rninterrn7 Eyi will then have value 1 at 010 and 0 at every other triple in B3 The other two rninterrns come from considering F100 1 and F101 1 The sum of these three rninterrns will have value 1 at each of 1007 0107 101 and 0 at all other triples in B3 23 Example 231 EXAMPLE 231 Simply the eppression Fpy7 z Ey 95y 172 using properties of Boolean eccpressions Solution Eyi zy 2 zyz Eyi 95732 z EyEJr zy1 EyEJr x17 Discussion Example 231 shows how we might simplify the function we found in Exam ple 221 Often surn of product expressions may be simpli ed7 but any nontrivial simpli cation will produce an expression that is not in surn of product form A sum of products form must be a sum of rninterrns and a rninterrn must have each variable or its compliment as a factor EXAMPLE 232 The following are epamples of simplifying that changes a sum of products to an eppression that is not a sum of products sum of product form zyz 95y zyz NOT sum of product form xi zyz NOT sum of product form My yz EXERCISE 231 Find the disjunctive normal form for the Boolean function G of degree 4 such that Gp1z2 3 4 0 if and only if at least 3 of the variables are 1 2 REPRESENTING BOOLEAN FUNCTIONS 121 24 Functionally Complete DEFINITION 241 A set of operations is called functionally complete if every Boolean function can be epppessed using only the operations in the set Discussion Since every Boolean function can be expressed using the operations f the set f is functionally complete The fact that every function may be written as a sum of products demonstrates that this set is functionally complete There are many other sets that are also functionally complete If we can show each of the operations in 7 can be written in terms of the operations in another set7 S then the set S is functionally complete 25 Example 251 EXAMPLE 251 Show that the set of operations 77 is functionally complete PROOF Since and 7 are already members of the set7 we only need to show that may be written in terms of and 7 Weclaim zyfy Proof of Claim Version 1 Proof of Claim Version 2 27 E g T 39 g 33917 y 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 0 D Discussion EXERCISE 251 Show that is functionally complete 2 REPRESENTING BOOLEAN FUNCTIONS 122 EXERCISE 252 Prove that the set is notfunctionally complete by showing that the function E of order I cannot be written using only z and addition and multiplication 26 NAND and NOR DEFINITIONS 261 1 The binary operation NAND denoted is de ned by the table z 9 1 1 U 1 U 1 U 1 1 U U 1 2 The binary operation NOR denoted L is de ned by the table 96 y 96 to 1 1 U 1 U U U 1 U U U 1 Discussion Notice the NAND operator may be thought of as not and77 while the NOR may be thought of as not or7 EXERCISE 261 Show that ziy W for all z andy in B 01 EXERCISE 262 Show that is functionally complete EXERCISE 263 Show that z Ly m for all z andy in B 01 EXERCISE 264 Show that is functionally complete 3 ABSTRACT BOOLEAN ALGEBRAS 123 3 Abstract Boolean Algebras 31 Abstract Boolean Algebra DEFINITION 311 An abstract Boolean algebra is de ned as a set 3 contain ing two distinct elements 0 and 1 together with binary operations and a unary operation 7 having the following properties z 0 z Identity Laws z 1 z z z 7 Compliments Laws a a zyzzyz zyzy2 zyyz xyy zltyzgtltzygtltzzgt zltyzgtltzygtltzzgt Associative Laws Commutative Laws Distributive Laws Discussion The de nition of an abstract Boolean algebra gives the axioms for an abstract Boolean algebra The unary operation 7 is called complementation Named after the English mathematician George Boole 1815 18647 Boolean algebras are especially important in computer science because of their applications to switching theory and design of digital computers 32 Examples of Boolean Algebras Examples 1 B 01 together with the operations 7 7 described in Boolean Functions is a Boolean Algebra Bk together with the operations a 1J2J37 7 11171127937 711k 1 y17r2y27x3y37 7 112 b 1J2J37 7 39 11171127937 711k 1 9172 yz7339ya77k E0 c 1727377k1727377 is a Boolean Algebra We can nd the element of Bk that is considered the one element77 by asking which element of Bk will satisfy the properties a one77 z and a E one77 for all z E Bk In other words7 using the de nition of the operations in Bk we need to nd the element of Bk so that for all 172737 wk 6 Bk we have 3 ABSTRACT BOOLEAN ALGEBRAS 124 123 x one77 123 wk and mlT12T2x3T3 xkTk Notice that the ordered k tuple of all 17s satis es these properties so the one element is 11 1 3 BOOLk de ned to be the set of all Boolean functions of degree k together with the operations a F G or F V G de ned by F Gu for any u E Bk b F G or F G de ned by F Gu for any u E Bk c and F de ned by W for any u E Bk is a Boolean Algebra 4 Let S be a set and let FUNS01 be the set of all functions with domain S and codomain 01 De ne the Boolean operations on FUNS01 as follows Let F G E FUNS01 then a F G S a 01 is the function de ned by F Gz for all z E S b F G S a 01 is the function de ned by F Gz for all z E S c F S a 01 is the function de ned by W for all z E S FUNS01 together with these operations is a Boolean Algebra 5 Let S be a set The power set PS together with the operations a ABAUB for all AB E PS b ABA Bfor allAB PS c A is the complement of A for all A E PS is a Boolean Algebra We can nd the element of PS that is the one element by asking which element of PS will satisfy the identity and compliments properties of a Boolean algebra lnterpreting this in terms of the way the operations are de ned on this set we see the set S is the element in PS that satis es the properties since AUA S and A S A for any set A in PS 6 The set D6 1 2 3 6 along with the operations a a b lcmab for all ab 6 D6 b a b gcdab for all ab 6 D6 c 6 6a for all a 6 D6 is a Boolean algrebra The element 1 of D6 is the zero element of D6 since it satis es the identity and compliments properties for this Boolean algebra That is zero a 6 gcda 6a 1 and a zero a 1 lcma 1 a for all a 6 D6 Discussion The set E 01 together with the Boolean operations de ned earlier is the simplest example of a Boolean algebra but there are many others some of which do not involve Boolean operations on the set 0 1 at least overtly The examples above exhibits six examples of abstract Boolean algebras including 01 and the Boolean 3 ABSTRACT BOOLEAN ALGEBRAS 125 algebra of Boolean functions discussed in the lectures on Boolean Functions and their Representations Let us examine example 3 a bit closer The set BOOL2 is the set of all Boolean functions of degree 2 In the lecture notes Boolean Functions we determined there were 16 different Boolean functions of degree 2 ln fact7 in an exercise following this observation you created a table representing all 16 Boolean functions of degree 2 Notice BOOL2 is the set of the 16 functions represented by this table EXERCISE 321 Write a table representing all the elements of BOOL2 and name the elements functions F17F27F37 7F16 a Find F3 F4 F3 F4 anng your answers will depend on how you labeled your functions b Which of the functions is the 0 element of the abstract Boolean algebra c Which of the functions is the 1 element of the abstract Boolean algebra The following table gives some of the identity elernents7 0 and 17 of the Boolean algebras given in the previous examples of abstract Boolean algebras EXERCISE 322 Fill in the rest of the information in the table Boolean Algebra 0 element 1 element an element that is neither 0 nor 1 B U 1 none B5 11111 10000 f abc a B de ned FUNG Wb 07 1 X 9 by fa we 1fltcgt1 PS S D6 1 The function XA S a B7 where A a subset of S is called the characteristic function ofA and is de ned by XAx 1 if p E A and XAz 0 if z E S 7 A X is the lower case Greek letter chi Here is another important example that we discussed in some detail in MAD 2104 EXAMPLE 327 LetB be a 3 set ofp r quot39 quot f 39 the 139quot I ifp is in B then so is op and 2 ifp andq are in B then so arequ andpq Then 3 together with the operations V for for and for is a Boolean algebra 3 ABSTRACT BOOLEAN ALGEBRAS 126 PROOF Since 3 74 Q 3 contains a proposition p By 1 p is also in B By 2 3 contains the tautology p V p 1 and the contradiction p p 0 The remaining properties were established in the materials covered in MAD 2104 D As these examples illustrate the names for addition and multiplication in a par ticular Boolean algebra may be idiomatic to that example Addition may be called sum union join or disjunction whereas multiplication may be called product inter section meet or conjunction Because the addition and multiplication operations in a Boolean algebra behave so differently from addition and multiplication in the more familiar algebraic systems such as the integers or real numbers alternative notation such as V for and for are often used instead At the risk of creating confu sion we shall use and when working in an abstract Boolean algebra but when working with a particular example such as the one above we will use conventional notation associated with that example 33 Duality DEFINITION 331 Duality Notice how the accioms of an abstract Boolean al gebra in the de nition of a Boolean algebra have been grouped in pairs It is possible to get either acciom in a pair from the other by interchanging the operations and and interchanging the elements 0 and 1 This is called the principle of duality As a consequence any property of a Boolean algebra has a dual property which is also true obtained by performing these interchanges 34 More Properties of a Boolean Algebra THEOREM 341 Properties Let B be an abstract Boolean algebra Then for any my 6 B 11dempotentLawsxx z z and z z z 2 Domination Laws z 1 1 and z 0 0 3 Absorption Laws x x z and x y a z 4xy1andzy0ifand only ifyf 5 Double Complements Law z 6 DeMorgan s Laws W E y and m E 17 Discussion The properties in Theorem 341 are all consequences of the axioms of a Boolean algebra When proving any property of an abstract Boolean algebra we may only use the axioms and previously proven results In particular we may not assume we are working in any one particular example of a Boolean algebra such as the Boolean algebra 01 In the following examples and exercises pyz represent elements 3 ABSTRACT BOOLEAN ALGEBRAS 127 of an arbitrary Boolean algebra 3 Notice that these arbitrary elements may or may not be the zero or one elements of the Boolean algebra EXAMPLE 341 For any x in 3 0 z z and 1 x x PROOF These follow directly from the Identity Laws and the Commutative Laws Notice that the second property is the dual of the rst D 35 Proof of Idempotent Laws PROOF OF FIRST lDEMPOTENT LAW Let B be a Boolean algebra and let x e B x z x p 1 Identity Law x p x E Compliments Law z x Distributive Law z 0 Compliments Law z ldentity Law D Discussion EXERCISE 351 Interpret the Idempotent Laws for the Boolean algebra PS of subsets of a set S Epample 5 EXERCISE 352 Prove the other Idempotent Law for any x in B x z p in two ways a using the principle of duality and b directly without invoking the duality principle 36 Proof of Dominance Laws PROOF OF THE THE DOMINANCE LAW 95 1 1 Let B be a Boolean algebra and let x E B x 1 x 1 1 Identity Law x 1 x E Compliments Law z 1 f Distributive Law z E ldentity Law Compliments Law Discussion 3 ABSTRACT BOOLEAN ALGEBRAS 128 One of the Dominance Laws Property 2 of Theorem 341 is proved above This Dominance Law77 may look a little peculiar since there is no counterpart in the algebra of the integers or real numbers It is however a familiar property of the Boolean algebra PS of subsets of a set S It merely says that A U S S for every subset A of S EXERCISE 361 Prove the other Dominance Law Theorem 341 Property 2 E 0 0 for every E in B in two ways a using the principle of duality and b directly without invoking the duality principle EXERCISE 362 Prove the Absorption Laws Theorem 341 Property E E and E y E E for all Ey in B Hintx Use Property EXERCISE 363 Interpret the Absorption Laws for the Boolean algebra PS of subsets of a set S EEample 5 37 Proof of Theorem 341 Property 4 Recall Theorem 341 Property 4 For allE andy in B Ey 1 andEy0 ifand only ifyE PROOF OF THEOREM 341 PROPERTY 4 Let Ey e B and suppose that E y 1 andEy0 Then y y 1 Identity Law y E E Compliments Law y E y E Distributive Law 0 y E Hypothesis y E ldentity Law On the other hand E E1 ldentity Law E E y Hypothesis E E E y Distributive Law E E y E Commutative Law 0 y E Compliments Law y E ldentity Law Thus y y E E D Discussion One direction of the if and only if7 statement of Property 4 Theorem 341 is just a restatement of the Compliments Laws hence we need only prove that if u v 1 and u v 0 then v U Since u U 0 and u v 0 it is tempting to take the resulting equation u U u v and simply cancel77 the u from each side to conclude that E v However there is no cancellation law for multiplication 3 ABSTRACT BOOLEAN ALGEBRAS 129 or addition in a Boolean algebra as there is in the algebra of the integers or the real numbers Thus7 we must be a little more clever in constructing a proof EXERCISE 371 Give an example of a Boolean algebra B and elements Eyz in B such thatEzyz butEy y Property 4 shows that the complement of an element a in a Boolean algebra is the unique element that satis es the Compliments Laws relative to u Such uniqueness results can provide very powerful strategies for showing that two elements in a Boolean algebra are equal Here is another example of uniqueness7 this time of the additive identity element 0 THEOREM 371 Suppose a is an element ofa Boolean algebra B such that Eu E for allE in 3 Then a 0 PROOF SinceEuEfor allE in B 0u0 But 0uu0u bythe Commutative and Identity Laws hence7 u 0 D EXERCISE 372 Suppose v is an element ofa Boolean algebra B such that Ev E for all E in B Prove that v 1 EXERCISE 373 Prove thatT 0 andU 1 Hintx Use Theorem 341 Property 4 and duality EXERCISE 374 Prove the Double Complements Law E E 38 Proof of DeMor39ganls Law Recall one of DeMorgan7s Laws E for all Ey in a Boolean algebra7 B PROOF Let Ey e B yetHEW xiW Z7 icyE w mm do Now apply Property 4 with u Ey and v E 1 to conclude that E E m D 3 ABSTRACT BOOLEAN ALGEBRAS 130 Discussion As in ordinary algebra we may drop the and indicate multiplication by jux taposition when there is no chance for confusion We adopt this convention in the previous proof7 wherein we give the steps in the proof of one of DeMorgan7s Laws The proof invokes the uniqueness property of complements7 Property 4 in Theorem 3417 by showing that E y behaves like the complement of zy EXERCISE 381 Give reasons for each of the steps in the proof of the DeMorgan s Law proven above Some steps may use more than one property EXERCISE 382 Prove the other DeMorgan s Law z y Er using the principle of duality EXERCISE 383 Prove the other DeMorgan s Law z y E17 directly without invoking the duality principle Notice One of the morals from DeMorgan7s Laws is that you must be careful to distinguish between z y and 3y or between E and 1y since they may represent different elements in the Boolean algebra 39 Isomorphism DEFINITION 391 Two Boolean algebras B1 and B2 are isomorphic if there is a bijection f B1 a B2 that preserves Boolean operations That is for all z andy in B1 The bijection f is called an isomorphism between B1 and B2 Discussion The adjective isomorphic was used earlier to describe two graphs that are the same in the sense that they share all of the same graph invariants A graph isomorphism was de ned to be a one to one correspondence bijection between the vertices of two simple graphs that preserves incidence The terms isomorphic and isomorphism are used throughout mathematics to describe two mathematical systems are essentially the same EXAMPLE 391 Let B be the Boolean algebra 01 and let PS be the Boolean algebra of subsets of the set S a having just one element Prove that B and PS are isomorphic 3 ABSTRACT BOOLEAN ALGEBRAS 131 PROOF PS 0 S has exactly two elements as does B Thus there are two bijections from B to 135 Only one of these however is an isomorphism of Boolean algebras namely the bijection f B a PS de ned by f0 Q and f1 S We can check that the three properties of an isomorphism hold by using tables to check all possible cases x M E 1 W 0 1 1 S S 1 S 0 I 0 x y W M zy 9611 MM f96Ufy My fz fy 0 0 I I 0 0 1 I I 0 0 1 o S 1 0 S S I I 1 0 S I 1 0 S S I I 1 1 S S 1 1 S S S S EXERCISE 391 Given B and PS as in Example 39 show that the bijeetion g B a PS de ned by 90 S and 91 Q does not de ne an isomorphism 310 Atoms DEFINITION 3101 An element a in a Boolean algebra B is called an atom if I a 31 0 and 2 for every x in B either ax a or ax 0 THEOREM 3101 A nonzero element a in a Boolean algebra B is an atom if and only iffor every my 6 B with a xy we must have a z ora y In otherwords a is indecomposable Discussion The method of exhausting all possible cases used in Example 391 to prove that a given bijection is an isomorphism is clearly not feasible for Boolean algebras that con tain very many elements The concept of an atom can be used to simplify the problem considerably Atoms are in some sense minimal nonzero elements of a Boolean alge bra and in the case of a nite Boolean algebra they generate the algebra that is every nonzero element of the algebra can be written as a nite sum of atoms 3 ABSTRACT BOOLEAN ALGEBRAS 132 EXAMPLE 3101 Let B2 00 01 10 1 1 be the Boolean algebra de scribed in Example 2 with h 2 The elements 01 and 10 are the atoms of B2 Why Notice that the only other nonzero element is 1 1 and 1 1 0 11 0 EXERCISE 3101 Let B 1z2 0 or 1 be the Boolean algebra described in Example 2 a Show that the atoms of B are precisely the elements a 00 010 0 ith cooTrdinate i 12 n Hintx Show each a is an atom and ii ifz E B has two nonzero coordinates then x is not an atom b Show that every nonzero element of B is a sum of atoms PROOF OF THEOREM 3101 Let a e B First we show Vii E Bau 0 an a i Vxy E Ba zy a a x Vay Assume a is such that an 0 or an a for all u E B and let my 6 B be such that z y a Then ax z z yd z yd 961 11 1 d But by our assumption ax 0 or ad a so z 0 or z a If x 0 then we would have y a proving Voy E Ba z y a a d V a We now will show Vxy E Ba z y a a d V a Vii E Bau 0 au a Assume a is such that Vzy E Ba zy a a z Va and let u E B Then aua au a1 a Thus an a or an a Suppose an a Then 3 ABSTRACT BOOLEAN ALGEBRAS 133 311 Theorem 3111 THEOREM 3111 fa andb are atoms in a Boolean algebra B then eithera b or ab 0 Discussion Theorem 3111 gives a property of atoms that we will nd very useful It says that7 in some sense7 atoms in a Boolean algebra are disjoint When applied to the example PS of subsets of a set S this is precisely what it is saying EXERCISE 3111 Prove Theorem 311 Hintx Use the de nition to prove the logically equivalent statement If ab 31 0 then a b 312 Theorem 3121 THEOREM 3121 Suppose that an element x in a Boolean algebra B can be eco pressed as a sum of distinct atoms a1 am Then alpham are unique epeept for their order Discussion Theorem 3121 provides the rather strong result that an element of a Boolean algebra cannot be expressed as a sum of atoms in more than one way7 except by reordering the summands In particular it shows that each individual atom is inde eomposable in the sense that it cannot be written as a sum of two or more atoms in a nontrivial way PROOF OF THEOREM 3121 Suppose x can be expressed as sums a1azambibzbm where each al and each bj is an atom of B the as are distinct7 and the bs are distinct Then7 by the Distributive Law7 for each i 17 m7 0 aiaiazam aibibzbn aiaiai02quot39aiam aibiaibzaibn 3 ABSTRACT BOOLEAN ALGEBRAS 134 By Theorem 31117 aiaj 07 ifi 31 j so that aial aiaz 39 39 aiam aiai ai lf al 31 bj for all j then7 again by Theorem 31117 aibj 0 for all j so that aZbL 1in aibn 0 This is not possible7 however7 since al 31 0 and al aZbL 1in aibn Thus7 al bj for some j By interchanging the roles of the as and the b7s7 the same argument shows that for each j bj al for some i Thus7 m n7 and the sets a1am and b1L7 bm are equal D 313 Basis THEOREM 3131 Suppose B is a nite Boolean algebra Then there is a set of atoms A aL7 a2 ak in B such that every nonzero element ofB can be eppressed uniquely as a sum of elements ofA up to the order of the summands DEFINITION 3131 Given a Boolean algebra B a set A of atoms ofB is called a basis if every nonzero element ofB can be written as a nite sum of atoms in A Discussion Theorem 3131 shows that every nite Boolean algebra has a basis7 as de ned above The niteness condition is necessary as the following exercise makes clear EXERCISE 3131 Let Z denote the set of integers Prove a The atoms of PZ are the sets for n E Z b PZ does not contain a basis PROOF OF THEOREM 3131 Suppose B x1x2zm where the as are distinct As in Representing Boolean Functions7 de ne a minterm in the as as a product ylyg ym7 where each yl is either 1 or 7 Using the Compliments Law7 z E 17 one can prove7 by mathematical induction7 that the sum of all possible minterms is 1 Z yiyZquot39ym 1 yii 0r yFE See Exercise 3132 If a minterm y1y2ym is not 07 then it must be an atom 3 ABSTRACT BOOLEAN ALGEBRAS 135 49192 39 39 192 39 39 39 39 39 39ym 07 if 9139 77 and 0 49192 39 39 192 39 39 39 39 39 ym y1y2ym71fyi Thus for any i iii391i39 Z y1y2ym Z yii 0r yi7 yii 0r yFE As observed above each product ziy1y2ym is either 0 or is equal to the rninterrn y1y2ym itself Thus if x 7 0 then x is a sum of nonzero rninterrns hence a sum of atoms Thus we have shown that each nonzero rninterrn in the ms is an atom and each nonzero element of B is a sum of nonzero rninterrns The theorem is now proved by letting A a1a2 ak be the set of all nonzero rninterrns in the zs Every nonzero element of B can be expressed as a sum of elements of A and the uniqueness of this representation follows from Theorem 3121 D EXERCISE 3132 Use mathematical induction to prove that if zlz2z are arbitrary elements of a Boolean algebra B then the sum of all minterms y1y2yT in the x s is equal to Z Hintx Notice that the terms in the sum of all minterms Z y1y2quot yr yizi or yiw7 fall into two classes those for which yl p1 and those for which yl EXERCISE 3133 Suppose In 1 2 Show that the set 12 is a basis for the Boolean algebra PU of subsets of In 314 Theorem 3141 THEOREM 3141 Suppose that B is a nite Boolean algebra having a basis con sisting ofn elements Then 3 is isomorphic to the Boolean algebra PU of subsets ofIn 12 Discussion Theorern 3141 together with Theorern 3131 provides the main characteriza tion of nite Boolean algebras Putting these two theorerns together we see that every nite Boolean algebra has a basis and hence is isomorphic to the Boolean algebra PU of subsets of the set In 12 for some positive integer n This characterization puts a severe constraint on the number of elements in a nite Boolean algebra since the Boolean algebra PU has 2 elements 3 ABSTRACT BOOLEAN ALGEBRAS 136 PROOF OF THEOREM 3141 Let 0102 a be the basis for 3 Recall that in the Boolean algebra PU addition is union U multiplication is intersection and complementation is set theoretic complementation A nonempty subset J of In determines an element of B by taking the sum of the atoms of 3 having indices in the set J For example if J 1 3 5 then we get the element i 01 as 15 of B In general we can denote the element of 3 determined by an arbitrary subset J of In by I 2 ieJ provided we adopt the convention that the empty sum adds to 0 2a 13960 De ne an isomorphism f B a PU as follows Given a subset J of I and an element s Z a ieJ of 3 set f J f is well de ned since by Theorem 3131 each element of B can be expressed uniquely as a sum of atoms By the convention this now includes 0 f has an inverse 9 PH a 3 de ned by gJ 2a ieJ Thus f is a bijection since it has an inverse In order to see that f is an isomorphism we must show that f preserves sums products and complements Two key observations are that if J and K are subsets of I then ZajZak Z a jeJ keK ieJUK 2a Z Z jEJ keK ieJ K and 3 ABSTRACT BOOLEAN ALGEBRAS 137 The rst follows from the ldempotent Law z z s since in the left hand sum ifz39 E J K then after combining like terms we get the summand aiai 1 That is after simplifying using the ldempotent Law we get a term a for each 239 in J U K and no others The second follows from the ldempotent Law xx z and Theorem 3111 After using the Distributive and Associative Laws the left hand side is a sum of terms ajak wherej is in J and k is in K Since the afs are atoms Theorem 3111 says that the only nonzero terms are terms in whichj k This only occurs when j k E J K and in this case ajaj 17 Thus if z 276 17 y ZkEK 1 are arbitrary elements of B then y Z a and zy Z 1 ieJUK ieJ K so that fy JU K f96 U M and fay J K f96 W M ln order to see tlgt f preserves complements we need one further observation If x 276 17 and if J is the complement of J in In then E Z 177 j Ej For example if n 5 and z a1 14 then E a2 a3 15 This follows from Property 4 in Theorem 341 After using the Distributive Law the terms in the product 2 2 7396 j ej are each of the form ajajz where j is in J and j in J Since J and J are disjoint j 31 j for any such term and so by Theorem 3111 the product ajaj 0 That is Z 2a 0 jeJ 7767 On the other hand we have already shown in the proof of Theorem 3131 and Exercise 3132 that the sum of all of the atoms is 1 so that Zaj Zajz Z aiZaia1agan1 73961 7767 ieJUJ id Property 4 Theorem 341 now guarantees that if z Z 17 then TE ah J EJ jeJ 3 ABSTRACT BOOLEAN ALGEBRAS 138 and so rm J z D COROLLARY 31411 Suppose that 31 and 32 are nite Boolean algebras having bases of the same size Then 31 and 32 are isomorphic EXERCISE 3141 Show that ifB is a nite Boolean algebra then B is isomorphic to B for some positive integer n 4 LOGIC GATES 139 4 Logic Gates 41 Logic Gates DEFINITION 411 Boolean algebra can be used to model circuit design in an electronic device Basic elements are gates The three most common gates are I Inuerter NI 2 AND X1 xn xn 3 OR gt X1 x2 XlX2X3x11 xn Discussion Gates are the basic building blocks of circuits We combine gates to construct combinatorial circuits or gating networks that have as output a given Boolean expres sion 42 Example 421 EXAMPLE 421 Construct a combinatorial circuit for the function F given by the following table 4 LOGIC GATES 140 96 y 2 Hag72 U U U I U U I U U I U I U I I U I U U I I U I Z Z I U U I Z I 0 Solution X Y gt zalgto gt X gt Y Z Xyzxyzxyzxyz X gt y gtDo gt 2 X Y 2 Discussion The gure given in the solution to example 421 comes from the disjunctive normal form for the function The function is equivalent to EyE 95 z z iii This 4 LOGIC GATES 141 function is also equivalent to x E3 so the combinatorial network below also has the same output Y gt xy x2 90 29 Clearly the network given here is simpler than the one given in the solution for example 421 In this section we will not be concerned with simplifying the net works7 only with getting the correct output using the gates discussed Simpli cation processes will be addressed in the next set of lecture notes 43 NOR and NAND gates DEFINITION 431 The NOR and NAND gates are given by N D X gt le y gt NOR X gt xJ y Y gt Discussion 4 LOGIC GATES 142 Recall the de nition of NAND and NOR from Representing Boolean Functions It was proven in that lecture that the sets and are both functionally complete So a combinatorial circuit can always be created so that it consists only of NAND gates or only of NOR gates 44 Example 44 1 EXAMPLE 441 Construct a circuit for the output of the eEpression E yz using only NAND gates Solution x XI WI 2 Y gt Z gt Discussion We use the following to get the expression in terms of NAND operators only E yz by DeMorgan7s Laws by the de nition of NAND by the de nition of NAND We then use this expression to make the circuit The expression used for the solution of Example 441 is not the only possible expression We could have also found an expression for Eyz using the equivalences E ElE7 Ey and E y Using these equivalences we get 2W m mm12gt zlzlltzlzlylzlylz1llltylzlylz1 This expression is much more complex than the one used for the solution in Example 4417 thoughl EXERCISE 441 Construct a circuit for the output of the eEpression in Example 44 using only NOR gates 4 LOGIC GATES 143 45 Half Adder DEFINITION 451 The half adder circuit has as input the variables x andy and has as output the variables 5 and c given by the table In ut Output a y s c 77 77 U 1 1 U 1 U 1 U 1 1 U 1 i z give the correct output for these The functions c xy and 5 functions Therefore7 the Circuit for the half adder follows gt X y sltxyltxy gt cxy 46 Full Adder DEFINITION 461 The full adder circuit has as input the variables x y and C and has as output the variables 5 and Ci1 given by the table 4 LOGIC GATES 144 Input Output u y 01 s Ci1 U U U U U U U 1 1 U U 1 U 1 U U 1 1 U 1 1 U U 1 U 1 U 1 U 1 1 1 U U 1 1 1 1 1 1 We can use the half adder to calculate the full adder as shown in the circuit below l I ssum of halfadder i gt Half adder xyxy carry of half adder Ci1 Discussion Recall from Applications of Number Theory the algorithm for adding two integers a and b written in base 2 Let a an1an2a1a02 and b bnilbnign b1b027 and suppose the sum of a and b is s snsn1sn2 51502 Note that if the binary expansions for a and b do not have the same number of digits we add zeros to the left of the smaller one to make them the same length Since sabwe have aobo20080 aibi6020181 02bz0120282 4 LOGIC GATES 145 anil bnil Cn72 207L711 Snil Snil Cn71 At the rst stage of the addition we only add the rst bits of a and b and get out the values for CO and so The half adder gives us this operation In fact7 the half adder gives us a rst stage77 of each of the following additions as well However7 we must go further than adding the bits of a and b to get the carries and sums on subsequent stages because we must also consider the carry from the previous addition The full adder gives us the carry and sum when we input the appropriate bits for a and b and the previous carry EXERCISE 461 Eccplain each stage of the algorithm used to nd the sum of the binary numbers 1011 and 110 by giving each step including which adder is used and its input and output 5 MINIMIZING CIRCUITS 146 5 Minimizing Circuits 51 Minimizing Circuits A circuit is minimized if it is a sum of products that uses the least number of products of literals and each product contains the least number of literals possible to produce the desired output The laws of Boolean algebra can often be used to simplify a complicated Boolean expression7 particularly the sum of products expressions that we have used to rep resent Boolean functions Any such simpli cation also leads to a simpli cation of combinatorial circuits 52 Example 521 EXAMPLE 521 Fzyz zyz zy2 xyify Mimimz39zed Ezpressz39zm x2 if Discussion We can simplify the expression in Example 521 as follows xyz 95112 xi xi xyz E 173x E zy1 E1 There are various methods that do not require ad hoc77 manipulation of variables for simplifying expressions and we cover two of the basic methods here Karnaugh Maps and Quine McCluskey 53 Karnaugh Maps 1 For a given number of variables7 71 form a table containing 17s for all possible minterms arranged so the minterms that are adjacent left to right or above and below differ by only a singe literal 2 Circle blocks of adjacent 17s Start with the largest possible block with number of rows and columns powers of 2 Continue circling the largest block possible so that every 1 is within at least one block 3 The simpli ed form is the sum of the products represented by each block 54 Two Variables The Table below shows how the Karnaugh map represents the minterms for two variables 5 MINIMIZING CIRCUITS 147 gtlt gtlt lt X lt EXAMPLE 541 Example 1 Two Variables Simplify xy zy Ey Solution First create a table with 1 s corresponding to each miriterm y 7 X 1 1 7 1 Necct circle blocks of size 2 gtlt 2 1 gtlt 2 arid0r blocks of size 1 gtlt 1 Last write the sum of the terms represented by the circled blocks xy Discussion When using the Karnaugh maps to simplify functions of two variable we try to nd blocks of 17s It all 4 squares have ones7 we have a 2 gtlt 2 block we circle Otherwise look for 1 gtlt 2 blocks of ones Circle any block of this size possible If there is a 1 not coveredl7 see if it is in a 1 gtlt 2 block If it is circle the block7 if not circle the one Continue in this manner until all the ones are circled 5 MINIMIZING CIRCUITS 148 Now7 suppose the blocks representing pp and x are circled The product that corresponds to this block is z since pp 17 My 17 x A method of determining the product corresponding to a block is to look for the literals that are the same in every entry in that block 55 Three Variables The Table below shows how the Karnaugh rnap repre sents the rninterrns for three variables Y2 Y2 Y2 Y2 X xyz xy2 X72 X72 X Xyz Xy2 X72 X72 The Karnaugh rnaps may be set up with the variables in different arrangements than the one in the above chart7 but they must be set up so that adjacent squares differ by only one literal Notice the entries in the left column differ from the ones in the right column by a single variable We consider the top left adjacent to the top right and the bottom left adjacent to the bottom right If you imagine rolling the chart and taping the red edges you have a tube which best represents this Karnaugh rnap EXAMPLE 551 Example 2 Three Variables Simplify pyz zijz Eyz 2y 172 i z Solution First create a table with 1 s corresponding to each miriterm gtltI Necct circle blocks of size 2 gtlt 4 1 gtlt 4 2 gtlt 2 1 gtlt 2 andor blocks of size 1 gtlt 1 5 MINIMIZING CIRCUITS 149 Last write the sum of the terms represented by the circled blocks 2 Discussion To simplify we check as follows 1 If all the squares have ones the function simpli es to 1 2 Check for blocks of size 2 gtlt 2 4 gtlt 1 2 gtlt 1 or 1 gtlt 1 Circle the largest block you can nd 3 If there is a 1 not circled nd the largest possible block containing it and if possible try to use a block that contains other 17s that are not circled 4 continue until all the 17s have been circled 5 Write down the sum of the products represented by the circled blocks 56 Four Variables The Table below shows how the Karnaugh rnap represents the rninterrns for four variables uv uv UV uv xy xyuv xyuv nyV xy v X7 xyuv xyuv xyuv xyuv 737 YVUV xyuv YVUV Yy v Ky quv quV nyV Yy v As with the map with three variables we consider the squares on the left adjacent to the corresponding ones on the right In addition we wish to consider the top 5 MINIMIZING CIRCUITS 150 row entries adjacent to the corresponding entries in the bottom row This may be Visualized by rolling the chart so we tape the red edges together to create a tube Now curve the tube around so the blue edges may be taped together to create a donut shape also called a torus EXAMPLE 561 Example 3 Four Variables Simplify zyuv zym xiii zij i iju yyuz Eyuv Eymz Solution First create a table with 1 s corresponding to each minterm uv 39EIV39 UV XY1 1 XY1 Necct circle blocks of size 4 gtlt 4 2 gtlt 4 1gtlt 4 2 gtlt 2 1gtlt 2 andor blocks 0fsize1gtlt1 UV XY1 Last write the sum of the terms represented by the circled blocks WW Discussion This time we check for blocks of size 4 gtlt 4 2 gtlt 4 2 gtlt 2 4 gtlt 1 2 gtlt 1 or 1 gtlt 1 5 MINIMIZING CIRCUITS 151 The Karnaugh maps begin to lose their ease of use when we move to more vari ables lt is still possible to use Karnaugh maps for four variables7 but the adjacent squares are more dif cult to visualize EXERCISE 561 Draw Kamaugh maps for ve variables and identify which blocks are adjacent 57 Quine McCluskey Method The Quine McCluskey method is a method used for simplifying the conjunctive normal form of a Boolean expression This method is easier to program than the Karnaugh Maps EXAMPLE 571 Simplify the eapression zyuv xqu 17115 mj E u fij zyuv Solution 1 Represent each minterm by a binary string Use 1 for the variable and 0 for the complement 2 Make a table listing the minterms7 the binary strings7 and the number of 17s in the stings Enumerate the list Minterm String no of ones 1 zyuv 1111 4 2 xum 1101 3 3 Eyuv 0111 3 4 xiii 1010 2 5 fijuz 0010 1 6 mj 1000 1 7 EQUE 0000 0 3 Find the strings that differ by only one bit Replace the different bit with a dash and remove the variable from the product that corresponds to that bit 4 Create a new table by listing the combined product7 the new product7 and the binary string Product String 17 2 zyi 11 7 1 13 gm 7111 45 17a 7010 4 6 m 10 i 0 5 7 We 00 7 0 6 7 ya 7000 5 Use the previous table to continue to reduce the products by nding strings that differ by one bit 5 MINIMIZING CIRCUITS 152 P d t 4757 677 m 6 Since there are no bit strings in the last table that differ by a single bit we are ready to nd the simpli ed expression 7 From the last table we have the string 6 This simpli ed the minterms numbered 4 through 7 From the table before we look for strings that simplify the minterms numbered 1 through 3 We use zyv and yuv to cover77 the minterms 1 2 and 3 The simpli ed form is E zyv yuv Discussion Notice that a string with a certain number of 17s will have exactly one more or one less 1 if one of the bits are changed Thus when we are looking for bit strings that differ by only one bit we only need to look at the bits that have exactly one more or one less 1 This is the only reason we add a column with the number of 17s in it We could also add this column in the later tables Combining 4 5 and 6 7 gives us the same string as we get by combining 4 6 and 5 7 so we only use one of these combinations Any time the numbers are the same we will obtain the same string We continue creating tables until we get to a table where none of the bit strings in that table differ by a single bit including the dashes Once we have all the tables created we need to cover77 all the minterms In this example we start with the last table and use the strings given in that table to cover the minterms numbered 4 5 6 7 Since this was the only product in the last table we now move to the second to the last table and look one or more products that cover the remaining minterms 1 2 and 3 Since there is a product that covers 1 and 2 we will use it Now we have to cover 3 Any product that covers 3 will do but there is only one choice in this table so we use it If there had not been a product in the second to the last table that covered 3 we would move up to the previous table It is possible to an expression to have more than one minimal expression It is also possible that there are several choices of strings from a given table that could be used to cover the minterms We chose the combinations that use the fewest possible strings to cover the most minterms
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'