Quiz - MO412 - Julia Pietro

Considering a scale-free network, where $$P(k) \sim k^{-\gamma}$$, and the critical threshold is given by: $f_{c} = 1 - \frac{1}{\frac{\langle k^{2} \rangle}{\langle k \rangle} - 1}$ For a network where $2 < \gamma < 3$ and another where $\gamma > 3$, select the correct alternative. a.) For $2 < \gamma < 3$, the second moment tends to zero and the value of $f_{c}$ tends to zero, indicating extreme fragility to random failures. b.) For $\gamma > 3$, the second moment diverges, making the network completely robust.  c.) For $2 < \gamma < 3$, the second moment diverges and $f_{c}$ tends to 1, indicating that the network can sustain the random removal of almost all nodes without losing the giant component. d.) The value of $f_{c}$ is independent of the exponent $\gamma$, depending only on the network size $N$. e) None of the above Original idea by: Julia de Pietro Bigi

According to Kuratowski’s Theorem, for connected and planar networks, the number of vertices minus the number of edges plus the number of faces equals 2. This is Euler’s Formula, where:  V - E + F = 2.  Considering that faces are the regions bounded by links and that there will always be an outer face, given the following situations, how would Euler’s Formula behave? Scenario 01: a single node A.  Scenario 02: addition of a node B with a link to this existing node A. Scenario 03: addition of another node C with a link to the existing node A.  Scenario 04: addition of a link between nodes B and C.  a.) Euler’s formula remains constant (equal to 2) in scenarios 01 and 02.  b.) Euler’s formula remains constant (equal to 2) in all scenarios. c.) Euler’s formula depends on the number of nodes; therefore, it takes on a different value for each scenario: Scenario 01 = 2; Scenario 02 = 2; Scenario 03 = 3; and Scenario 04 = 3 d.) Euler’s formula depends on the nu...

Consider that on Easter Sunday, due to high demand, airlines had to limit the number of planes that could fly over certain regions. Help Azul Airlines maximize the number of planes that could travel on April 4, 2026, at 2 PM, through the areas shown in the figure below. What would be the residual network formed from the networks in Figure 2?  SP is the source node and AM is the sink node.  1: 2:  a.)  b.)  c.)  d.)  e) None of the above Original idea by: Julia de Pietro Bigi

How does the Kosaraju–Sharir algorithm identify Strongly Connected Components (SCC)? a.) Performs a DFS on a graph G . Then, it orders the nodes by decreasing finishing times. The branches found by the DFS are considered strongly connected components. b.) Applies only to cyclic graphs. If a cycle has more than three nodes, then it is considered a strongly connected component. c.) Performs a DFS on a graph G . Then, it orders the nodes by decreasing finishing times. This order is used to perform a second DFS on the transposed graph G′ (where all edges are reversed). The trees formed during this DFS are considered strongly connected components. d.) Identifies cycles in a graph G , where for any pair of nodes u and v , there is a path from u to v and from v to u . e.) None of the above Original idea by: Julia de Pietro Bigi

What do BFS and DFS have in common? What about their differences?  a.) Common: They both use an adjacency list as input. Both of them can be used to calculate distances and classify edges. Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a given node, so not necessarily the entire tree will be visited. b.) Common: they both use an adjancency list and starting + ending times of node's visits as input.  Differences: BFS can be used to calculate distances and finding connected components. While DFS can be used to detect cycles and classify edges.  c.) Common: they both use an adjancency list as input.  Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a giving node, so not necessarily the entire tree will be visited.  d.) Common: they both need an adjancency list ...

Consider the following network: Which statements are TRUE or FALSE? 1. The degree distribution of this network would generate a graph with equal values of pk for k values.  2. If link (4-5) were to be removed, then the network would have 2 components. This makes the connection between nodes 4 and 5 to be called a bridge. 3. Considering node 4 as the zero node, the diameter of this network is dmax = 4. 4. The degrees of the two mostl connected nodes are equivalent to 2/3 and 1.  a.) T F F T b.) F F T T c.) T T F T  d.) F T T F  e) None of the above Original idea by: Julia de Pietro Bigi