Traveling Salesperson Problem (TSP)

A dairy facility located in Itajubá/MG seeks to distribute its cheese products to the nearby cities of Pouso Alegre/MG, Santa Rita do Sapucaí/MG, and Paraisópolis/MG. The following graph illustrates the transportation costs between each municipality.

Applying the Traveling Salesperson Problem (TSP), which of the provided alternatives reflects the empirically most cost-effective route, commencing from Itajubá/MG (identified as the central vertex)?

A) 50

B) 55

C) 60

D) 75

E) None of the above

Original idea by: Jonas Henrique Ribeiro Paula

Degree Correlation Function

In a network, for nodes of degree \( k = 3 \), the conditional degree distribution of their neighbors is given by

\[p(k' = 1 \mid k = 3) = 0.50\]

\[p(k' = 2 \mid k = 3) = 0.30\]

\[p(k' = 5 \mid k = 3) = 0.20\]

What is the value of \( k_{nn}(3) \), i.e., the average degree of the neighbors of nodes with degree 3?

1. 1.8
2. 2.1
3. 3.0
4. 3.5
5. None of the above.

Original idea by Jonas Henrique Ribeiro Paula

Network Flow Question

The Central Student Directory of UNICAMP plans to organize a 5 Km race on the Barão Geraldo campus. To ensure safety, the campus administration has imposed restrictions on the number of students allowed on each campus street. To maximize registration opportunities, the administration modeled the campus streets as a directed graph with the capacity defined by the administration and applied the Ford-Fulkerson method to determine maximum flow. Regarding this method, consider the following statements:

1. The algorithm locates an augmenting path and modifies the flow on each edge according to its available residual capacity;
2. In each iteration, the flow increases along an augmenting path within the residual graph;
3. If integer capacities are used, the algorithm terminates after a finite number of iterations and yields an integer-valued maximum flow. 

Select the option that exactly list the correct statements:

1. I, II are correct.
2. I, III are correct.
3. II and III are correct.
4. I, II and III are correct.
5. None of the above.

Original idea by: Jonas Henrique Ribeiro Paula

Strongly Connected Components Question

A technical leader responsible for the software testing team intends to allocate a functional requirement to a team member who currently has no assigned tasks. For this assignment, the objective is to select a functional requirement that does not have strong dependencies on other requirements. Therefore, the leader chose to use the Kosaraju-Sharir algorithm to identify the Strongly Connected Components composed of only a single vertex, starting from FR01, as represented in the directed graph shown in the image below:

Accordingly, which functional requirement was assigned to the team member for testing?

    A. FR01

    B. FR03

    C. FR07

    D. FR09

    E. None of the above

Original idea by: Jonas Henrique Ribeiro Paula

BFS Question

Within an intelligence organization, secret agents transfer coded publications through designated post office boxes. For enhanced security, each agent is permitted knowledge of the post office box locations assigned to no more than two other agents.

• If an agent intends to transmit a message to another agent, they should deliver the magazine directly to the recipient’s post office box. Alternatively, if the agent does not possess the specific address, the magazine should be sent to all known agents for whom addresses are available.
• Upon receipt of the magazine by an agent who identifies themselves as not the intended recipient, it is their responsibility to forward the magazine to all agents whose addresses they have.
• Prioritization rule: always send/forward it first to the agent with the lowest number among the known addresses.

The graph below represents the agents who know each other's addresses.

We can calculate the fewest number of magazine sends/forwards using Breadth First Search (BFS). Based on the connections between agents, which of the following is FALSE regarding the distance calculated with BFS?

a) The distance between agent 001 to 005 is 3

b) The distance between agent 002 to 001 is 4

c) The distance between agent 003 to 002 is 1

d) The distance between agent 007 to 005 is 5

e) None of the above

Original idea by: Jonas H. Ribeiro Paula