Matheus - MO412

Evaluate the following affirmations regarding planarity and planarity testing algorithms: I. A multi-graph is considered planar when it admits a plane drawing . II. To postulate Euler's formula ( $N-L+F=2$ ), one can start with a single node and observe        the  effect on $N$ , $L$ , and $F$ when adding a new node connected to an existing node, or when    adding a link between two existing nodes . III.  Kuratowski's Theorem states that a graph is planar if and only if it contains a subdivision (the process of replacing a link by a path) of $K_{3,3}$ or of $K_{5}$ , effectively making them mandatory subgraphs for planarity . IV. The pseudo-code for the DMP algorithm begins by starting with a single node and iteratively selects a fragment $B$ with the maximum number of faces $F(B)$ that contain all its vertices of attachment . V.  When using the DMP algorithm, a fragment of a graph $G$ with respect to a subgraph $H$ can be an...

In the heart of a bustling kitchen, Chef Leo is famous for his "Variable Soufflé." The height of the soufflé, $H$ , depends on two main factors: the temperature of the oven, $x$ , and the amount of whisking time, $y$ . Leo has discovered a mathematical model for his perfect bake: $$H(x, y) = x^2y + 3xy^2 + 5x - 2y$$ One morning, while the oven is preheating, Leo needs to know exactly how the height of the soufflé changes if he increases the temperature ( $x$ ) while keeping the whisking time ( $y$ ) perfectly constant. He needs to calculate the partial derivative of $H$ with respect to $x$ at the point where $x = 2$ and $y = 3$ . Given the function $H(x, y) = x^2y + 3xy^2 + 5x - 2y$ , what is the value of the partial derivative $\frac{\partial H}{\partial x}$ at the point $(2, 3)$? a) 37 b) 44 c) 39 d) 41 e) None of the above. Original idea by: Matheus de Oliveira Saldanha

 We know that Kosaraju-Sharir's algorithm can be used to find the Strongly Connected Components (SCCs)   of a graph. It is composed of three main tasks:  Get Decreasing Order of DFS Finishing Times Traverse the Reverse Graph Each Tree is a Strongly Connected Component Given that, and the following graph: Select the alternative that has the correctly DFS decreasing order of finishing times starting from node A , the correctly reverse graph and, finally, each SCC colored correctly.       e) None of the above.                                                   Original idea by: Matheus de Oliveira Saldanha

Jerry the mouse is trying to reach a piece of cheese located somewhere in a maze. The maze can be represented as a graph , where: Each node is labeled with a letter and a number (for example: A1, D2, F3). Edges represent paths between locations in the maze . Jerry starts at node D2 and explores the maze using Depth-First Search (DFS) . When DFS needs to choose which neighbor to visit next, Jerry must follow one consistent ordering rule . However, he is not sure which rule will lead him to the cheese the fastest. Jerry is considering the following four DFS neighbor ordering strategies: Order neighbors by the letter only, ascending (A → Z) Order neighbors by the letter only, descending (Z → A) Order neighbors by the number only, ascending (1 → 9) Order neighbors by the number only, descending (9 → 1) Assume that when sorting neighbors, the ignored part of the label is not considered . The cheese is located at node  J2 . Which of the following alterna...

Using the Breath-First-Search (BFS) algorithm, how many nodes have a distance of 1, 2 and 3 from node A, respectively? a) 2, 4, 3 b) 3, 3, 3 c) 3, 4, 2 d) 2, 3, 4 e) None of the above. Original idea by: Matheus de Oliveira Saldanha