- Camino euleriano
-
Camino euleriano
Dado un grafo conexo y no dirigido
style="max-width : 98%; height: auto; width: auto;" src="/pictures/eswiki/49/195636bf16428d76b710b5750c2ae013.png">, P es un camino euleriano sobre G si y sólo si pasa por todas las aristas de G exáctamente una vez.
Teorema
Dado un grafo conexo y no dirigido
style="max-width : 98%; height: auto; width: auto;" src="/pictures/eswiki/49/195636bf16428d76b710b5750c2ae013.png">, si G tiene exactamente dos vértices de grado impar, entonces G tiene un camino euleriano.
Teorema
Dado un Grafo conexo y no orientado G; Si tiene 2k nodos de grado impar, entonces G puede ser escrito como unión de k caminos(simples) distintos sobre los arcos.
caminos distintos sobre los arcos
va de un nodo de grado impar a un nodo de grado impar.
Un grafo admite un camino euleriano cuando tiene exactamente dos nodos de grado impar (conexos a los caminos)
Véase también
- Ciclo Euleriano
Categorías: Teoría de grafos | Optimización | Investigación Operativa
Wikimedia foundation. 2010.