DSA Week 11

Which option contains the correct set of vertices and edges based on the provided graph on the screen?

• V = {0, 1, 2, 3}
  E = {(0, 1), (0, 2), (0, 3), (1, 2)}

• V = {1, 2, 3, 4}
  E = {(1, 2), (2, 4), (3, 4)}

• V = {1, 2, 3, 4}
  E = {(1, 2), (2, 3), (3, 4)}

• V = {1, 2, 3, 4}
  E = {(1, 2), (3, 4), (2, 3)}

Which option contains the correct set of vertices and edges based on the provided graph on the screen?

• V = {1, 2, 3, 4}
  E = {(1, 3), (1, 2), (2, 3), (3, 4)}

• V = {1, 2, 3, 4}
  E = {(1, 3), (2, 4), (3, 4), (1, 2)}

• V = {1, 2, 3, 4}
  E = {(1, 2), (2, 3), (3, 4), (1, 4)}

• V = {1, 2, 3, 4}
  E = {(1, 2), (3, 4), (1, 4), (2, 4)}

Based on the graph provided on the screen, which adjacency matrix is correct?

• 
• 
• 
• 

Based on the graph provided on the screen, which adjacency matrix is correct?

• 
• 
• 
• 

Based on the graph provided on the screen, which adjacency list is correct?

• 0 -> 3

  1 -> 2

  2 -> 1 -> 3

  3 -> 0 -> 2

• 0 -> 3

  1 -> 2

  2 -> 3

  3 -> 0

• 0 -> 3 -> 2 -> 1

  1 -> 2 -> 3 -> 0

  2 -> 3 -> 0

  3 -> 2 -> 1

• 0 -> 3 -> 2

  1 -> 2

  2 -> 3 -> 0

  3 -> 2

Based on the graph provided on the screen, which adjacency list is correct?

• 0 -> 2 -> 3

  1 -> 2

  2 -> 0 -> 1

  3 -> 0

• 0 -> 2 -> 3

  1 -> 0 -> 2

  2 -> 0 -> 1

  3 -> 0

• 0 -> 2

  1 -> 2

  2 -> 0 -> 1

  3 -> 0

• 0 -> 2 -> 3

  1 -> 2

  2 -> 0

  3 -> 0

What is the time complexity to find the number of in-edges for a single node X using an adjacency matrix?

• O(n²)

• O(n)

• O(n³)

• O(1)

What is the time complexity to find the number of in-edges for a single node X using an adjacency list, where k represents the total number of edges in the graph?

• O(n)

• O(k)

• O(n^k)

• O(kⁿ)

Which option INCORRECTLY represents the spanning tree based on the graph provided on the screen?

• 
• 
• 
• 

Which option correctly represents the spanning tree based on the graph provided on the screen?

• 
• 
• 
•