Math

What is Prim's algorithm used for?

• • A) Finding the longest path in a graph

• • B) Finding the minimum spanning tree

• • C) Finding the shortest path in a graph

• D) Finding all possible circuits in a graph
  

What is the first step in Prim's algorithm?

• • A) Start with an empty tree

• • B) Add the largest edge to the spanning tree

• • C) Add any edge to the tree

• D) Choose any edge with the smallest weight
  

In Prim's algorithm, when do you stop adding edges?

• • A) When there are no more edges left

• B) When n−1n - 1n−1 edges have been added

• • C) When the tree forms a circuit

• D) When all vertices are connected
  

Which of the following statements is true about Kruskal's algorithm?

• • A) It starts with any edge

• • B) It only adds edges incident to a vertex already in the tree

• • C) It starts with an empty graph and adds edges of minimum weight

• D) It only works for directed graphs
  

What is a key difference between Prim's and Kruskal's algorithms?

• • A) Prim's algorithm only works on directed graphs

• • B) Kruskal's algorithm adds edges that are incident to a vertex already in the tree

• • C) Prim’s algorithm only adds edges connected to vertices in the tree

• D) Kruskal’s algorithm cannot find the minimum spanning tree
  

In Kruskal's algorithm, how are edges chosen?

• • A) By adding the highest-weighted edges first

• • B) By adding edges only if they form a circuit

• • C) By adding edges of minimum weight that do not form a circuit

• D) By adding edges that form a cycle
  

What is the total weight of the minimum spanning tree in Example 8 (using Prim's algorithm)?

• • A) 22

• • B) 24

• • C) 25

• D) 26
  

What is the total weight of the minimum spanning tree in Example 9 (using Kruskal's algorithm)?

• • A) 24

• • B) 25

• • C) 26

• D) 28
  

In the context of spanning trees, what does it mean for a graph to have a "unique simple path" between any two vertices?

• • A) It has multiple paths between each vertex pair

• • B) It contains circuits between vertices

• • C) There is exactly one path between any two vertices

• D) It has no edges
  

According to the proof on trees, what property does a tree have if it is connected and has no circuits?

• • A) It contains parallel edges

• • B) It contains isolated vertices

• • C) It has a unique path between any two vertices

• D) It forms multiple loops