Quiz Question - March 13, 2026

 Consider the following graph and the subsequent statements:


1. The link (g, a) is a back edge when starting DFS from node d (alphabetical order).

2. The link (g, a) is a back edge when starting DFS from node a (alphabetical order).

3. The number of tree edges is the same when applying DFS from node a and from node d.

4. If we remove nodes h and i, the remaining graph will have a hamiltonian path.


The correct statements are:

a) 1, 3 and 4.

b) 1, 2 and 3.

c) 2, 3 and 4.

d) Just 1 and 4.

e) None of the above.


Original idea by: Rafael Brusiquesi Martins

Comentários

  1. Joao Meidanis14 de março de 2026 às 07:03

    Nice question, but we have many already, and this one mixes Hamiltonian paths with DFS. I'm not sure we covered Hamiltonian paths.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Imagem
We have this conformation of connected water tanks: We can model the first tank as: \[ \begin{cases} \frac{dm}{dt} = \dot{m}_{in} - \dot{m}_{out}  \\ \dot{m}_{out}=\sqrt{m} \\ \dot{m}_{in}=10 \\ m(t=0)=0 \end{cases} \] Where \(m\) is the mass inside the tank, \( \dot{m}_{in}\) is the mass entering the tank and \( \dot{m}_{out}\) is the mass leaving the tank. Units: Kg for mass, minutes for time. Tip: \(\int_{0}^{y} \frac{1}{a - \sqrt{x}} \, dx = 2a \ln \left| \frac{a}{a - \sqrt{y}} \right| - 2\sqrt{y}\) Take a look at the following statements: 1. The time for the first tank to achieve 80% of it's steady-state mass would be roughly 27 minutes. 2. Assuming the second tank follow the same model from the first tank, but it's inlet is defined by the outlet of the first tank, after a very long time, the mass inside the tank would be roughly 10 Kg. 3. Assume that at a given time, the entire tank system behaves like the following flow network: The residual network related to the syste...
Leia mais

Quiz Question - March 27, 2026

Imagem
 Take a look at the following graphs. Graph 1: Graph 2: Graph 3: 1. If we plot the degree distribution of Graph 2 in a log-log plot, we would get a shape similar to a line. 2. For Graph 2 to keep the same number of nodes, but become connected, the probability \(p\) should be roughly 0.0038. 3. Graph 1 operates in the subcritical regime, which means it lacks a giant component. 4. Graph 3 can be accurately approximated by a Poisson Distribution. The correct statements are: a) 1 and 2. b) 1 and 4. c) 2 and 3. d) Just 3. e) None of the above. Original idea by: Rafael Brusiquesi Martins
Leia mais

Quiz Question - March 6, 2026

Imagem
 Consider the following graph and the subsequent affirmations: 1. The graph is connected because the links (0, 1), (0, 2) and (0, 3) instersect with the links (4, 5), (4, 6) and (5, 6). 2. If we consider the components of this graph as projections of a bipartite graph, the parent bipartite graph could be: 3. The adjacency matrix of this graph can be rearranged and separated into two non-zero submatrices of size 4x4 and 3x3. The correct affirmations are: a) 1 and 2 b) 1 and 3 c) 2 and 3 d) Just 3 e) None of the above. Original idea by: Rafael Brusiquesi Martins
Leia mais