2022-190

Consider the flow network below with source 1 and sink 10, where the capacities are shown besides each link.

Select the correct alternative containing the maximum flow through this network and possible flow values from node 1 to nodes 2, 4, and 3, respectively, in a max flow solution.

1. The maximum flow of the network is 19 and the flow values from node 1 are 8, 5, and 9.
2. The maximum flow of the network is 18 and the flow values from node 1 are 7, 5, and 6.
3. The maximum flow of the network is 20 and the flow values from node 1 are 7, 5, and 8.
4. The maximum flow of the network is 19 and the flow values from node 1 are 7, 5, and 7.
5. None of the above.

Original idea by: Rubens de Castro Pereira

2022-189

Goods are transported by trucks from two orchards to three retailers. Some of the orchards cannot ship directly to some of the retailers. The capacities of the routes are limited by the number of trucks available and the number of trips made daily.  The following table shows in the margins the daily amounts of supply at the orchards and demand at the farms. The cell entries of the table specify the daily capacities of the associated routes.  All figures are in number of container boxes.

Determine the maximum amount of container boxes that can be shipped daily from orchards to retailers.

A. 24

B. 10

C. 54

D. 17

E. None of the above.

Original idea by: Muhammad Idrees

2022-188

Consider the flow network in the figure, where s and t are the source and sink, respectively, with an initial flow though paths in blue and red. Choose the alternative with the pair of augmenting paths that together push the largest amount of flow in the corresponding residual graph.

1. s-A-C-F-H-D-t and s-E-C-F-H-D-t
2. s-A-C-D-t and s-E-C-F-H-D-t
3. s-E-G-I-t and s-A-C-E-G-I-t
4. s-A-C-F-H-t and s-E-C-B-D-t
5. None of the above.

Original idea by: Lucca Bavia

2022-187

What is the maximum flow from S to T in the network from Figure 1?

Fig. 1: A flow network.

1. 19.
2. 20.
3. 21.
4. 22.
5. None of the above.

Original idea by: Gabriel Oliveira

2022-186

Applying a divisive algorithm on the network below, we obtain the following dendrogram:

Network 

Dendrogram

Looking at the dendrogram, we establish two cuts creating community partitions. Which partition yields better communities and why? (Values are rounded to 2 decimal places).

1. A, because its modularity is equal to 0.36
2. A, because its modularity is equal to 0.45
3. B, because its modularity is equal to 0.36
4. B, because its modularity is equal to 0.45
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

2022-185

The generalized modularity \( M \) of a network with \( L \) links partitioned into \( n_c \) communities can be calculated as:

$$M = \sum_{c=1}^{n_c}\left[\frac{L_c}{L}-\left(\frac{k_c}{2L}\right)^2\right]$$

where \( L_c \) is the total number of links within the community \( C_c \) and \( k_c \) is the total degree of the nodes in this community. Consider the following statements about \( M \):

1. Higher values of \( M \) correspond to better community structures.
2. \( M = 0 \) when the entire network is taken as a single community.
3. \( M \) cannot be negative.
4. \( M \) cannot exceed one.

What is correct to assert:

1. Only I is true
2. I, II, and III are true
3. I, II, and IV are true
4. I and II are true, III and IV are false
5. None of the above

Original idea by: Marcelo Silva

2022-184

 

Given the graph below, where each color represents a different partition, calculate the modularity value. Round it up to two decimals places.

 

 

1. 0.12
2. 0.26
3. 0.37
4. 0.41
5. None of the above.

Original idea by: André Nóbrega