DISCRETE MATHEMATIC 1 Show that each of the following sets i

DISCRETE MATHEMATIC

1) Show that each of the following sets is countable:

a) set of negative integers;
b) set of integers that are multiples of 5;

For a) and b) write the one to one correspondence between
Z+ and the specified set.

2) R is the set of real numbers. Let T = { xR | 5 < x < 11 }.
Show that the set T is not countable.
Hint: Find a function that maps interval (0,1) R into the
interval (5,11 R.

For questions 3,4 draw graphs with specified properties
or explain why no such graph exists.

3) Graph with 4 vertices of degrees 1,2,3,4.
4) Graph with 5 vertices of degrees 1,2,3,3,5.

For questions 5,6 determine which graphs are bipartite.
Redraw the ones that are bipartite graphs to show their
bipartite nature.

5)                                             6)

7) Use Dijkstra\'s algorithm to find the length of the shortest path
between vertices a and z. Show each step of the calculations.

Solution

1)

a) the set of negative integers is countable because we can map one to one correspondence with natural numbers to it.

(Z⁺ ) -N

1 -1

2 -2

3 -3

etc

b) set of integers that are multiples of 5 is also countable.

N(Z⁺ ) 5N

1 5

2 10

3 15

etc

set of positive integers(Z⁺) mens N.

2) for the interval (0,1) there are many decimal numbers with infinite number of digits

like this for the interval (5,11) also infinite number of digits will come.

therefore it is uncountable.

3) here n=4 vertices then if degree of one vertex is 4 then there is no possible for the vertex with degree 1

so graph construction is not possible.

4) here n=5 vertices then if degree of one vertex is 5 then there is no possible for the vertex with degree 1

so graph construction is not possible.

for 5,6,7 images are not downloaded.