Postagens

Flow network

Imagem
Given the flow network below with labels (capacity, flow), let (S) be the source and (T) be the sink. Build the residual network from the given (capacity, flow) labels. Consider this as the   initial residual network and evaluate the statements: I. In the initial residual network, the path S -> B -> E -> F -> T is an augmenting path with bottleneck 3 . II. In the initial residual network, there is no augmenting path. The current flow is already maximum. III. Starting from the initial residual network, after performing any best single-path augmentation (i.e., any   augmenting path   with maximum bottleneck possible) , there still exists an augmenting path with bottleneck 1 . IV. The value of the current flow in the given network (before any new augmentation) is 13 . Choose the correct alternative: A) I and III only B) I and IV only C) II and III only D) I, III, and IV E) None of the above Original idea by: Thiago Soares Laitz
1 comentário
Leia mais

Graph algorithms

A software engineering team is modernizing a legacy system with hundreds of code modules. The goal is to refactor the system by splitting it into independent microservices. A major challenge is the complex network of “imports” between modules. They found that many modules are interdependent; that is, Module A depends on Module B, which in turn, directly or indirectly, depends on Module A. To carry out the microservice separation, the team first needs to identify these groups of mutually dependent modules, since they must be treated as a single unit. Which algorithmic approach would be most effective to identify these groups of modules, considering this problem can be modeled as a directed graph? Analyze the statements below and select the correct alternative: I. Topological Sorting can be applied because it arranges modules in a linear order of dependencies and, when it fails, it indicates the existence of cycles, making it useful as a diagnostic tool and making it easy to identify th...
1 comentário
Leia mais

DFS

 Consider the execution of Depth-First Search (DFS) on a graph G. Analyze the following statements: I. The existence of at least one backward edge during the DFS traversal guarantees that G contains at least one cycle. II. In an undirected graph, DFS can generate forward and cross edges if the graph is disconnected. III. After running DFS on a graph, if a backward edge is found, it is still possible to produce a valid topological sort of its vertices. IV. Cross edges alone are sufficient to guarantee that G contains a cycle. Which of the following combinations of statements is true? A) I and III only. B) I and II only. C) Only I. D) II and IV only. E) None of the above. Original idea by: Thiago Laitz
2 comentários
Leia mais