ciclo euleriano

ciclo euleriano

ciclo euleriano in un grafo orientato G = (X, A), cammino chiuso semplice che attraversa ciascun arco del grafo una e una sola volta. Non è sempre possibile determinare un ciclo euleriano in un grafo. Un grafo orientato possiede un ciclo euleriano orientato se e solo se le cardinalità della stella uscente e della stella entrante di ogni nodo sono uguali. Un ciclo euleriano è definibile anche in un grafo non orientato come percorso chiuso semplice che attraversa ciascun arco del grafo una e una sola volta. Un grafo possiede un ciclo euleriano se e solo se il grado di ogni nodo è pari.