Sea G el grafo no plano con el mínimo número posible de aristas. Entonces G tiene
(A) 9 aristas y 5 vértices
(B) 9 aristas y 6 vértices
(C) 10 aristas y 5 vértices
(D) 10 aristas y 6 vértices
Respuesta: (B)
Explicación: Según el teorema de Kuratowski , un gráfico es plana si y sólo si no contiene subdivisiones de los gráficos K 5 o K 3,3 .
Eso significa que K 5 y K 3,3 son gráficos mínimos no planos. Estos gráficos tienen 5 vértices con 10 aristas en K 5 y 6 vértices con 9 aristas en K 3,3 gráfico.
Entonces, el grafo K 5 tiene vértices mínimos y aristas máximas que K 3,3 .
Método alternativo:
un gráfico plano que tiene ‘n’ vértices, no puede tener más de ‘2*n-4’ número de aristas. Por lo tanto, usando la lógica, podemos deducir que para 6 vértices, se requieren 8 aristas para que sea un gráfico plano. Entonces, agregar un borde al gráfico lo convertirá en un gráfico no plano.
Entonces, 6 vértices y 9 aristas es la respuesta correcta.
Entonces, la opción (B) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA