이산수학, 10장 11장 문제

21.

a. How many positive two-digit integers are multiples of 3?

 

b. What is the probability that a randomly chosen positive two-digit integer is a multiple of 3?

 

c. What is the probability that a randomly chosen positive two-digit integer is a multiple of 4?

 

12. How many cards must you pick from a standard 52-card deck to be sure of getting at least 1 red card? Why?

 

15.

a. How many even integers are in the set

{1,2,3,...,100}?

 

b. How many odd integers are in the set

{1,2,3,...,100}?

 

c. How many ways can two integers be selected from the

set{1,2,3,...,100}so that their sum is even?

 

d. How many ways can two integers be selected from the

set{1,2,3,...,100}so that their sum is odd?

 

5. If n is a positive integer, how many 4-tuples of integers from 1 through n can be formed in which the elements of the 4-tuple are written in increasing order but are not necessarily distinct?

In other words, how many 4-tuples of integers (i, j, k,m) are there with 1 ≤ i ≤ j ≤ k ≤ m ≤ n?

 

8. how many times will the innermost loop be iterated when the algorithm segment is implemented and run? Assume n, m, k, and j are positive integers.

 

for m := 1 to n

for k := 1 to m

for j := 1 to k

for i := 1 to j

[Statements in the body of the inner loop, none containing branching statements that lead outside the loop]

next i

next j

next k

next m

(i) Find all edges that are incident on v1.

(ii) Find all vertices that are adjacent to v3.

(iii) Find all edges that are adjacent to e1.

(iv) Find all loops.

(v) Find all parallel edges.

(vi) Find all isolated vertices.

(vii) Find the degree of v3.

(viii) Find the total degree of the graph

Determine which of the graphs have Euler circuits. If the graph does not have an Euler circuit, explain why not. If it does have an Euler circuit, describe one.

Find Hamiltonian circuits for each of the graphs in 23

either draw a graph with the given specifications or explain why no such graph exists.

10. Graph, circuit-free, nine vertices, six edges

15. Graph, circuit-free, seven vertices, four edges

21. Tree, ten vertices, total degree 24

 

23. A connected graph has nine vertices and twelve edges. Does it have a nontrivial circuit? Why?

 

26. If a graph has n vertices and n −2 or fewer edges, can it be connected? Why?

2. Consider the tree shown below with root v0.

a. What is the level of v8?

b. What is the level of v0?

c. What is the height of this rooted tree?

d. What are the children of v10?

e. What is the parent of v5?

f. What are the siblings of v1?

g. What are the descendants of v12?

 

3. Draw binary trees to represent the following expressions:

a. a·b −(c/(d +e)) b. a/(b −c·d)

find all minimum spanning

trees that can be obtained using (a) Kruskal’s algorithm and (b)

Prim’s algorithm starting with vertex a or t. Indicate the order

in which edges are added to form each tree.

Use Dijkstra’s algorithm to find the shortest path froma to z for the graph in 14. In each case make tables similar to

Table 10.7.1 to show the action of the algorithm.

18. Given any two distinct vertices of a tree, there exists a

unique path from one to the other.

a. Give an informal justification for the above statement.

✶ b. Write a formal proof of the above statement.