Question

question 1 - calculator active

(a) for the vertex-edge graph shown to the right, create the adjacency matrix. call it m. be sure to clearly label your matrix.

(b) for the digraph shown to the right, create the adjacency matrix. call it n.

(c) create matrix ( n^3 ). call this new matrix t.

find the value of ( t_{4,3} ). explain the meaning of your answer in the context of this situation.

-25 aqr unit 1 formative assessment 2
page

Answer:

Part (a) - Adjacency Matrix for Undirected Graph (Vertices: A, B, C, D, E)

Step 1: Identify Edges

• A to A: 2 (loop)
• A to B: 1
• A to C: 1
• A to E: 1 (wait, no, looking at the graph: A connected to A (2), A to B (1), A to C (1), A to E (1? Wait, the graph has A, B, C, D, E. Let's list all pairs:
• A: connects to A (2), B (1), C (1), E (1)? Wait, no, the original graph (undirected) has:
• A: loops (2), A-B (1), A-C (1), A-E (1)? Wait, maybe vertices are A, B, C, D, E (assuming E is the middle? Wait, the graph shows A, B, C, D, and a middle node E? Wait, the first graph (a) has nodes A, B, C, D, E (E is the middle). Let's list adjacency:
• A: A (2), B (1), C (1), E (1)
• B: A (1), B (2) (loop), C (1)
• C: A (1), B (1), C (0? No, wait, C to D (1), C to E (1)? Wait, maybe I mislabel. Let's re-express:

Wait, the correct way: for an undirected graph, adjacency matrix \( M \) is \( n \times n \) where \( n \) is number of vertices (A, B, C, D, E: 5 vertices). \( M_{i,j} \) is number of edges between vertex \( i \) and \( j \).

• A (row 1):
• A (col 1): 2 (loop)
• B (col 2): 1 (edge A-B)
• C (col 3): 1 (edge A-C)
• D (col 4): 0 (no edge A-D)
• E (col 5): 1 (edge A-E)
• B (row 2):
• A (col 1): 1 (edge A-B)
• B (col 2): 2 (loop)
• C (col 3): 1 (edge B-C)
• D (col 4): 0 (no edge B-D)
• E (col 5): 0 (no edge B-E)
• C (row 3):
• A (col 1): 1 (edge A-C)
• B (col 2): 1 (edge B-C)
• C (col 3): 0 (no loop)
• D (col 4): 1 (edge C-D)
• E (col 5): 1 (edge C-E)
• D (row 4):
• A (col 1): 0 (no edge A-D)
• B (col 2): 0 (no edge B-D)
• C (col 3): 1 (edge C-D)
• D (col 4): 0 (no loop)
• E (col 5): 0 (no edge D-E)
• E (row 5):
• A (col 1): 1 (edge A-E)
• B (col 2): 0 (no edge B-E)
• C (col 3): 1 (edge C-E)
• D (col 4): 0 (no edge D-E)
• E (col 5): 0 (no loop)

Wait, maybe my initial labeling was wrong. Let's check the graph again: the first graph (a) has nodes A, B, C, D, and E (the middle node). So edges:

• A: two loops (A-A), A-B, A-C, A-E
• B: two loops (B-B), B-A, B-C
• C: C-A, C-B, C-D, C-E
• D: D-C
• E: E-A, E-C

So correct adjacency matrix \( M \):

\[
M =

$$\begin{bmatrix} 2 & 1 & 1 & 0 & 1 \\ 1 & 2 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ \end{bmatrix}$$

\]

Part (b) - Adjacency Matrix for Digraph (Vertices: A, B, C, D, E)

For a digraph, \( N_{i,j} \) is number of directed edges from \( i \) to \( j \).

From the digraph:

• A (row 1):
• A: 2 (loops)
• B: 1 (A→B)
• C: 1 (A→C)
• D: 0 (A→D)
• E: 1 (A→E)
• B (row 2):
• A: 0 (B→A)
• B: 2 (loops)
• C: 1 (B→C)
• D: 0 (B→D)
• E: 0 (B→E)
• C (row 3):
• A: 1 (C→A)
• B: 1 (C→B)
• C: 0 (no loop)
• D: 1 (C→D)
• E: 1 (C→E)
• D (row 4):
• A: 0 (D→A)
• B: 0 (D→B)
• C: 1 (D→C)
• D: 0 (no loop)
• E: 0 (D→E)
• E (row 5):
• A: 1 (E→A)
• B: 0 (E→B)
• C: 1 (E→C)
• D: 0 (E→D)
• E: 0 (no loop)

Wait, no, looking at the digraph arrows:

• A: loops (2), A→B, A→C, A→E? Wait, the digraph has:

• A to A: 2 (loops)
• A to B: 1 (arrow A→B)
• A to C: 1 (arrow A→C)
• A to E: 1 (arrow A→E)
• B to B: 2 (loops)
• B to C: 1 (arrow B→C)
• C to A: 1 (arrow C→A)
• C to B: 1 (arrow C→B)
• C to D: 1 (arrow C→D)
• C to E: 1 (arrow C→E)
• D to C: 1 (arrow D→C)
• E to A: 1 (arrow E→A)
• E to C: 1 (arrow E→C)

So matrix \( N \):

\[
N =

$$\begin{bmatrix} 2 & 1 & 1 & 0 & 1 \\ 0 & 2 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ \end{bmatrix}$$

\]

Part (c) - Compute \( N^3 = N \times N \times N \)

First, compute \( N^2 = N \times N \), then \( N^3 = N^2 \times N \).

Step 1: Compute \( N^2 \)

Matrix multiplication: \( (N^2)_{i,j} = \sum_{k=1}^5 N_{i,k} \times N_{k,j} \)

Let's compute each row:

• Row 1 (A) of \( N \): [2, 1, 1, 0, 1]
• Column 1 (A) of \( N \): [2, 0, 1, 0, 1]
• \( 2*2 + 1*0 + 1*1 + 0*0 + 1*1 = 4 + 0 + 1 + 0 + 1 = 6 \)
• Column 2 (B) of \( N \): [1, 2, 1, 0, 0]
• \( 2*1 + 1*2 + 1*1 + 0*0 + 1*0 = 2 + 2 + 1 + 0 + 0 = 5 \)
• Column 3 (C) of \( N \): [1, 1, 0, 1, 1]
• \( 2*1 + 1*1 + 1*0 + 0*1 + 1*1 = 2 + 1 + 0 + 0 + 1 = 4 \)
• Column 4 (D) of \( N \): [0, 0, 1, 0, 0]
• \( 2*0 + 1*0 + 1*1 + 0*0 + 1*0 = 0 + 0 + 1 + 0 + 0 = 1 \)
• Column 5 (E) of \( N \): [1, 0, 1, 0, 0]
• \( 2*1 + 1*0 + 1*1 + 0*0 + 1*0 = 2 + 0 + 1 + 0 + 0 = 3 \)
• So Row 1 of \( N^2 \): [6, 5, 4, 1, 3]

• Row 2 (B) of \( N \): [0, 2, 1, 0, 0]
• Column 1 (A) of \( N \): [2, 0, 1, 0, 1]
• \( 0*2 + 2*0 + 1*1 + 0*0 + 0*1 = 0 + 0 + 1 + 0 + 0 = 1 \)
• Column 2 (B) of \( N \): [1, 2, 1, 0, 0]
• \( 0*1 + 2*2 + 1*1 + 0*0 + 0*0 = 0 + 4 + 1 + 0 + 0 = 5 \)
• Column 3 (C) of \( N \): [1, 1, 0, 1, 1]
• \( 0*1 + 2*1 + 1*0 + 0*1 + 0*1 = 0 + 2 + 0 + 0 + 0 = 2 \)
• Column 4 (D) of \( N \): [0, 0, 1, 0, 0]
• \( 0*0 + 2*0 + 1*1 + 0*0 + 0*0 = 0 + 0 + 1 + 0 + 0 = 1 \)
• Column 5 (E) of \( N \): [1, 0, 1, 0, 0]
• \( 0*1 + 2*0 + 1*1 + 0*0 + 0*0 = 0 + 0 + 1 + 0 + 0 = 1 \)
• So Row 2 of \( N^2 \): [1, 5, 2, 1, 1]

• Row 3 (C) of \( N \): [1, 1, 0, 1, 1]
• Column 1 (A) of \( N \): [2, 0, 1, 0, 1]
• \( 1*2 + 1*0 + 0*1 + 1*0 + 1*1 = 2 + 0 + 0 + 0 + 1 = 3 \)
• Column 2 (B) of \( N \): [1, 2, 1, 0, 0]
• \( 1*1 + 1*2 + 0*1 + 1*0 + 1*0 = 1 + 2 + 0 + 0 + 0 = 3 \)
• Column 3 (C) of \( N \): [1, 1, 0, 1, 1]
• \( 1*1 + 1*1 + 0*0 + 1*1 + 1*1 = 1 + 1 + 0 + 1 + 1 = 4 \)
• Column 4 (D) of \( N \): [0, 0, 1, 0, 0]
• \( 1*0 + 1*0 + 0*1 + 1*0 + 1*0 = 0 + 0 + 0 + 0 + 0 = 0 \)
• Column 5 (E) of \( N \): [1, 0, 1, 0, 0]
• \( 1*1 + 1*0 + 0*1 + 1*0 + 1*0 = 1 + 0 + 0 + 0 + 0 = 1 \)
• So Row 3 of \( N^2 \): [3, 3, 4, 0, 1]

• Row 4 (D) of \( N \): [0, 0, 1, 0, 0]
• Column 1 (A) of \( N \): [2, 0, 1, 0, 1]
• \( 0*2 + 0*0 + 1*1 + 0*0 + 0*1 = 0 + 0 + 1 + 0 + 0 = 1 \)
• Column 2 (B) of \( N \): [1, 2, 1, 0, 0]
• \( 0*1 + 0*2 + 1*1 + 0*0 + 0*0 = 0 + 0 + 1 + 0 + 0 = 1 \)
• Column 3 (C) of \( N \): [1, 1, 0, 1, 1]
• \( 0*1 + 0*1 + 1*0 + 0*1 + 0*1 = 0 + 0 + 0 + 0 + 0 = 0 \)
• Column 4 (D) of \( N \): [0, 0, 1, 0, 0]
• \( 0*0 + 0*0 + 1*1 + 0*0 + 0*0 = 0 + 0 + 1 + 0 + 0 = 1 \)
• Column 5 (E) of \( N \): [1, 0, 1, 0, 0]
• \( 0*1 + 0*0 + 1*1 + 0*0 + 0*0 = 0 + 0 + 1 + 0 + 0 = 1 \)
• So Row 4 of \( N^2 \): [1, 1, 0, 1, 1]

• Row 5 (E) of \( N \): [1, 0, 1, 0, 0]
• Column 1 (A) of \( N \): [2, 0, 1, 0, 1]
• \( 1*2 + 0*0 + 1*1 + 0*0 + 0*1 = 2 + 0 + 1 + 0 + 0 = 3 \)
• Column 2 (B) of \( N \): [1, 2, 1, 0, 0]
• \( 1*1 + 0*2 + 1*1 + 0*0 + 0*0 = 1 + 0 + 1 + 0 + 0 = 2 \)
• Column 3 (C) of \( N \): [1, 1, 0, 1, 1]
• \( 1*1 + 0*1 + 1*0 + 0*1 + 0*1 = 1 + 0 + 0 + 0 + 0 = 1 \)
• Column 4 (D) of \( N \): [0, 0, 1, 0, 0]
• \( 1*0 + 0*0 + 1*1 + 0*0 + 0*0 = 0 + 0 + 1 + 0 + 0 = 1 \)
• Column 5 (E) of \( N \): [1, 0, 1, 0, 0]
• \( 1*1 + 0*0 + 1*1 + 0*0 + 0*0 = 1 + 0 + 1 + 0 + 0 = 2 \)
• So Row 5 of \( N^2 \): [3, 2, 1,