Given the image bellow of a small part of the Campinas' streets represented in a graph and your knowledge about Network Science, check the following affirmations.
- There is only one shortest path between nodes 1 and 9 and it has length 9;
- The given graph is strongly connected;
- A shortest path can contain a loop;
- If we executed BFS Algorithm starting at node 9, the longest distance would be 7;
- The link between nodes 8 and 10 is a bridge (bridge as the Network Science definition).
Select the answer with only the true affirmations:
- I, II and V;
- I, III and IV;
- II and IV;
- II, IV and V;
- None of the above.
Original idea by: Fillipi Valadares
Interesting question, but I wonder what the definition of bridge for directed graphs is. We haven't discussed that. Also, the fact that the graph is in Campinas is just a distraction and should be avoided.
ReplyDeleteThanks for the considerations, professor! I thought from the book that since it did not mention the given bridge definition as particular for one kind of graph, it would apply for both directed or undirected.
ReplyDeleteAlso, the idea of defining the graph on top of a street view of Campinas was to follow the purpouse of Network Science we discussed in the first class, that it is intended to apply graphs to real problems, so I gave it a shot of showing how we can detect graphs in our daily routine.
Thanks once more!