Problema: grafo euleriano
Por un
grafico orientado, un camino (o circuito) euleriano pasa una y sólo una vez por todos los arcos. Análogamente, en el caso no dirigido, una cadena o ciclo euleriano pasa una y sólo una vez por todas las aristas.
El gráfico debe estar fuertemente conectado (o conectado). De hecho, si el gráfico no lo es, no se puede acceder a uno o más subgrafos que contienen enlaces. Vemos que un ciclo o circuito euleriano contiene tantos enlaces que llegan a un vértice como sale (llegamos a un vértice para salir)
Condiciones necesarias y suficientes del circuito / ciclo euleriano. El gráfico está conectado (o fuertemente conectado). Cualquiera que sea el vértice del gráfico, su grado es par (su grado de salida es igual a su grado de entrada).
Dado que todos los vértices tienen un grado par, sabemos que hay un circuito. Un camino es una unión de circuitos disjuntos en los bordes. Si eliminamos los bordes de un camino, los grados siempre son pares. Supongamos que no hay un camino que dé un ciclo euleriano. Si eliminamos una ruta con un máximo de bordes en el gráfico, los grados permanecen uniformes. Pero en este caso, hay un circuito desarticulado de nuestra ruta máxima. Siendo el recorrido una unión de circuitos disjuntos, se concluye que el recorrido inicial no era máximo. De esto se deduce que la ruta máxima contiene todos los bordes del gráfico. La prueba es idéntica para el caso orientado.
Sea una gráfica que admita una cadena euleriana. Agregar un borde entre el inicio y el final de la cadena nos dará un ciclo euleriano. Asimismo, si eliminamos cualquier borde de un ciclo euleriano, tendremos una cadena euleriana.
Con esta transformación, deducimos las condiciones necesarias y suficientes para que un gráfico tenga una cadena (o trayectoria) euleriana.
Condiciones necesarias y suficientes de la cadena / camino euleriano. El gráfico está conectado (o fuertemente conectado). Para todos los vértices del gráfico, excepto posiblemente dos, su grado es par (su grado de salida es igual a su grado de entrada + o - 1 para posiblemente dos vértices.
Problema: gráfico hamiltoniano
En un gráfico dirigido, un circuito o un camino hamiltoniano es un circuito o camino que pasa una vez y solo una vez por todos los vértices. Lo mismo ocurre con el caso no orientado.
Hasta la fecha, no existen condiciones necesarias y suficientes, sino solo condiciones suficientes relativas a los grados de los vértices.
Dirac 1952. Un gráfico simple con no vértices (n> 2) cada vértice de los cuales tiene un grado al menos igual an / 2 es hamiltoniano.
Mineral de 1960. Un gráfico simple con no vérticesn> 2) tal que la suma de los grados de cualquier par de vértices no adyacentes sea al menos no es hamiltoniano.
Posa 1962. Un gráfico simple con no vértices (n> 2) tales que para todos k, 0 <k<(n-1)/2 le nombre de sommets de degré inférieur ou égal à k es inferior a k. El número de vértices de grado menor o igual que (n-1) / 2 es menor o igual que (n-1) / 2.
ES 
FR 
EN