Posts

Image
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...
1 comment
Read more
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
1 comment
Read more
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...
1 comment
Read more
Image
  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
2 comments
Read more