PUERTA | PUERTA CS 2019 | Pregunta 19

Sea G un grafo completo no dirigido sobre n vértices, donde n > 2. Entonces, el número de ciclos hamiltonianos diferentes en G es igual a

(A) no!
(B) n – 1!
(C) 1
(D) (n-1)! / 2

Respuesta: (D)
Explicación: Un circuito simple en un gráfico G que pasa por cada vértice exactamente una vez se llama circuito hamiltoniano .

En un gráfico completo no dirigido en n vértices, hay n permutaciones posibles para visitar cada Node. Pero de estas permutaciones, hay:

1. En diferentes lugares (es decir, Nodes) puede comenzar;
2. 2 (hacia la derecha o hacia la izquierda) direcciones diferentes en las que puede viajar.

Así que cualquiera de estos n! ciclos está en un conjunto de 2n ciclos que contienen el mismo conjunto de aristas. Así que hay,

= (n)! / (2n)
= (n−1)! / 2 distinct Hamilton cycles. 

La opción (D) es correcta.
Cuestionario de esta pregunta