Sea G un grafo completo no dirigido de 6 vértices. Si los vértices de G están etiquetados, entonces el número de ciclos distintos de longitud 4 en G es igual a
(A) 15
(B) 30
(C) 45
(D) 360
Respuesta: (C)
Explicación: Puede haber un total de 6 C 4 formas de elegir 4 vértices de 6. El valor de 6 C 4 es 15.
Tenga en cuenta que el gráfico dado está completo, por lo que cualquier 4 vértices pueden formar un ciclo.
Puede haber 6 ciclos diferentes con 4 vértices. Por ejemplo, considere 4 vértices como a, b, c y d. Los tres ciclos distintos son
los ciclos deberían ser así
(a, b, c, d,a)
(a, b, d, c,a)
(a, c, b, d,a)
(a, c, d, b,a)
( a, d, b, c, a)
(a, d, c, b, a)
y
(a, b, c, d, a) y (a, d, c, b, a)
(a, b, d, c, a) y (a, c, d, b, a)
(a, c , b, d,a) y (a, d, b, c,a)
son ciclos iguales.
Así que el número total de ciclos distintos es (15*3) = 45.
**NOTA**: En el cuestionario original de GATE 45 no era una opción. En lugar de 45, había 90.
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