Buenas, tengo una duda de este ejercicio del examen, la primer parte.
Pueden explicar como se hace?
Tengo una idea a ver si ayuda, aplico principio de inclusión exclusión:
Numerando los vértices del 1 al 15, todos los caminos hamiltoneanos vienen de la
permutación de los 1 2 3 4 5 . . . 15 vértices: 15!
Ahora tomamos dos aristas no adyacentes, digamos 12 y 34, la condición C1 de los
caminos que si pasan por 12 es la permutación de:
12 3 4 5 ... 15, o sea 14! x 2, (por dos ya que tengo que considerar 12 y 21)
Análogo para C2, los caminos que pasan por 34: 14! x 2
Finalmente los caminos que pasan por 12 y por 34:
12 34 5 6 7 .... 15: 13!x4 (por 4 para considerar 12 34, 21 34, 12 43 y 21 43)
Aplicando S-S1+S2: 15! - (14!x2 + 14! x 2) + 13!x4, haciendo cuentas y sacando 13! de factor común deberías llegar a la respuesta.
Numerando los vértices del 1 al 15, todos los caminos hamiltoneanos vienen de la
permutación de los 1 2 3 4 5 . . . 15 vértices: 15!
Ahora tomamos dos aristas no adyacentes, digamos 12 y 34, la condición C1 de los
caminos que si pasan por 12 es la permutación de:
12 3 4 5 ... 15, o sea 14! x 2, (por dos ya que tengo que considerar 12 y 21)
Análogo para C2, los caminos que pasan por 34: 14! x 2
Finalmente los caminos que pasan por 12 y por 34:
12 34 5 6 7 .... 15: 13!x4 (por 4 para considerar 12 34, 21 34, 12 43 y 21 43)
Aplicando S-S1+S2: 15! - (14!x2 + 14! x 2) + 13!x4, haciendo cuentas y sacando 13! de factor común deberías llegar a la respuesta.
Muchas gracias!! logre entenderlo
Pregunta, entendí tu razonamiento pero me quedo una duda. Vos ahí elegiste las aristas no adyacente (1,2) y (3,4) pero perfectamente se pudieron haber elegido otras ¿En algún momento, no habría que multiplicar por todas las formas de elegir dos aristas no adyacentes?
Me parece que no. Cada vez que elegís dos aristas para retirar, estás creando un grafo nuevo, la idea del planteo debe ser calcular la cantidad de caminos de ese grafo (de hecho lo plantea en singular) y no la suma de todos los caminos de todos los grafos posibles.
Buenas tengo el mismo ejercicio pero con K18 y me piden h/16! donde h es la cantidad de caminos hamiltonianos , hice todo tal cual explicaste vos pero no me da el resultado no se en que me puedo estar equivocando me tiene que dar 273
Para K18 me da 242, no sé entonces como se llega al 273.
Si ahiva me da eso , no se la verdad donde puede estar el error
Hola
Gracias Rafael por tu respuesta con el procedimiento de resolución, que es correcto.
Germán, revisé la versión de la pregunta con K18 y tenía la respuesta mal. La correcta es 242, como dice Rafael.
(la recorrección no afectó a nadie)
Saludos
Gracias Rafael por tu respuesta con el procedimiento de resolución, que es correcto.
Germán, revisé la versión de la pregunta con K18 y tenía la respuesta mal. La correcta es 242, como dice Rafael.
(la recorrección no afectó a nadie)
Saludos