[beginnerweb]

Se sabe que un grafo G de 12 vértices tiene un ciclo hamiltoniano, entonces se puede afirmar que la cantidad mínima de aristas que puede tener G es: 45 o 57?


\( n=12 \)

\( \dfrac{1}{2}(n^2-3n+6) \)

\( \dfrac{1}{2}(12^2-3*12+6) \)
Mensaje corregido desde la administración.

[geómetracat]

No sé si estoy entendiendo algo mal, pero yo diría que el número mínimo de aristas que puede tener un grafo de \[ 12 \] vértices con un ciclo Hamiltoniano es \[ 12 \]. Piensa en el grafo que forma un polígono de \[ 12 \] lados (y \[ 12 \] vértices). Este grafo tiene claramente un ciclo Hamiltoniano.

Tampoco tengo claro de dónde has sacado esa fórmula ni qué representa.

[Luis Fuentes]

Hola

Se sabe que un grafo G de 12 vértices tiene un ciclo hamiltoniano, entonces se puede afirmar que la cantidad mínima de aristas que puede tener G es: 45 o 57?


\( n=12 \)

\( \dfrac{1}{2}(n^2-3n+6) \)

\( \dfrac{1}{2}(12^2-3*12+6) \)
Mensaje corregido desde la administración.

Creo que se refiere al mínimo número de aristas que tiene que tener (no que puede tener) un grafo de \( n \) vértices para poder garantizar que sea Hamiltoniano.

Es:

\( \displaystyle\binom{n-1}{2}+2 \)

Saludos.

P.D. https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

[beginnerweb]

Entonces seria 7,5 aristas? 

[Luis Fuentes]

Hola

Entonces seria 7,5 aristas? 

No. Estoy hablando del número combinatorio \( \displaystyle\binom{n-1}{2} \). Para \( n=12 \):

\( \displaystyle\binom{12-1}{2}+2=\dfrac{11\cdot 10}{1\cdot 2}+2=57 \)

Saludos.

[beginnerweb]

Bueno gracias.
Me da el mismo resultado que usando el Teorema 12 de Grafos, pero tu forma es mucho mas sencilla