Consider the digraph G whose nodes are the integers from 1 to 12 inclusive and such that (i,j) is an arc if and only if i is a proper divisor of j . Write down the adjacency matrix representation of G and of the reversed graph Gr.
时间: 2024-02-23 17:02:39 浏览: 90
ford.c.zip_Single and Single
To write down the adjacency matrix of G, we need to determine whether there is a directed edge from each node i to each node j. In this case, there is a directed edge from i to j if and only if i is a proper divisor of j. The adjacency matrix A for G is therefore:
```
1 2 3 4 5 6 7 8 9 10 11 12
1 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 0 1 0 1 0 0 0 0 0 0
3 1 1 0 0 0 1 0 0 0 0 0 0
4 1 0 1 0 0 1 1 0 0 0 0 0
5 1 0 0 0 0 1 0 0 0 0 0 0
6 1 1 1 1 0 1 0 1 0 0 0 0
7 1 0 0 0 0 1 0 0 0 0 0 0
8 1 1 0 1 0 1 1 0 1 0 0 0
9 1 0 1 0 0 1 0 0 0 1 0 0
10 1 1 0 1 0 1 1 0 0 0 1 0
11 1 0 0 0 0 1 0 0 0 0 0 1
12 1 1 1 1 1 1 1 1 1 1 1 0
```
To write down the adjacency matrix of the reversed graph Gr, we need to determine whether there is a directed edge from each node i to each node j in Gr. In this case, there is a directed edge from i to j in Gr if and only if there is a directed edge from j to i in G. The adjacency matrix A' for Gr is therefore:
```
1 2 3 4 5 6 7 8 9 10 11 12
1 0 1 1 1 1 1 1 1 1 1 1 1
2 0 0 1 0 0 1 0 1 0 1 0 1
3 0 0 0 1 0 1 0 0 1 0 0 1
4 0 0 0 0 0 1 0 1 0 1 0 1
5 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 1 0 1 0 1
7 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 1 0
```
阅读全文