Quelqu'un s'est déjà amusé à calculer le nombre d'arêtes maximum qu'il peut y avoir dans un graphe orienté acyclique ? On aurait pas un truc du genre n*(n-1) si n est le nombre de sommets ? Dans ce cas là, le coût de construction dans le pire des cas est de l'ordre de O(n²), non ?

Sinon, je suis preneur de tout cours/bouquin sur le calcul de complexité/d'algorithmique. J'ai envie de me remettre à jour sur deux-trois trucs

Si j'ai déjà fait ça dans ma vie, c'était dans un sujet de concours/examen que j'ai oublié.

J'arrive à faire un graphe orienté acyclique avec n noeud et n(n-1)/2 arêtes. Au dela de ce nombre, comme il y n(n-1)/2 paires de noeuds, tu vas forcément avoir au moins une arête prise dans les deux sens (et donc un cycle entre 2 noeuds).

Quand à la construction du graphe qui atteint ce maximum, elle peut me coûter O(1) (O(log(n)) en complexité binaire) dans la mesure où ce graphe est unique modulo l'ordre des sommets (et qu'on se fiche bien souvent de cet ordre).

Ah ouais, bien vu, je me disais aussi que quelque chose clochait
Il n'y a pas juste le noeud d'origine qui ne peut pas pointer sur lui même, mais également tous ses successeurs...

Merci !