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 vertex. Prove that the (i, j) entry of An, n > 1, is the number of different trails between i and j of length n in G. An denotes matrix multiplication of A with itself 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
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 vertex. Prove that the (i, j) entry of An, n > 1, is the number of different trails between i and j of length n in G. An denotes matrix multiplication of A with itself 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