Problem 14 - Discrete Mathematics with Applications

Question

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.

Step-by-Step Solution

Answer

To determine if a digraph is a Directed Acyclic Graph (DAG), follow these steps: 1. Compute the powers of the adjacency matrix A from \(A^2\) up to \(A^n\), where n is the number of vertices. 2. Create the boolean matrix R by performing an OR (\(\vee\)) operation on each power of A up to the nth power: \(R(A)_{ij} = A_{ij} \vee (A^2)_{ij} \vee \cdots \vee (A^n)_{ij}\). 3. Examine the main diagonal elements of R. If all \(R_{ii}=0\), the digraph is a DAG; otherwise, it is not. Apply these steps to the adjacency matrix A of a given digraph to determine if it is a DAG.

Step 1: Compute the powers of the adjacency matrix

Compute the powers of the adjacency matrix for the given digraph from \(A^2\) up to \(A^n\), where n is the number of vertices.

Step 2: Create the boolean matrix R

Using the computed powers of the adjacency matrix, create the boolean matrix R by performing an OR (\(\vee\)) operation on each power of the adjacency matrix up to the nth power. In other words, for each pair of indices (i, j), compute \(R(A)_{ij} = A_{ij} \vee (A^2)_{ij} \vee \cdots \vee (A^n)_{ij}\).

Step 3: Check the main diagonal elements of R

After computing the boolean matrix R, examine its main diagonal elements. If all the elements in the main diagonal (i.e., elements with indices \(R_{ii}\)) are zero, then the given digraph is a Directed Acyclic Graph (DAG); otherwise, it is not. To apply these steps to specific digraphs, we would need the adjacency matrix A for each digraph. Unfortunately, there are no specific digraphs provided in the given exercise. However, assuming we have an adjacency matrix A for a given digraph, the steps mentioned above can be performed to determine if the digraph is a DAG or not.