Discrete Mathematics for Computer Science

416 CHAPTER 6 Graph Theory

14. Topologically sort D.

5

4 6

3 7

2

8

D

15. Prove that G contains no Hamiltonian cycle.

G

16. Let A be the adjacency matrix of a graph G = (V, E) with V = {1, 2 ... n}. Prove

that the sum of the entries in any column is the degree of the corresponding ver-

tex. Prove that the (i, j) entry of An, n > 1, is the number of different trails be-

tween i and j of length n in G. An denotes matrix multiplication of A with it-

self n times. For A, a 3 x 3 matrix, define A • A to have (i, j)th entry equal to

_k=1 aik "akj.

6.21.4 Using Discrete Mathematics in Computer Science

1. A vertex in a directed graph that has an indegree of zero is called a transmitter Identify
   the transmitters in D. Devise a strategy for spreading a rumor so that all the nodes of
   the graph, which can be thought of as people on the ends of telephone lines, know the
   rumor.
   c d

a b

g f

D