MO412 - Melissa Araújo

Maria studies at UNICAMP and is taking a Graph Algorithms class.  Driven by curiosity, she applied what she learned in class to a network generated from her classmates' profiles on the social media platform Z. The nodes of the network are Maria's classmates and an outgoing edge indicates following someone, while an incoming edge indicates being followed by someone.  She wanted to identify specific communities and see if there were any isolated classmates. Her goal was to bring those people into a community to ensure no one feels alone in class. Could you help her identify the number of communities and isolated profiles in this network? Maria defines a c ommunity  as any group of classmates forming a Strongly Connected Component (SCC) of two or more people (nodes). Any classmate who belongs to an SCC of only one person (node) is considered an i solated profile . a) There are 3 communities and 4 isolated profiles. b) There are 2 communities and 4 isolate profiles. c) There ...

Consider the graph on the figure below. Determine the number of back edges, cross edges, and forward edges generated by the Depth-First Search (DFS) algorithm. Assume the algorithm visits neighboring vertices in ascending order. A) 2 back edges, 4 cross edges, and 2 forward edges.  B) 2 back edges, 5 cross edges, and 1 forward edge. C) 1 back edge, 4 cross edges, and 2 forward edges. D) 1 back edge, 5 cross edges, and 2 forward edges. E) None of the above. Original idea by: Melissa Araújo.

Consider the following networks: Choose the correct answer: A) Only the A, B and C graphs are bipartite. B) All the graphs are bipartite. C) Only the A, B and D graphs are bipartite. D) Only the A and D graphs are bipartite. E) None of the above. Original idea by: Melissa Araújo