PUERTA | PUERTA CS 2012 | Pregunta 36

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 ₄ formas de elegir 4 vértices de 6. El valor de ⁶ C ₄ 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.

 
Cuestionario de esta pregunta