Write an assignment about Discrete Structures in Computer Science

Prove that if G′ is a solution to the minimum network design problem then G′ is a tree

 

Order Now
SKU: assim10

1. Prove, using the induction on the number of elements n of set A, that there exactly kn functions from A  into a set B with exactly k elements

 

2. Let A be an n element set and B be a k element set with k < n. Prove the following:

(a) There is onto mapping from A to B.

(b) There is an injective mapping from B to A.

 

3. Let G = (V, E) be a weighted connected graph. Consider graphs of the form G′ = (V, E′ ) where E′ ⊆ E. The cost of such subgraph G′ is the sum of the weights of the edges in E′ . We want to build a subgraph G′ = (V, E′ ) such that G0 is connected and the cost of G′ is as minimum as possible. We call this the minimum network design problem.

Prove that if G′ is a solution to the minimum network design problem then G′ is a tree

 

4. Let B be the set of all strings over the alphabet {0, 1, 2}. Consider the function f : BB such that for any string x, the value f(x) is obtained by replacing all 0s in x by 1s, and all 1s in x by 2s, and all 2s in x by 0s. Is the function bijective? Explain your answer.

 

5. Consider the function f : Z² → Z²  defined as follows. For (x, y) ∈ Z² : if both x and y are even or both x and y are odd then f(x, y) = (x, y + 1); otherwise f(x, y) = (x + 1, y).

Prove that f is a bijective function.

 

6. Let f : ZZ be the function defined as: f(n) = (−1)n + n. Prove that f is a bijective function.

 

7. Let A and B be finite sets. Prove that if f : AB is a bijection, then A and B have the same number of elements

 

8. Assume that there is a path in graph G from vertex x to vertex y, where xy. Prove that there is a path from x to y such that no vertex in this path is repeated.

 

Reviews

There are no reviews yet.

Be the first to review “Write an assignment about Discrete Structures in Computer Science”

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

Sorry no more offers available