MO412 - Melissa Araújo

You’ve been waiting in the hospital waiting room for a long time. After staring at the artwork for so long, you begin to notice that the drawings in the frames look a lot like graphs. To pass the time, you decide to figure out which graphs are planar and which are not. The figure below illustrates how you see the artworks on the hospital wall. Select the option below that contains only frames whose drawings represent planar graphs: A) Frame 1, Frame 2, and Frame 3; B) Frame 1 and Frame 2; C) Only Frame 1; D) Only Frame 3; E) None of the above. Original idea by: Melissa Araújo.

Cynthya is a big fan of the band Suplaz, which rarely performs in Brazil. She just found out they’ll be at Rock in Rio and is thrilled. She is the manager of the Capanema (Pará) Suplaz fan group, so she decides to organize transportation to help as many fans from her city as possible attend the concert.  Since the trip is long, she sets up a system of shared rides and transfers: fans can travel between cities using different cars, vans, or buses, meeting at stops along the way. At each segment of the trip, there is a limit to how many people can be transported, depending on vehicle availability. Fans may switch vehicles at intermediate stops. The figure above represents this transportation system as a directed network. Capanema is the source (S) and Rock in Rio is the sink (T). The intermediate nodes (A, B, C, and D) represent transfer points, like hotels or meeting locations. Each edge has a capacity, indicating the maximum number of people that can travel along that segment. Usin...

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