Chapter 10

Verify Theorem 10.1 using Exercise 2

How many edges does a dominance digraph with \(n\) vertices have?

Let \(A=\left(a_{i j}\right)\) be the adjacency matrix of a digraph with \(n\) vertices. Then \(D\) is a dag if and only if the main diagonal of the boolean matrix \(R=\) \(A \vee A^{|2|} \vee \cdots \vee A^{|n|}\) is zero. Using this fact, determine if the digraphs are dags.

Let \(A=\left(a_{i j}\right)\) be the adjacency matrix of a digraph with \(n\) vertices. Then \(D\) is a dag if and only if the main diagonal of the boolean matrix \(R=\) \(A \vee A^{|2|} \vee \cdots \vee A^{|n|}\) is zero. Using this fact, determine if the digraphs are dags.

A row of the adjacency matrix of a digraph is zero. Prove that the digraph is not strongly connected.

A column of the adjacency matrix of a digraph is zero. Prove that the digraph is not strongly connected.

Construct the de Bruijn sequence for binary couplets.

Is a strongly connected digraph also weakly connected?

Using the adjacency matrix of a weakly connected digraph with vertices 1 through \(n,\) what can you say about each vertex, where \(1 \leq i, j \leq n ?\) Vertex \(i\) if row \(i\) is zero.

Using the adjacency matrix of a weakly connected digraph with vertices 1 through \(n,\) what can you say about each vertex, where \(1 \leq i, j \leq n ?\) Vertex \(j\) if column \(j\) is zero.

Using Dijkstra's algorithm, find a shortest path and its length from vertex \(a\) to the other vertices. $$\left.\begin{array}{c|cccccc} & a & b & c & d & e & f \\ a & \infty & 3 & 5 & \infty & \infty & \infty \\ b & \infty & \infty & \infty & 2 & \infty & \infty \\ c & \infty & \infty & \infty & 3 & \infty & \infty \\ d & 4 & \infty & \infty & \infty & 3 & 6 \\ e & \infty & 5 & \infty & \infty & \infty & \infty \\ f & \infty & \infty & 4 & \infty & \infty & \infty \end{array}\right]$$

Using the adjacency matrix of a weakly connected digraph with vertices 1 through \(n,\) what can you say about each vertex, where \(1 \leq i, j \leq n ?\) Construct the de Bruijn sequence for binary couplets.

Using the adjacency matrix of a weakly connected digraph with vertices 1 through \(n,\) what can you say about each vertex, where \(1 \leq i, j \leq n ?\) Construct the memory wheel for binary couplets.

One of the two distinct de Bruij sequences for binary triplets is 01110100 . Find the other de Bruijn sequence.

One of the two distinct de Bruijn sequences for binary triplets is 01110100. Find the other de Bruijn sequence.

One of the two distinct de Bruij sequences for binary triplets is 01110100 . List the binary triplets resulting from it.

One of the two distinct de Bruijn sequences for binary triplets is 01110100. List the binary triplets resulting from it.

One of the two distinct de Bruij sequences for binary triplets is 01110100 . Construct a de Bruijn sequence for binary quadruplets, (There are 16 different sequences.)

One of the two distinct de Bruijn sequences for binary triplets is 01110100. Construct a de Bruijn sequence for binary quadruplets. (There are 16 different sequences.)

Suppose de Bruijn Hotel has 16 guest rooms. Each guest receives a three bit code to enter his room. Each door has a keypad with two push buttons, one for 0 and the other for \(1 .\) When the correct sequence of the four bits is entered, regardless of what bit was entered earlier, the door will open. Suppose a burglar wishes to enter a room. Find the minimum number of bits he needs to enter to be certain that the door will open.

Prove each. The vertices of a dag can be topologically sorted. (Hint: Use induction.)

In \(1934, \mathrm{M}\) . H. Martin developed an algorithm for constructing a de Bruijn sequence for binary n-tuples. Begin with the \(n\) -bit word consisting of all O's. Successively append the larger of the bits 0 and 1 that does not lead to a duplicate \(n\) -tuple. Using this method, construct a de Bruijn sequence for each. Binary couplets

In \(1934,\) M. H. Martin developed an algorithm for constructing a de Bruijn sequence for binary \(n\) -tuples. Begin with the \(n\) -bit word consisting of all 0's. Successively append the larger of the bits 0 and 1 that does not lead to a duplicate \(n\) -tuple. Using this method, construct a de Bruijn sequence for each. Binary couplets

In \(1934, \mathrm{M}\) . H. Martin developed an algorithm for constructing a de Bruijn sequence for binary n-tuples. Begin with the \(n\) -bit word consisting of all O's. Successively append the larger of the bits 0 and 1 that does not lead to a duplicate \(n\) -tuple. Using this method, construct a de Bruijn sequence for each. Binary triplets

In \(1934,\) M. H. Martin developed an algorithm for constructing a de Bruijn sequence for binary \(n\) -tuples. Begin with the \(n\) -bit word consisting of all 0's. Successively append the larger of the bits 0 and 1 that does not lead to a duplicate \(n\) -tuple. Using this method, construct a de Bruijn sequence for each. Binary triplets

In \(1934, \mathrm{M}\) . H. Martin developed an algorithm for constructing a de Bruijn sequence for binary n-tuples. Begin with the \(n\) -bit word consisting of all O's. Successively append the larger of the bits 0 and 1 that does not lead to a duplicate \(n\) -tuple. Using this method, construct a de Bruijn sequence for each. Binary quadruplets

In \(1934,\) M. H. Martin developed an algorithm for constructing a de Bruijn sequence for binary \(n\) -tuples. Begin with the \(n\) -bit word consisting of all 0's. Successively append the larger of the bits 0 and 1 that does not lead to a duplicate \(n\) -tuple. Using this method, construct a de Bruijn sequence for each. Binary quadruplets