hermano al principio dijistes que el camino hamiltoniano visita todos los puntos sin repetir aristas, y no te entendi, no querras decir que los vertices no se pueden repetir? vi que lo correjistes en la descripcion del video, no muchos la leen
Solo sirve para afirmar que un grafo es hamiltoniano, pero no para lo contrario, o sea decir que un grafo no es hamiltoniano y no se como puede hacer eso. Es como tratar de definir la luz sin el concepto de oscuridad o viceversa. Incluso me parece mejor esas veces cuando se puede decir en que falla algo mas no el como solucionarlo.
una pregunta mas, los grafos que pusistes al principio , no son hamiltonianos, tienes que convertirlos verdad? por eso de las aristas extras que no se pueden recorrer ya que repetirian vertices
Todos los grafos que salen en el video tienen ciclo y camino hamiltoniano. El hecho de que tengan mas aristas te hace mas fácil "en general" poder visitar todos los vértices sin repetir ninguno porque te da mas opciones. A que te refieres con convertir?.
El camino una cond necesaria y suficiente sería que hayan suficientes caminos para conectar los puntos, y éstos serán igual a la n cant de puntos - 1. Para el ciclo vengo pensando lo mismo, que una cond necesaria y suficiente es que los caminos sean suficientes para conectar con el mismo punto, siendo igual que la cond anterior, sin embargo se suma un camino para conectar el tramo final con el tramo inicial, o sea n. Son suficientes solo cuando se busca el camino o ciclo con menos conexiones.
El teorema de redei está mal, dibujad un grafo que sea un rombo y su diagonal menor, y un vértice en cada esquina del rombo y otro en mitad de la diagonal menor, no se cumple el teorema de rédei porque redei nunca dijo eso, es un error de wikipedia, ya está arreglado con otro teorema
gracias por el video. No entiendo lo del camino Hamiltoniano. No veo como puedes ir del nodo superior izquierdo al nodo superior derecho pasando por todos los caminos sin repetir un camino. Igual es que estoy un poco obtuso.
Si claro, si puedes hacer un circuito que empiece en un punto y termine en el mismo y pase por todos los puntos (vertices), aunque no uses todos las carreteras(aristas) ya es un ciclo hamiltomiano.
@@omurillo17 Si el grado de alguno de los vértices es mayor a la mitad del numero de vértices del grafo, podemos afirmar que ese grafo es Hamiltoniano, este teorema se llama teorema de Dirac
En realidad no deben ser adyacentes, he puesto ese ejemplo para que veáis cual seria el menor grado que se puede alcanzar con la suma con ese grafo (es solo un ejemplo), pero quizá con un vértice no adyaciente habría sido mejor. Ahora me he dado cuenta, gracias por el detalle!