The airline GRAPHIPLAN needs to design routes between airports. In this setting, each airport/airplane is represented by a vertex, and each route between two airports is represented by an edge.

Because all aircraft operate at the same altitude, the company must identify which configuration necessarily leads to route crossings, that is, whether there exists a graph that cannot be drawn in the plane without edges intersecting.

Based on the figures below, choose the option that corresponds to a non-planar graph.

a)


b) 











c)














d)









e) None of the above.


Original idea by: Tássia Martins.

Comments

Post a Comment

Popular posts from this blog

Look at the adjacency matrix of a directed graph below, analyze the statements, and choose the right answer: $$ A_{ij} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\  0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} $$ OBS: To BFS and DFS consider starting at node 1 and in an ascending order. I - This graph has a Cycle, so we can say that there is at least one back edge. II - The order that the nodes are visited using DFS is 1-4-2-6-7-5-3. III - The order that the nodes are visited using BFS is 1-4-5-2-6-7-3. IV - Besides the graph presented by the matrix being a directed graph, in an undirected graph there are no forward and no cross edges. a) I, II, III and IV are co...
Read more
Image
  Look at the figures below and choose the right answer: I- The graph in figure A is a Multigraph and in figure B is a simple graph. II- In a complete graph, known as clique, all nodes are connected to each other. III- The diameter of the graph in figure B is d max = 4. IV- The adjacency matrix of graph in figure B is: a) I and II are correct b) II, III and IV are correct c) II and IV are correct d) I, II, IV are correct e) None of the above
Read more
C onsider a directed graph G and the concept of Strongly Connected Components (SCC). Analyze the following statements, and choose the right answer: I- In a directed tree, each vertex is considered a SCC. II- Every cycle in a directed graph G always constitutes its own separate SCC. III- A trivial graph G cannot be considered as a SCC. a) I and II are correct. b) II and III are correct.  c) Only I is correct.  d) Only III is correct. e) None of the above. Original idea by: Tássia Martins
Read more