Sea G un grafo plano conexo simple con 13 vértices y 19 aristas. Entonces, el número de caras en la incrustación plana del gráfico es
(A) 6
(B) 8
(C) 9
(D) 13
Respuesta: (B)
Explicación:
Un gráfico no dirigido se llama gráfico plano si se puede dibujar en un papel sin tener dos bordes cruzados y tal dibujo se llama Planar Embedding. Decimos que un grafo puede estar incrustado en el plano, si es plano. Un gráfico plano divide el plano en regiones (limitadas por los bordes), llamadas caras. El gráfico K4 es un gráfico palanar, porque tiene una incrustación plana como se muestra en
la siguiente figura.
Fórmula de Euler: para cualquier poliedro que no se interseque a sí mismo (Gráfico plano conectado), el
• Número de caras (F)
• más el número de vértices (puntos de esquina) (V)
• menos el número de aristas (E)
, siempre es igual a 2. Esto se puede escribir: F + V − E = 2.
Solución :
Aquí como se indica, F=?,V=13 y E=19
-> F+13-19=2
-> F=8
Entonces la respuesta es (B).
Esta solución es aportada por Nirmal Bharadwaj
Podemos aplicar la fórmula de Euler de grafos planos . La fórmula es v − e + f = 2.
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