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 question 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

2025-282

A large, undirected network, with no self-loops or multi-links, is analyzed. It exhibits a scale-free degree distribution described by the formula \(p(k) = k^\gamma\) with an exponent \(\gamma=2.5\). Empirical measurement yields a degree correlation coefficient \(r = -0.15\). A plot of the average nearest-neighbor degree \(k_{nn}(k)\) shows relatively independency of the degree \(k\) for small \(k\), but it begins to decay for nodes with \(k > \sqrt{\langle k\rangle N}\), where \(N\) is the network size. What is the most precise classification of this network's degree correlations?

A)  The network is intrinsically disassortative;

B) The network exhibits structural disassortativity, a phenomenon affecting scale-free networks with exponent \(\gamma < 3\) and the network's nature;

C) The network is neutral, as the average nearest-neighbor degree is independent of \(k\) for most nodes and \(r\) is close to 0;

D) The network is assortative, but the measurement is skewed by the high variance of high-degree nodes;

E)  None of the above.

Original idea: Caio Rhoden

2025-281

Classify the following statements as true or false, regarding degree correlation properties in networks:

I: For Erd\H{o}s-Rényi, assortative networks, the transition to a giant component takes longer, as hubs preferentially connect to each other.

II: For a disassortative network, the degree correlation function knn (k) increases with k.

III: Structural disassortativity is a phenomenon observed in scale-free networks where γ < 3, which arises because the network lacks a sufficient number of links to connect the large hubs in a neutral way.

IV: Assortative, random networks have a shorter average path length than random neutral networks, but also a larger network diameter.

Now choose the alternative that agrees with the classifications of statements I to IV, in this order:

A) T-F-T-T

B) T-F-F-F

C) F-F-T-T

D) T-F-F-T

E) None of the above

Original idea by: Alexandre Petrachini

2025-280

Consider networks generated by the following models:

• Barabási-Albert model
• Erdős-Rényi model

With regard to the degree correlations, the generated networks are, with high probability, respectively:

A. Disassortative and Disassortative

B. Disassortative and Neutral

C. Neutral and Disassortative

D. Neutral and Neutral

E. None of the above

Original idea by: Jhessica Silva

2025-279

Consider that the following network obeys the Barabási–Albert model, assess each statement from I to V regarding probabilities of receiving a link, and then mark the correct alternative. Round probability values to two decimal places.

I) Node M is the node with the highest probability of receiving a link from a new node, of 0.13.

II) Node D is the node with the second highest probability of receiving a link from a new node, of 0.10.

III) Nodes A, C, L, P, and I have the same probability of receiving a new link, of 0.02.

IV) Nodes N and E have the same probability of receiving a new link, of 0.08.

V) Nodes H and D have different probabilities of receiving a new link, of 0.08 and 0.09 respectively.

Which alternative contains the truth values of the above statements in the correct order?

A) F F T T F

B) T F T T F

C) T T F F T

D) T F T F T

E) None of the above

Original idea by: Carolina Albuquerque

2025-278

Consider a network with 4 nodes (1, 2, 3, 4) and the following 5 edges: (1, 2), (1, 3), (2, 3), (2, 4), (3, 4). What is the average nearest neighbor degree for nodes of degree \(k=3\), denoted by \(k_{nn}(3)\)?

1. 2.5
2. 3.0
3. 2.67
4. 2.33
5. None of the above

Original ideia by: Gabriel Sato