2023-227

Consider a flow network for the company "A", which needs to deliver products from the capital to 10 cities. Three of these cities are small and don't have direct delivery routes from the capital. However, each of these small cities can receive products from the other 7 cities.

Due to a special event, City "T", one of the three small cities, requires a delivery of 650 products. The flow capacities of the network are defined as follows:

• Company "A" can send a maximum of 150 products to each city that has a direct connection from the capital.
• Two of the 7 cities that can receive products directly from the capital can forward a maximum of 200 products each to City "T".
• The remaining 5 of the 7 cities can forward a maximum of 50 products each to City "T".
• The other two small cities don't require any products.

Given these conditions, how many of the 650 requested products can be delivered to City "T" for the event?

1. 500
2. 550
3. 600
4. 650
5. None of the above

Original idea by: Thaysa Bello

2023-226

 

Imagine a Cayley Tree, constructed starting from a central node of degree \( k \). Each node at distance \( d \) from the central node has degree \( k \), until the nodes reachable at distance \( P \) that have degree one, as shown in figure above. Consider \( k+1 \) communities, with communities corresponding to the subtrees rooted at the children of the central node, and the central node by itself being a community. What is the modularity of this partition if \( k=3 \) and \( P=4 \)? Round it up to three decimal places.

1. 0.523
2. 0.621
3. 0.785
4. 0.891
5. None of the above.

Original idea by: Germán Darío Buitrago Salazar

2023-225

Agglomerative hierarchical clustering can be applied to community detection in graphs. By using dendrograms, one can visualize the order in which nodes merged. This visualization enables the extraction of the underlying community organization.

Which of the presented dendrograms and respective cuts would faithfully represent the given graph and its three colored communities?

1. IV;
2. III;
3. II;
4. I;
5. None of the above.

Original idea by: Fillipi Valadares

2023-224

Consider the following network. The fuchsia nodes are all part of a weak community.

Which option presents a modification that makes this community a strong one?

1. Remove node 8 from the community.
2. Add node 9 to the community.
3. Add node 5 to the community.
4. Remove node 6 from the community.
5. None of the above

Original idea by: Christian Konishi

2023-223

Considering the following undirected graph:

I. {1, 2, 3, 4} is a clique.

II. {1, 2, 3, 4} is a strong community.

III. {5, 6, 7} is a weak community.

IV. {5, 6, 7} is a clique.

V. {4, 5, 6, 7} is a weak community.

Which statements from the options above are correct?

1. I, III and V
2. II, III and V
3. II, IV and IV
4. II, III, IV and V
5. none of above

Original idea by: Anderson Nogueira Cotrim