labelling the vertices and edges of the two graphs | My Assignment Tutor

MATH221 Mathematics for Computer ScienceTutorial Sheet Week 12 { Autumn 20211. By suitably labelling the vertices and edges of the two graphs below, show that the graphs are isomorphic.2.(i) How many subgraphs of Kn that have all n vertices are there? (Hint: ideas about power sets are relevant.)Note that the question is not asking about the number of non-isomorphic subgraphs of Kn; that is a harderproblem.(ii) How many non-isomorphic subgraphs of K3 that have all 3 vertices are there?3. Use Kruskal’s and Prim’s Algorithms to find a minimum spanning tree for the following weighted graph. Whatis the total weight of the minimum spanning tree? Did you get the same tree in both instances? Under whatcircumstances will this happen and when will it not happen?4. Let f : N -! N be given by f(n) = 1 + n=2 if n is even and f(n) = 1 + (n – 1)=2 if n is odd. Calculate therange of f and determine whether f is one-to-one.5. Prove the following statements.(i) f : [0; 1) ! R, defined by f(x) := x2 + 1 is one-to-one but not onto.(ii) f : R ! (0; 1), defined by f(x) := x2 is onto but not one-to-one.(iii) f : (0; 1) ! (0; 1), defined by f(x) := x1 – xis bijective.


Leave a Reply

Your email address will not be published. Required fields are marked *