Discrete Structures ENGR 213
Christopher Newport University
Popular in Course
Popular in Engineering and Tech
This 139 page Class Notes was uploaded by Tony Davis on Monday October 5, 2015. The Class Notes belongs to ENGR 213 at Christopher Newport University taught by Dali Wang in Fall. Since its upload, it has received 6 views. For similar materials see /class/219482/engr-213-christopher-newport-university in Engineering and Tech at Christopher Newport University.
Reviews for Discrete Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/05/15
Section 11 Logic Introduction Applications of discrete mathematics Formal Languages computer languages Digital Circuits Compiler Design Data Structures Computability Algorithm Design Relational Database Theory Complexity Theory counting Example counting The Traveling Salesman Problem important in Circuit design Many other CS problems Given n cities c1 c2 cn Distance between city i and j du Find the shortest tour Example cont Assume a very fast PC 1 flop 1 nanosecond 10399 sec 1000000000 opssec 1 GHz A tour requires n1 additions How many different tours Choose the first city n ways the second city n1 ways the third city n2 ways etc Example cont Logic tours n n1 n2 2 1 n Combinations Total number of additions n1 n Rule of Product If n8 Tn 78 282240 flops lt 13 second HOWEVER If n50 Tn 4950 148 1066 149 1057 seconds 248 1055 minutes 413 1053 hours 172 1052 days 246 1051 weeks 473 1049 years a longtime Logic De nitions Proposition a proposition is a statement that is either true T or 1 or false F or 0 but not both 1 1 2 2 2 5 the moon is made of green cheese go to town What time is it A factbased declaration is a proposition even if no one knows whether it is true 11213 is prime 1 is prime There exists an odd perfect number Logic Logic De nitions Logic Boolean Variable a variable whose value is either true 1 or false 0 Propositional variables P Q R S New Propositions from old calculus of propositions propositional logic relate new propositions compound proposition to old ones Logical analysis begins with the modeling of fact based natural language declarations by propositions Examples Portland is the capital of Oregon Columbia University was founded in 1754 If 22 5 then you are the pope Logic De nitions Truth Table used to display the relationship between the truth values of propositions The boolean domain is the set T or 1 F or 0 Either of its elements is called a boolean value Logical Operations Negation Negation not Negation of P it is not the case that P Symbol a Truth Table Example P I am going to town a P It is not the case that I am going to town I am not going to town Logical Operations Conjunction Conjunction and P and Q is true when both P and Q are true and is false otherwise Symbol Truth Table Example P I am going to town Q It is going to rain PAQ I am going to town and it is going to rain Note Both P and Q must be true Logic 10 Logical Operations Disjunction Disjunction inclusive or P or Q is false when P and Q are both false and true otherwise Symbol v Truth Table Example P I am going to town Q It is going to rain PvQ I am going to town or it is going to rain Note Only one of P Q need be true Hence the inclusive nature Logic 11 Logical OperationsExclusive OR Exclusive OR Symbol r Exclusive OR of P and Q is the proposition that is true when exactly one of P and Q is true and is false otherwise Truth Table Example P I am going to town Q It is going to rain P 6 Q Either I am going to town or it is going to rain Truth Table Note Only one of P and Q must be true Logic 12 Logical Operations Others Bitwise AND OR operations Others NAND I NOR J Logical Operations Implication Implication Ifthen Symbol gt Implication P gt Q is the proposition that is false when P is true and Q is false and true otherwise Truth Table P gt Q 1 OOU AO OQ 1 0 1 Logic Implication Terminology P premise hypothesis Q conclusion consequence Example P I am going to town Q It is going to rain P gt Q Ifl am going to town then it is going to rain Implication Equivalent forms If P then Q P implies Q If P Q P only if Q P is a sufficient condition for Q Q if P Q whenever P Q is a necessary condition for P Implication Note The implication is false only when P is true and Q is false If the moon is made of green Cheese then I have more money than Bill Gates If the moon is made of green Cheese then I m on welfare If 11 3 then your grandma wears combat boots If I m wealthy then the moon is not made of green Cheese If I m not wealthy then the moon is not made of green Cheese Logic 17 Implication Converse and Contrapositive Q gt P is the CONVERSE of P gt Q Q gt P is the CONTRAPOSITIVE of P gt Q Implication Logic Example Find the converse and contrapositive of the following statement R Raining tomorrow is a sufficient condition for my not going to town Step 1 Assign propositional variables to component propositions P It will rain tomorrow Q I will not go to town Step 2 Symbolize the assertion R P gt Q Step 3 Symbolize the converse Q gt P Step 4 Convert the symbols back into words If I don t go to town then it will rain tomorrow Or Raining tomorrow is a necessary condition for my not going to town or My not going to town is a suf cient condition for it raining tomorrow Logical Operations Bidirectional Biconditional Bidirectional if and only if iff Symbol lt gt Biconditinal Plt gt Q is the proposition that is true only when P and Q have the same truth value Truth Table Example P I am going to town Q It is going to rain Plt gtQ I am going to town if and only if it is going to raIn Note Both P and Q must have the same truth value Equivalent forms P if and only if Q P is necessary and sufficient for Q Logic 20 Form a Logical Expression Translating a sentence into a propositional expression Step 1 breaking assertions into component propositions Step 2 look for the logical operators Example Ifl go to Harry s or go to the country I will not go shopping P go to Harry s Q go to the country R I will go shopping Logic Form a Logical Expression Example You can not drink beer if you are under 21 unless you are accompanied by your teacher Step 1 Step 2 Recursive Section 35 Recursive Algorithms Recursive Algorithms A recursive algorithm is one which calls itself to solve smaller versions of an input problem Some algorithms are recursive by nature Binary search Fibonacci sequence R eeee sive Algorithms How it works The current status of the algorithm is placed on a stack A stack is a data structure from which entries can be added and deleted only from one end like the plates in a cafeteria PUSH put a 39plate39 on the stack POP take a 39plate39 off the stack When an algorithm calls itself the current activation is suspended in time and its parameters are PUSHed on a stack The set of parameters need to restore the algorithm to its current activation is called an activation record TOP Recursive Algumhms 3 Example Example classical procedure factorial n make the procedure idiot proof if n lt 0 return 39error39 if n 0 then return 1 else return n factorial n1 Recursive Algorithms The operating system supplies all the necessary facilities to produce factorial 3 PUSH 3 on stack and call factorial 2 PUSH 2 on stack and call factorial 1 PUSH 1 on stack and call factorial 0 return 1 POP 1 from stack and return 1 1 POP 2 from the stack and return 2 1 1 POP 3 from the stack and 4 return 3 2 1 1 Example Complexity Let fn be the number of multiplications required to compute factorial n f0 O the initial condition fn 1 fn1 the recurrence equation R eeee sive Algorithms Example A recursive procedure to find the max of a nonvoid list Assume we have builtin functions called Length which returns the number of elements in a list Max which returns the larger of two values Listhead which returns the first element in a list Max requires one comparison R eeee sive Algorithms Example procedure maxist list Complexity The strip off head of list and recurrence equation for pass the remainder the number of I d m n n r Ir Esratttzalznst return LIstheadIIst n is else f 1 0 return Max Listheadlist maxistremainder of list fn 1 fn1 Recursive Algorithms Example Example Find the maximum element from a list assuming the length is a power of 2 We divide the list in half and find the maximum of each half Then find the Max of the maximum of the two halves R eeee sive Algorithms Example procedure maxist list a divide and conquer approach if Length list 1 then return Listheadlist else a maxist fist half of list b maxist second half of list return Maxa b Recursive Algorithms Recurrence equation for the number of comparisons required for a list of length n fn is f1 0 fn 2 fn2 1 There are two calls to maxist each of which requires fn2 operations to find the max There is one comparison required by the Max function Example f162f81 f8 2 f4 1 f4 2f2 1 f22f11 f10 So f21 f4211 3 f82317 f16271 15 fn Pecuvswe Aigumhms Divide list in half Divide lis in half Divide iisl in Iialf XXXxiXXXXXXXxixxXX Logic Sets Section 12 Propositional Equivalences De nitions A tautology is a proposition which is always true Classic Example PV IP A contradiction is a proposition which is always false Classic Example PAAP A contingency is a proposition which neither a tautology nor a contradiction Example P vQ gtAR Propositional Equivalences 2 Logical Equivalence De nition Two propositions P and Q are logically equivalent if Plt gtQ is a tautology We write P ltgt Q or P E Q Example P gtQ AQ gt PltgtPlt gtQ Note Because of this equivalence if and only if or iff is also stated as is a necessary and suf cient condition for Propositional Equivalences Logical Equivalence Proof To show logical equivalence the left side and the right side must have the same truth values independent of the truth value of the component propositions Example Show that P gtQ ltgt PvQ Propositional Equivalences Logical Equivalence Proof To show a proposition is not a tautology or two propositions are not logical equivalent use an abbreviated truth table Try to find a counter example or to disprove the assertion Search for a case where the proposition is false Example find out either the two expression are logical equivalent P gtQ and Pv Q Propositional Equivalences Logical Equivalence Proof Example Prove P vQ Rltgt P VQ P v R Propositional Equivalences Logical Equivalence Table Some famous logical equivalences P T ltgt P P v F ltgt P Identity P v T ltgtT P F ltgt F Domination P v Pltgt P P PltgtP Idempotency Pltgt P Double negation P vQltgtQv P P AQltgtQA P Commutativity Propositional Equivalences Logical Equivalence Table P VQV Rltgt Pv Qv R P AQ Rltgt P QA R P Qv Rltgt P AQV P R P vQ Rltgt P VQ P v R P gtQltgt P vQ P v Pltgt T Propositional Equivalences Associativity Distributivity DcMorgan s laws Implication Tautology Logical Equivalence Table P A Pltgt F Contradiction P gtQ Q gt Pltgt Plt gtQ Equivalence P gtQ P gt Qltgt P Absurdity P gtQltgt Q gt P Contrapositive P VP AQltgt P P P vQltgt P Absorption P AQ gt Rltgt P gtQ gt R Exportation Propositional Equivalences f Methods Section 33 Induction De nitions De nition A set S is well ordered if every subset has a least element Let PX be a predicate over a well ordered set S The problem is to prove VxPx The rule of inference called The first principle of Mathematical Induction can sometimes be used to establish the universally quanti ed assertion Section 33 Induction Some Background From modus ponens P P gt q q conclusion We can easily derive double modus poncns W M gt 130 130 gt p2 p2 conclusion Section 33 Induction Some Background We might also derive triple modus ponens quadruple modus ponens and so on Thus we have no trouble proving assertions about arbitrarily large integers A classic example For instance the initial domino falls If any of the first 999 dominoes falls then so does its successor Therefore the first 1000 dominoes all fall down Sectmn 3 3 lnducuun Mathematical Induction The rst principle of Mathematical Induction The problem is to prove VxPx In the case that X e N SN the natural numbers the principle has the following form PO Pn gt Pn 1 VxPx The hypotheses are H1 PO and H2 Pn gt Pn 1 for n arbitrary H1 is called The Basis Step H2 is called T he Induction Inductive Step Section 33 Induction Mathematical Induction We first prove that the predicate is true for the smallest element of the set S 0 if S N We then show if it is true for an element X n if S N implies it is true for the next element in the set n 1 if S N Then knowing it is true for the first element means it must be true for the element following the first or the second element knowing it is true for the second element implies it is true for the third and so forth Therefore induction is equivalent to modus ponens applied an countable number of times Section 33 Induction 6 Mathematical Induction Summary Summary two steps involved in a induction proof Basis Step H1 Pk k 0 for natural number Induction Step Pn gt Pn 1 for arbitrary 11 To prove Pk merely a veri cationsubstitution is needed To prove H2 we normally use a Direct Proof Section 33 Induction 7 Example Prove a classic nnl 01 2 Solution EH Step 0 Identifying Pn1 Wail nn2 1 Step 1 The Basis Step H1 we need to prove P 0 I 0 0 0 1 21 2 i0 Section 33 Induction Example Cont Step 2 T he Induction Inductive Step H2 using a direct proof State the Induction Hypotheses Assume Pn is true for n arbitrary Now use this and anything else you know to establish that Pn I must be true Pn I is the assertion n1 1 1 1 I 2 n n i0 2 Note Write down the assertion Pn Don39t make it hard for yourself because you don39t know what it is you are to prove Section 33 Induction 9 Example Cont Step 2 cont Note you must manipulate the assertion Pn1 so that you can apply the induction hypothesis PM If for you do not apply the induction hypothesis somewhere it is not a valid induction proof But iiiinl Use thelgssuiiiption PM to substitute 1 l for nn2 to get quot1 nn 1 i0 n1 Section 33 Induction 10 Example Cont Step 2 cont We manipulate the right side to get which is exactly Pn1 i0 Hence we have established H2 We now say by the Principle of Mathematical Induction it follows that PM is true for all n or it nn 1 i0 2 QED n 1n 1 1 2 Section 33 Induction 11 Mathematical Induction We can use the Principle to prove more general assertions because N is well ordered Suppose we wish to prove for some speci c integer k Vxn Z k gtPx Now we merely change the basis step to Pk and continue Section 33 Induction Example Prove the sum of first n odd positive integers is n2 n 21 Section 33 Induction 13 Example Prove 2n lt n for positive integers n 2 4 Section 33 Induction Recursive Section 34 Recursive Definitions Recursive form Recursive form defines a set an equation or a process by defining a starting set or value and giving a rule for continuing to build the set equation or process based on previously defined items Recursive De nition A recursive definition has two parts Basis must define values for some finite number of elements For sets State the basic building blocks 88839s of the set For functions State the values of the function on the 888 s Recursion remaining elements are defined by the recursion relation For sets Show how to build new things from old with some construction rules For functions Show how to compute the value of a function on the new things that can be built knowing the value on the old things Recursive Definitions Recursive De nition Recursiver Defined Functions Function F defined on nonnegative integers To give a recursive definition of F Basis Specify F0 Recursive Step Give a rule for defining Fn1 from Fevaluated at smaller values Example Example set A recursive definition of N set of natural numbers 1 Basis O is in N O is the BBB 2 Induction if n is in N then so is n 1 how to build new objects from old add one to an old object to get a new one Recursive Definitions Example Example function Now given the above recursive definition of N we can give recursive definitions of a function on N 1 f0 1 the initial condition or the value of the function on the 888 s 2 fn 1 n 1 fn the recurrence equation how to define fon the new objects based on its value on old objects Example Example function A recursive definition of the Fibonacci sequence Classical A young pair of rabbits one for each sex is placed on a island After they are 2 months old each pair produces another pair each month The number of pairs of rabbits after h month is fn Mommy 01mm New F 1 Basis 0 f0 f1 1 two initial conditions 2 Induction fn1fnfn1 the recurrence equation 1 l 2 l 2 3 4 Recursive De nitions Example Example set A recursive definition of the set of strings over a finite alphabet An alphabet 2 is a finite set A string over 2 is a finite sequence of symbols from 2 The set of all strings over 2 is denoted by 2 The empty string the string containing no symbols is the string containing no symbols lts length is O and it is denoted by A Note he 2 wx e 2 wheneverw e 2 and X e 2 A language over 2 is a subset of 2 Recursive Definitions 8 Example Examples Give recursive definitions of Fna Fn flak Example a Example Given the recurrence relation an221n1an2 for n2 3 4 Determine if sequence an is a solution if an3n Recursive Definitions 10 Example Compound Interest On your 21St birthday you get a letter informing you that on the day you were born an eccentric rich aunt deposited 100000 in a bank account earning 4 interest compounded annually and she now intends to turn the account to you provided that you can gure out the questions bellow 1 Find out the worth of the account k year after you were born using a recursive de nition 2 Find a closedform representation of the account worth for kth year and prove that it is valid Recursive Definitions 11 Permutations Combinations and Binomial Theorem Section 43 amp 44 of Text Permutation De nition Definition Permutation is an ordered arrangement of distinct objects of a set A permutation is an arrangement that order matters After selecting the objects two different orderings or arrangements constitute different permutations Notation An ordered rselection from a set S of n elements traditionally named r permutation is a sequence of r objects from S denoted as Pn r Permutations Combinations and Binomial Theorem Permutation Calculation Example passwords of length 6 from distinct alphabets In general to compute rpermutation of a set with n element Pn r Choose the first object n ways Choose the second object since selection is without replacement n 1 ways the rth object n r 1 ways Thus Pnr nn 1n 2 n r 1 Note n Pnr Permutations Combinations and Binomial Theorem Permutation Examples Suppose a salesman has to visit 8 different cities He has to begin his trip in a specified city and end his trip in a specified city He can visit the other cities in any order he wishes How many possible orders can he use How many different ways can three of the letters of the word BYTES be chosen and written in a row How many different ways can this be done if the first letter must be B Permutations Combinations 4 and Binomial Theorem Combinations De nition Definition an rcombination of elements of a set of n elements is an unordered selection of r distinct elements from the set It is simply a subset of the set with r elements It is equivalent to selecting subsets of size r from a set of size n denoted as Cn r Permutations Combinations and Binomial Theorem Combinations Calculation Example how many unordered 2 selection of elements can be made from the set 0 1 2 3 In general the r permutation Pn r can be obtain by Form the rcombinations Cn r Ordering the r elements within each r combination set which can be done in Pr r way Thus Pn rCn rPr r and n Pnr n Cn r Z r Pnr n rr Permutations Combinations and Binomial Theorem Combinations Examples How many ways are there choosing 3 members from a group of 12 seniors to form a team for the ACM programming contest How many ways are there to select a committee to develop a discrete mathematics course if the committee is to consist of 3 faculty from the math department and 4 form computer department if there are 9 faculty members in math department and 11 members in computer department Permutations Combinations and Binomial Theorem Permutation vs Combination Two distinct methods to select r elements from a set of n elements In an ordered selection permutation it is not only what elements are chosen but also the order in which they are chosen In an unordered selection combination it is only the identity of the chosen elements that matters Permutations Combinations 8 and Binomial Theorem Exercises The IEEE club has 15 members How many ways are there to chose four members of the club to serve on a executive committee How many ways to choose a president vice president secretary and treasurer of the club There are 6 candidates for governor of a state In how many different orders can the names of the candidates be printed on a ballot A circuit consists of 10 components 2 of them are faulty How many different set of locations for these two faulty components are possible Permutations Combinations and Binomial Theorem Combination Calculation Theorem the number of rcombination of a set with n elements is Cnjr n Pnr n r Prr n rr Interesting facts about some combination values Cn O Cn 1 Cn n Permutations Combinations and Binomial Theorem More on Combination Corollary Cn r Cn nr proof why Corollary ECO190221 Corollary Pascal s Identity Cn 1 kCn k1Cn k It produces Pascal s triangle Permutations Combinations 11 and Binomial Theorem Example Suppose you flip a fair coin n times How many different ways can you get no heads exactly one head exactly two heads exactly r heads at least 2 heads Permutations Combinations and Binomial Theorem Example How many bit string consisting of Os and 1s of length 4 have exactly 2 ones or exactly 2 zeros Permutations Combinations and Binomial Theorem Example 39 i How many bit string of length 100 have at least 2 ones Permutations Combinations 14 and Binomial Theorem Functions Complexity of Algorithms Section 21 23 Complexity of Algorithms Algorithm Complexity Space Complexity Determine the approximate memory required to solve a problem of size n Time Complexity Determine the approximate number of operations required to solve a problem of size n Complexity of Algorithms 2 Time Complexity Time Complexity Use the BigO notation Ignore house keeping Count the expensive operations only Basic operations searching algorithms key comparisons sorting algorithms list component comparisons numerical algorithms floating point ops flops multiplicationsdivisions andor additionssubtractions Complexity of Algorithms Time Complexity Running Scenarios Best Case minimum number of operations Worst Case maximum number of operations Average Case mean number of operations assuming an input probability distribution Basic Operation Selection another variant Complexity of Algorithms 4 Case Study Numerical A Numerical Algorithm Analysis worst case Multiply an n x n matrix A by a scalar c to produce Count the number of oatmg pomt the matrix B It 1 t mu 1 1021 10118 procedure n c A B p n2 elements requ1res n2 forifromltondo mult1p11cat10ns for j from 1 to n do 130 j GAG 139 end do end do or quadratic complexity time complexity is On2 Complexity of Algorithms 5 Case Study Numerical A Numerical Algorithm Multiply an n x n upper triangular matrix A Ai j 0 if i gt j by a scalar c to produce the upper triangular matrix B procedure 11 c A B A and B are upper triangular for i from 1 to 11 do for j from i to 11 d0 130 j GAO j end do end do Complexity of Algorithms Analysis worst case Count the number of floating point multiplications The maximum number of nonzero elements in an n x n upper triangular matrix 1234Hn n2 n2 n n22 n2 Quadratic complexity but the leading coefficient is 12 Case Study Sorting Sorting Algorithms Bubble sort L is a list of elements to be sorted We assume nothing about the initial order The list is in ascending order upon completion Method Bubble the largest element to the 39top39 by starting at the bottom swap elements until the largest in the top position Bubble the second largest to the position below the top Continue until the list is sorted Note this is not an efficient implementation of the algorithm Complexity of Algorithms Case Study Sorting Sorting Algorithms Analysis procedure bubble n L 39 39 iS a Usquot f demerits n1 comparison on the first pass 39 SWaP 393 3 Intermed39ate n2 comparisons on the second swap location pass for i from n 1 to 1 by 1 do 1 comparison on the last pass for from 1 to i do Total ifLJgtLJ1d0 n1n21On2 swap Lj 1 or H 1 H quadratic complexity swap what IS the leading coeffICIent end do end do end do Complexity of Algorithms Case Study Search Search algorithm locate an element x in a list of distinct elements or determine that is not in the list Linear searchsequential search algorithm The linear search algorithm begins by comparing x and a1 lfx a1 the solution is the location of a1 If x 7 a1 compare x with a2 Continue this process until a match is found unless no match is found Complexity of Algorithms Case Study Search Procedure linearsearch X integer a1 a2 a distinct integers i1 while iltn and Xiai ii1 if iltn then location i else location 0 location 0 means no match found Complexity of Algorithms 10 Case Study Search Worst case Need to go through all of the n element in the list to find the match or no match found Each step two comparisons are performed Finally one more comparison is needed Worst case 2n1 comparison Worstcase analysis tells us the number of operations required to guarantee a solution Complexity of Algorithms Case Study Search Best case find the match on the 1st element Average case X is the ith element in the list Number of comparison 1 1 2 3 IUIUJ n 2n1 The average number of comparison used 3572n1 I l n2 Complexity of Algorithms Selection of Key Operations Basic operation need to determined prior to complexity analysis The selection depends on Algorithm under study Computer running the algorithm Complexity of Algorithms Case Study Sorting Selection Sort algorithm Basic operations SelectionSortaiSt N comparison swap or both for position1 to N1 do Complexity is different based small S positior on the selection of basic I t operations 390 3 39 99839 Ion case 1 nn12 for pOSIton1 to N do case 2 n1 If smagtst then Iistm case 3 sma Big difference Mace endif swapistpositionlistplace endfor end for Complexity of Algorithms 14 Chapter 8 Part 2 Graphs W O Representing Graphs amp Graph Isomorphism 83 9 Connectivity 84 by Kenneth H Rn en A Fi h F dih39 on Me GmwHill 2003 n Dr M Representing Graphs amp Graph IsomorphisH KIXIIIZ39IIIIIZIIIIIIIIIII39IIIIIIII 9 Introduction goals Choose the most convenient representation of a graph We need to determine whether 2 graphs are isomorphic this problem is important in graph theory Representing Graphs Representing Graphs Adjacency Lists 9 Use adjacency list which specifies the vertices that are adjacent to each vertex of the graph Example Use adjacency lists to describe this simple graph Vertex Adjacent vertices b 81 39 a 4 COUIon b c e eQ d ade O ce acd CDQOO39Q Representing Graphs Adjacency Lists cont Example Adjacency list Adjacent Vertex Vertices a b c b a c e f c a I f d e I f c b Representing Graphs Representing Graphs Adjacency Matrices A A A A A A A A A A A A A A A A A A A A A A A A A A A A A AA O Adjacency matrices To simplify computation graphs can be represented using matrices The adjacency matrix is defined as A an such that I ifvivjis an edgeofG ij 0 0therw1se Representing Graphs Example Use a adjacency matrix to represent this graph aye c ti Solution We order the vertices a b c d The matrix representing this graph is 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 Representing Graphs Adjacency Matrices Cont TO C FROM abcdef a010011 b d b c a e d W5 e f Representing Graphs Adjacency Matrices cont A A A A A A A A A A A A A A A A A A A A A A A A A A A A A AA In case of pseudographs the adjacency matrix is not a binary matrix but is formed of elements that represent the number of edges between 2 vertices Example Use an adjacency matrix to represent this pseudograph a Q I Solution The adjacency matrix using The ordering of vertices a b c d Representing Graphs Graph Isomorphism O Isomorphism of graphs Goal is it possible to draw 2 graphs in the same way In chemistry different compounds can have the same molecular formula but can differ in structure The graphs of these compounds may not be drawn in the same way Graphs having the same structure share common properties Graph Isomorphism Graph Isomorphism cont 0 Graph isomorphism Two graphs are isomorphic iff they are identical except for their node names Definition 1 The simple graphs G1 V1E1 and G2 V2E2 are isomorphic if there is a onetoone and onto function f from V1 to V2 with the property that a and b are adjacent in G1 if and only if fa and fb are adjacent in G2 for all a and b in V1 Such a function f is called an isomorphism Graph Isomorphism AAAA A A A A A A A A A A A A A A A A A A A A A A A A A AA Exampte Show that the graphs G VE and H WF are isomorphic ll pllj V1 V2 u 1 u V3 V4 1 H Solution The function fwith fu1 v1 fu2 v4 fu3 v3 fu4 v2 is a onetoone correspondence between V and W To see that this correspondence preserves adjacency note that adjacent vertices in G are u1 and u2 u1 and U3 u2 and U4 and U3 and U4 and each of the pairs fu1 v1 and fu2 v4 fu1 v1 and fu3 v3 fu2 v4 and fu4 v2 and fu3 v3 and fu4 v2 are adjacent in H Graph Isomorphism Graph Invariants under Isomorphism Necessary but not suf cient conditions for G1V E1 to be isomorphic to GZV E2 We must have that V1V2 and E1E2 The number of vertices with degree n is the same in both graphs For every proper subgraph g of one graph there is a proper subgraph of the other graph that is isomorphic to 9 Graph Isomorphism Isomorphism Example Olf isomorphic label the 2nd graph to show the isomorphism else identify difference Graph Isomorphism Isomorphism Example Olf isomorphic label the 2nd graph to show the isomorphism else identify difference ofvertl39ces 0 of edges 0 ofverts 0f the same degree Graph Isomorphism Connectivity 84 VVVVYVVVVVVVVVVVVVVVVY V V V V V V V VV A A A A A A A A A A A A A A A A A A A A A A A A A A A A A AA 9 Goal determination of paths within graphs 0 Many problems can be modeled with paths formed by traveling along the edges of graphs 9 Some examples of problems are Study the link between remote computers Efficient planning of routes for mail delivery Garbage pickup Diagnostic in computer networks Connectivity Definitions Oln an undirected graph a path oflength n from u to v is a sequence of n adjacent edges going from vertex u to vertex v 9A path is a circuit if uv 9A path pass through or traverses the vertices along it 9A path is simple if it contains no edge more than once Connectivity EZSQSEO 8 moEw 4500 v 552 5 8 moEw Ewa HmEmew I momem lt Paths in Directed Graphs VVVVVVVVVVVVVVVVVVVVVY V V V V V V V VV A A A A A A A A A A A A A A A A A A A A A A A A A A A A A AA OSame as in undirected graphs but the path must go in the direction of the arrows Connectivity Connectivity O Connectedness in undirected graphs Question asked When does a computer network have the property that every pair of computers can share information if message can be sent through one or more intermediate computers This question is equivalent to When is there always a path between 2 vertices in the graph Connectivity Connectivity Definition De nition An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph Theorem There is a simple path between every pair of distinct vertices of a connected undirected graph nnec iVity Connectivity cont A graph that is not connected is the union of two or more connected subgraphs each pair of which has no vertex in common These disjoint connected subgraphs are called the connected components of the graph Connectivity Connectivity in Directed Graph 0 Connected in directed graphs Definition A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph Definition A directed graph is weakly connected if there is a path between every 2 vertices in the underlying undirected graph Connectivity Connectivity in Directed Graph cont A directed graph is weakly connected ltgt there is always a path between 2 vertices when the directions of the edges are ignored Strongly connected gt weakly connected directed graph Connectivity in Directed Graph cont Example Are the directed graphs G and H strongly connected a b a G I he Hg h c 9 e d Connectivity Connectivity and Isomorphism O Paths amp isomorphism Paths and circuits can help determine whether 2 graphs are isomorphic The existence of a simple circuit or cycle of a particular length is a useful invariant to show that 2 graphs are not isomorphic Connectivity Isomorphism Example Example Determine whether the graph G and H are isomorphic u6 uz v6 V2 u fV w u4 V4 Connectivity Counting Paths 9 Counting paths between vertices Theorem Let G be a graph with adjacency matrix A with respect to the ordering v1 v2 vn with directed or undirected edges with multiple edges and loops allowed The number of different paths of length r from vi to V where r is a positive integer is equals to the i jth entry of Ar Counting Paths cont Example How many paths of length 4 are there from a to d in the simple graph G a b G Connectivity K J Sets Section 17 Set Operations Logic and Set Theory Propositional calculus and set theory are both instances of an algebraic system called a Boolean Algebra The operators in set theory are defined in terms of the corresponding operators in propositional calculus Set Operations Set Equivalence Definition Two sets A and B are equal denoted A B iff Vxx eAlt gt x EB Note By a previous logical equivalence we have A B iff Vxx eA gt x EB x 63 x 61 Or AB iffA gBanngA Set Operations Venn Diagrams A useful visualization tool for 3 or less sets The Universe U is the rectangular box Each set is represented by a circle and its All possible combinations of the sets must be interior represented 43 For 2 sets Set Operatluns U For 3 sets Set Operations The union ofA and B denoted A U B is the set X XEAVXEB The intersection ofA and B denoted A m B is the set X XEAAXEB Note If the intersection is void A and B are said to be disjoint The complement of A denotedZ is the set X X A Set Operations Set Operations The difference ofA and B or the complement of B relative to A denoted A B is the set A m B Note The absolute complement ofA is U A The symmetric difference of A and B denoted Ae B is the set A BUB A Set Operations Venn Diagram for Set Operations Confirming Identities with Venn Diagrams shade the appropriate region to represent the given set operation Example 1 m distributes over U A m B w CAmB w AmC Example 2 u distributes over m A w BmCAUB AUC Set Operations Set Identities Set identities correspond to the logical equivalences Identity Law A U Q A A m U A Domination Law A u U U A m Q Q Idempotent Law A u A A A m A A Complementation Law A7 A Set Operations ma 5258 00333123 rmltltn gtCwangt gtmmoomltm rmltltn gtCAwCOVn AgtCwVCO gtDAwDOVn 3930 Daiccgm rmltltn gtDAwCOVn AgtDwVCAgtDOV gtCAwDOVn AgtCwVDAgtCOV Um 2662 52 l mchJm mDmumCm m9 Ovm mzozm Union and Intersection of Indexed Collections LetA1 A2 sets Union and intersection are associative because 39and39 and 39or39 are we have 9111 AIUA2UmUAn An be an indexed collection of 1141 AlmA2mnmAn Examples Let AI i 00 1 s i lt 00 1 1 11 U141 2 mAi 2 i1 i1 Set Operations Section 16 Sets Set De nition A set is a collection of objects or elements or members A set is said to contain its elements There must be an underlying universal set U either specifically stated or understood Notation x is a member of S or X is an element of S X e S x is not an element of S X 9E S 2 e 57 7c algebra 2 2718 8 e p p is a prime number Sets Set Representation List the elements between braces S a b c db c a d CI Note listing an object more than once does not change the set Ordering means nothing Specification by predicates propositional functions 8 XI l3X 8 contains all the elements from U which make the predicate P true X y X y eR X2y2 1 Brace notation with ellipses S 3 2 1 the negative integers Sets Common Universal Sets R reals N natural numbers 01 2 3 the counting numbers Z all integers 3 2 1 O 1 2 3 4 2 is the set of positive integers Sets Subsets amp Null Set Sets Definition The set A is a subset of the set B denoted A g B iff Vxx eA gtx EB Definition The void set the null set the empty set denoted Q is the set with no members Note the assertion x 5 is always false Hence Vxx gtx GB is always true Therefore is a subset of every set Note Any set is always a subset of itself Relations on Sets Sets Definition IfA g B but A at B the we say A is a proper subset of B denoted A c B in some texts Definition The set of all subset of a set A denoted PA is called the power set of A Example IfA a b then PA Example P1 3 5 More on Sets Definition The number of distinct elements in A denoted A is called the cardinality of A lfthe cardinality is a natural number in N then the set is called nite else infinite Example A a b a b 2 Pa b P1 3 5 Sets