Network Science Quiz Questions by Jhonatan Cléto

Regarding the network shown above, which alternative is correct? A) The network is neutral, and the probability of a new edge forming between B and I is equal to that of a new edge forming between E and F. B) The network is assortative, and it is more likely for an edge to form between E and F than between B and I. C) The network is assortative, and it is more likely for an edge to form between B and I than between E and F. D) The network is disassortative, and the probability of a new edge forming between C and L is lower than that of a new edge forming between H and L. E) None of the above. Original idea by: Jhonatan Cléto

In the Ford–Fulkerson method, the bottleneck capacity of an augmenting path is usually defined as the minimum of the residual capacities of its edges. Suppose a path has two edges whose residual capacities vary with time \(t\), \(r_1(t) = t^2 + 1\) and \(r_2(t) = e^t\). Instead of taking the minimum, define the augmenting path capacity as the average of the residuals: \(R(t) = \frac{r_1(t) + r_2(t)}{2}\). What is the derivative \(\frac{dR}{dt}\) at \(t = 1\)? A) 1 B) 2.34 C) 2.72 D) 2.86 E) None of the above Original idea by: Jhonatan Cléto

Consider the following directed graph: I. The shortest path from A to J has length 5, and this is the longest among all shortest paths in the graph. II.  The number of cycles in the graph is exactly half the number of its strongly connected components. III.  If each strongly connected component is collapsed into a single node, there will be two possible topological orderings of the graph. IV.  If node D and all its incident edges are removed, and a new edge from B to E is added, the resulting graph will form a single strongly connected component. Which of the statements are  correct ? A) I, II, and III B) II and III C) Only III  D)  III and IV E) None of the above Original idea by: Jhonatan Cléto

Consider the following statements about detecting cycles using BFS: I. In an undirected graph , a cycle can be detected if BFS discovers an already visited node that is not the parent of the current node. II. In a directed graph , a cycle can be detected during BFS by encountering a node that is currently in the queue (i.e., discovered but not fully processed). III. BFS cannot be used for cycle detection in either directed or undirected graphs. IV. When used to test bipartiteness, BFS indirectly detects cycles of odd length if they exist. V. BFS can always detect cycles in a weighted graph, regardless of whether the weights are positive or negative. Which of the statements are correct ? A) I and II B) I, II and IV C) III and V D) Only IV E) None of the above Original idea by: Jhonatan Cléto