Consider two networks, G 1 G_1 and G 2 G_2 , both modeled according to the Erdős–Rényi model G ( N , p ) G(N,p) . Both networks have N = 1000 N = 1000 , but different connectivity parameters given by: p 1 = 0.012 p_1 = 0.012 p 2 = 0.004 p_2 = 0.004 Based on the presented parameters and the robustness concepts studied in class, choose the correct alternative. a) G 2 has greater structural robustness because it presents lower average connectivity. b) G 1 has lower connectivity and, therefore, lower failure propagation. c) G 1 presents a higher critical threshold f c being more robust against random vertex removal, but more susceptible to rapid failure propagation. d) G 2 presents greater cascading failure propagation due to its lower average degree. e) None of the above. Original idea by: Tássia Martins
Posts
The airline GRAPHIPLAN needs to design routes between airports. In this setting, each airport/airplane is represented by a vertex , and each route between two airports is represented by an edge . Because all aircraft operate at the same altitude, the company must identify which configuration necessarily leads to route crossings, that is, whether there exists a graph that cannot be drawn in the plane without edges intersecting . Based on the figures below, choose the option that corresponds to a non-planar graph . a) b) c) d) e) None of the above. Original idea by: Tássia Martins.
During a peak usage period following a power outage, the network of a community center began operating using packet switching, where data is divided into small packets and transmitted across the network, and bandwidth is provided on demand. The infrastructure is composed of devices (nodes) such as routers, switches, and computers, interconnected by links (edges) with limited capacities. Each link has a maximum transmission capacity in (MB/s) , representing how much data can be transmitted. For the transmission to continue operating normally, all links must receive greater than 0 MB/s of flow. The main objective of the system is to maximize the total flow of data (packets) sent from S to T . Since packets can follow different paths to reach the destination, the network can be modeled as a directed graph , where: each device is a node; each link is an edge with a maximum transmission capacity. To ensure the best possible performance, we aim to determine the maximum flow o...
C onsider a directed graph G and the concept of Strongly Connected Components (SCC). Analyze the following statements, and choose the right answer: I- In a directed tree, each vertex is considered a SCC. II- Every cycle in a directed graph G always constitutes its own separate SCC. III- A trivial graph G cannot be considered as a SCC. a) I and II are correct. b) II and III are correct. c) Only I is correct. d) Only III is correct. e) None of the above. Original idea by: Tássia Martins
Look at the adjacency matrix of a directed graph below, analyze the statements, and choose the right answer: $$ A_{ij} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} $$ OBS: To BFS and DFS consider starting at node 1 and in an ascending order. I - This graph has a Cycle, so we can say that there is at least one back edge. II - The order that the nodes are visited using DFS is 1-4-2-6-7-5-3. III - The order that the nodes are visited using BFS is 1-4-5-2-6-7-3. IV - Besides the graph presented by the matrix being a directed graph, in an undirected graph there are no forward and no cross edges. a) I, II, III and IV are co...
Look at the figures below and choose the right answer: I- The graph in figure A is a Multigraph and in figure B is a simple graph. II- In a complete graph, known as clique, all nodes are connected to each other. III- The diameter of the graph in figure B is d max = 4. IV- The adjacency matrix of graph in figure B is: a) I and II are correct b) II, III and IV are correct c) II and IV are correct d) I, II, IV are correct e) None of the above