Edge classification (16/08/2024)

After running a DFS algorithm in a directed graph, the following table represents the start and end time of each node.


Node

Start time

End time

A

1

10

B

8

9

C

2

7

D

3

4

E

5

6

 

Select the correct alternative about the edges:

 

a) The edge A -> C is a backward edge

b) The edge D -> E is a forward edge

c) The edge B -> C is a cross edge

d) The edge E-> D is a forward edge

e) None of the above

Original idea by: João Vitor  

Comentários

  1. Joao Meidanis19 de agosto de 2024 às 10:39

    Very good question. However, the reader is unsure about which edges exist in the graph. If edge B -> C exists, it will certainly be a cross edge, so alternative (c) would be correct. However, it may not exist, in which case the correct answer would be (e). This ambiguity forces me to discard your question.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Graph Teory (23/08/2024)

Consider an adjacency matrix A A , such that A i j = 1  if there is an edge from vertex  j  to vertex  i ,   A_{ij} = 1 \text{ if there is an edge from vertex } j \text{ to vertex } A i j = 0  otherwise . Select the correct alternative: a) If the graph is undirected, A = A T A = A^T . b) If the graph is directed, the main diagonal is always equal to 1. c) If the graph is undirected, the main diagonal is always equal to 0. d) If the graph is directed, A A is invertible. e) None of the above Original idea by: João Vitor Baptista Moreira
Leia mais

BFS (06/09/2024)

Imagem
John is a tourist from Minas Gerais who is on vacation and want to explore the cities in UaiSo. There are 3 main cities that he would like to visit: CheeseBreadLand, DulceDeLecheTown and TorresmoCity, that are painted in blue in the map. But John only moves following a BFS order , and he only has the time to visit 5 cities . Help John optimize his management so he can visit the most possible interesting cities. Consider that the BFS always choose the neighbours in ascending order and the following map is an undirected graph .   To visit the most number of cities he would like, what John should do? a) John should start his trip on city 1, so he can visit 2 cities of interest. b) John should start his trip on city 4, so he can visit 2 cities of interest. c) John should start his trip either on city 2 or 4, to visit 2 cities of interest. d) John should start his trip on city 2, so he can visit 2 cities of interest. e) None of the above Original idea by: João Vitor Baptista Moreira
Leia mais