2026-360

Sophia is collecting stickers for the 2026 World Cup album. To complete her collection, she plans to leave home (V0), visit all the sticker exchange points (V1, V2, V3, V4) in the city of Campinas exactly once, and then return home. The figure below shows a weighted adjacency matrix of an undirected graph.

	V0	V1	V2	V3	V4
V0	0	14	16	0	0
V1	14	0	11	12	14
V2	16	11	0	14	17
V3	0	12	14	0	15
V4	0	14	17	15	0

• each vertex (V) represents a sticker exchange point; 
• each link represents the possibility of traveling between two points; 
• the weight of each edge represents the amount Sophia will spend in R$ when taking that route; 
• there is only a connection between two vertices when the weight shown in the matrix is greater than zero. 

Considering this information, help Sophia choose a route where she visits all the sticker exchange points exactly once, returns home, and has the lowest possible total cost.

What is the minimum-cost cycle for Sophia? 

a) V0 -> V1 -> V2 -> V3 -> V4 -> V1 -> V0.

b) V0 -> V1 -> V3 -> V4 -> V2 -> V0.

c) V0 -> V2 -> V1 -> V3 -> V4 -> V1 -> V0.

d) V0 -> V2 -> V3 -> V4 -> V1 -> V0.

e) None of the above.

Original idea by: Tássia Martins

2026-358

Consider a Euclidian TSP with 5 cities located in a 2D plane at the following coordinates:

A (1, 2); B (5, 3); C (6, 7); D (2, 8); E (4, 5).

A delivery starts at city A and uses Nearest Neighbor Heuristic to construct a complete tour. Which alternative represents the total distance (cost) of the resulting tour, rounded to two decimals?

a) 13.31

b) 17.16

c) 15.52

d) 19.39

e) None of the above

Original idea by: Matheus Rufino

2025-288

A Flamengo fan living in Campinas made a promise that if their team reached the final of the 2025 Libertadores de America Cup, they would visit all the stadiums where Flamengo played during the knockout stages. Now that Flamengo has indeed made it to the final, the fan must fulfill their promise before returning home to Campinas to catch a flight to Lima for the final.

To plan the most efficient route, the fan created a simplified map in the form of a graph, where each node represents a stadium and each edge is weighted by the distance between stadiums. Using the Cheapest Insertion heuristic, they determined their itinerary.

What is the total distance to be covered on this journey?

A) 4085 Km

B) 4135 Km

C) 4140 Km

D) 5815 Km

E) None of the above

Original idea by: Eduardo Bouhid

2025-287

Considering the Traveling Salesman Problem (TSP) in a complete graph where the triangular inequality holds, which of the following statements most accurately describes the fundamental difference in tour construction and performance guarantee between the Rosenkrantz-Stearns-Lewis algorithm and the Christofides algorithm?

1. Both algorithms are based on the "Farthest Insertion" heuristic, but Christofides applies additional optimization using dynamic programming to achieve a 1.5 x optimal cost guarantee, while Rosenkrantz-Stearns-Lewis does not.


2. Christofides' algorithm uses minimum perfect matching over the odd degree nodes of the minimum spanning tree (MST) to construct an Eulerian graph, achieving an approximation guarantee of 1.5 x optimal cost. In contrast, the Rosenkrantz-Stearns-Lewis algorithm duplicates all edges of the MST, resulting in a guarantee of 2 x optimal cost.


3. The Rosenkrantz-Stearns-Lewis algorithm duplicates the edges of the MST to form an Eulerian tour, and the Christofides algorithm improves on this by finding a minimum perfect match on all nodes in the graph (not just those of odd degree), but both algorithms share the same 2 x cost-optimal performance guarantee.


4. The Rosenkrantz-Stearns-Lewis algorithm uses a minimum perfect match over the odd degree nodes of the MST, achieving a 1.5 x optimal cost guarantee, while the Christofides algorithm duplicates all MST edges, achieving a 2 x optimal cost guarantee.


5. None of the above.

Original idea by: Juan Jose Rodriguez Rodriguez

2025-286

The Euclidean Traveling Salesman Problem (Euclidean TSP) is a special case of the symmetric TSP where each city corresponds to a point in \(\mathbb{R}^d\) and costs equal the Euclidean distance between points. As the Euclidean distance is symmetric and satisfies the triangle inequality, Euclidean TSP is a special case of Metric TSP, allowing approximation algorithms to be used for a solution.

Consider the Euclidean TSP on 5 cities, located in \(\mathbb{R}^2\) at

A (0, 0); B (2, 0); C (2, 1); D (0, 1); E (1, 1).

Which of the following statements is true?

1. The Nearest Neighbor heuristic starting from any node always yields a tour of cost 6.
2. Any Euclidean TSP can be solved in polynomial time using the ILP formulation.
3. The optimal tour is achieved by ABCED, costing 5.
4. The Cheapest Insertion heuristic is better than the Nearest Neighbor for any starting single-node cycle. 
5. None of the above

Original idea by: Daniel Gardin

2025-285

The graph below is an input instance for the Traveling Salesperson Problem showing the weight of each link between nodes. Considering that links not shown have infinite weight, find the correct alternative.

a) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-c-d-f-e-b-a, with a total cost of 19.

b) Using the Closest Neighbor heuristic, any starting node will result in a total cost of 16.

c) Using the Cheapest Insertion heuristic, starting from the cycle a-b-c-a will result in a final cost of 16.

d) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-b-e-c-d-f-a, with a total cost of 16.

e) None of the above.

 

 Original idea by: Giorgio Rossa

2025-284

Solve the Travel Salesperson Problem for the following undirected weighted graph and pick the best answer:

A) Cycle ABCDEA with weight 24

B) Cycle ABCEDA with weight 20

C) Cycle ADEBCA with weight 18

D) Cycle AEBCDA with weight 19

E) None of the above

Original idea by: Raphael Adamski

2025-283

A post office must plan a route to visit five cities (A, B, C, D, E) and return to the start. Distances (cost units) are given in the graph below. The graph satisfies the triangle inequality and is undirected. Apply the cheapest insertion heuristic (from the traveling salesperson problem), starting with triangle ABC (initial cycle: A → B → C → A). At each step, insert the vertex that yields the smallest cost increase according to the cheapest insertion heuristic. Which final cycle is obtained and what is its total cost?

A) A → C → B → D → E → A, total cost 29

B) A → B → E → D → C → A, total cost 27

C) A → B → D → C → E → A, total cost 25

D) A → D → B → E → C → A, total cost 27

E) None of the above

Original idea by: Thiago Soares Laitz

2022-122

A traveling salesperson wants to use the Farthest Insertion algorithm to build a route map for their next trip. Consider the cities below and the cycle BDE as the initial route.

Which alternative represents a possible order of cities (nodes) addition:

 

A) GCFA

B) ACGF

C) FGCA

D) AFCG

E) None of the above



Original idea by: Iury Cleveston