next up previous contents index
suivant: Cas centré-arêtes monter: Graphe Eulérien précédent: Graphe Eulérien   Table des matières   Index

Cas centré-sommets

Dans le cas centré-sommets, cela donne la fonction Python suivante :
def eulerian (G):
    if not connected(G):
        return 0
    n = 0
    for i in range(NB_NODES(G)):
        d = NB_EDGES(NODE(G, i))
        if d % 2:
            n += 1
        if n > 2:
            return 0
    return 1
La complexité de la fonction connected(G) étant $O(\vert V(G)\vert + \vert E(G)\vert)$ et celle de la boucle for $O(\vert V(G)\vert$, nous obtenons dans le cas centré-sommets, une complexité $O(\vert V(G)\vert + \vert E(G)\vert)$ pour la fonction eulerian.