picking an arbitrary subset of the edges | My Assignment Tutor

1. .2. (i) We saw in class that Kn has 1 2n(n – 1) edges. The subgraphs we want are formed by keeping all the verticesand picking an arbitrary subset of the edges. Therefore, the number of subgraphs is the number of elements inthe power set of the set of edges, that is, 212n(n-1).(ii) There are 4 non-isomorphic subgraphs of K3 with all 3 vertices: (1) 3 vertices and no edges, (2) 3 vertices andany one edge, (3) 3 vertices and any two edges, and (4) 3 vertices and all three edges. Every subgraph of K3 isisomorphic to one of those 4. (There are 23 = 8 subgraphs with all 3 vertices in total).3. Kruskal’s Algorithm gives the following table. Will adding edgemake a circuit?ActiontakenCumulative Weightof subgraphEdgeWeight(v2; v4)74noadded74(v5; v7)83noadded157(v7; v8)151noadded308(v3; v5)230noadded538(v6; v7)242noadded780(v4; v6)262noadded1042(v4; v7)269yesnot added1042(v3; v7)306yesnot added1042(v2; v7)348yesnot added1042(v1; v4)355noadded1397 So a minimum spanning tree is the following.v1v2 v3v4v5v6 v7151242 v835574262 23083 Prim’s Algorithm starting at v1 gives the following table. Vertex addedEdge addedWeightCumulative weightv1v4(v1; v4)355355v2(v2; v4)74429v6(v4; v6)262691v7(v6; v7)242933v5(v5; v7)831016v8(v7; v8)1511167v3(v3; v5)2301397 So a minimum spanning tree is as follows.v1v2 v3v4v5v6 v7151242 v835574262 23083These two trees are the same, which will always happen if there are no two edges with the same weight, or if for everyinstance of edges with the same weight the same edge happens to be chosen by both algorithms.4. f(1) = 1 + 1-2 1 = 1; f(2) = 1 + 2 2 = 2; f(3) = 1 + 3-2 1 = 2; f(4) = 1 + 4 2 = 3; f(5) = 1 + 5-2 1 = 3; f(6) =1 + 63 = 4; : : :So we suspect that ran f = N. Certainly all function values are whole numbers and positive numbers; we see that bythe definition of the function. We must be sure that every natural number can be obtained, so let p 2 N be arbitrary.Notice that all the function values we found above can be obtained using the “n is odd” case.f(n) = p , 1 + n – 12= p, 2 + n – 1 = 2p, n = 2p – 1Since p 2 N; we have 2p – 1 2 N and we are sure that any arbitrary p 2 N can be obtained with f. Therefore,ran f = N.f(2) = f(3) = 2, so f is not injective.5. (i) Suppose that f(x1) = f(x2). Thenx2 1 + 1 = x2 2 + 1 () x2 1 = x2 2 () x1 = x2 _ x1 = -x2:Since the domain of f is [0; 1), f is one-to-one. Note that there is no x 2 [0; 1) for which f(x) = x2 + 1 = 0.Therefore, f is not onto. If instead, we define f : [0; 1) ! [1; 1) then f is one-to-one and onto, and sof-1 : [1; 1) ! [0; 1) can be defined by f-1(y) = py2 – 1.(ii) Since f-1; 1g ⊆ dom f and f(1) = f(-1) = 1, f is not one-to-one. For each y > 0, py 2 R, satisfiesf(py) = y. Hence f is onto.(iii) Let x1; x2 2 (0; 1) such that f(x1) = f(x2). Then we havex11 – x1=x21 – x2() x1(1 – x2) = x2(1 – x1)() x1 – x1x2 = x2 – x1x2 () x1 = x2:Hence f is one-to-one. To show that f is onto, observe that for each y 2 (0; 1), x := 1+y y 2 (0; 1), the domainof f, such thatf(x) = f 1 +y y = 1 -1+y1+ yy y = y:Therefore, f is bijective.

QUALITY: 100% ORIGINAL PAPER – NO PLAGIARISM – CUSTOM PAPER

Leave a Reply

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