Enunciado:
Sabendo que a "espessura" de um grafo G é o número mínimo de grafos planares em uma decomposição de G em grafos planares. E o "número de cruzamentos" de um grafo G é o número mínimo de cruzamentos em um desenho de G no plano. O valor da espessura e o número de cruzamentos do grafo de Peterson são respectivamentes:
A. 1 e 1
B. 1 e 2
C. 2 e 1
D. 2 e 2
E. NDA
Ideia original de: Zhenlei Ji
Tá muito fácil, colega Zhen. Se a espessura fosse 1, o grafo seria planar e seu crossing number seria zero. Isto elimina imediatamente as alternativas A e B. Descarto.
ResponderExcluir