Quiz question 07

In the context of the Traveling Salesperson Problem (TSP), what is the main objective when seeking a solution in a weighted, undirected graph?

a.) Determine the shortest path between two specific vertices $u$ and $v$.

b.) Find a path that visits all vertices at least once with the lowest total weight.

c.) Identify the minimum spanning tree (MST) that connects all nodes in the graph.

d.) Find a cycle that contains all vertices, does not repeat any of them, and has the minimum total weight.

e.) None of the above

Original idea by: Julia de Pietro Bigi

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Quiz question 01

Imagem
Consider the following network: Which statements are TRUE or FALSE? 1. The degree distribution of this network would generate a graph with equal values of pk for k values.  2. If link (4-5) were to be removed, then the network would have 2 components. This makes the connection between nodes 4 and 5 to be called a bridge. 3. Considering node 4 as the zero node, the diameter of this network is dmax = 4. 4. The degrees of the two mostl connected nodes are equivalent to 2/3 and 1.  a.) T F F T b.) F F T T c.) T T F T  d.) F T T F  e) None of the above Original idea by: Julia de Pietro Bigi
Leia mais

Quiz question 02

What do BFS and DFS have in common? What about their differences?  a.) Common: They both use an adjacency list as input. Both of them can be used to calculate distances and classify edges. Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a given node, so not necessarily the entire tree will be visited. b.) Common: they both use an adjancency list and starting + ending times of node's visits as input.  Differences: BFS can be used to calculate distances and finding connected components. While DFS can be used to detect cycles and classify edges.  c.) Common: they both use an adjancency list as input.  Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a giving node, so not necessarily the entire tree will be visited.  d.) Common: they both need an adjancency list ...
Leia mais

Quiz question 05

Imagem
According to Kuratowski’s Theorem, for connected and planar networks, the number of vertices minus the number of edges plus the number of faces equals 2. This is Euler’s Formula, where:  V - E + F = 2.  Considering that faces are the regions bounded by links and that there will always be an outer face, given the following situations, how would Euler’s Formula behave? Scenario 01: a single node A.  Scenario 02: addition of a node B with a link to this existing node A. Scenario 03: addition of another node C with a link to the existing node A.  Scenario 04: addition of a link between nodes B and C.  a.) Euler’s formula remains constant (equal to 2) in scenarios 01 and 02.  b.) Euler’s formula remains constant (equal to 2) in all scenarios. c.) Euler’s formula depends on the number of nodes; therefore, it takes on a different value for each scenario: Scenario 01 = 2; Scenario 02 = 2; Scenario 03 = 3; and Scenario 04 = 3 d.) Euler’s formula depends on the nu...
Leia mais