CONNEXION
  • RetourJeux
    • Sorties
    • Hit Parade
    • Les + populaires
    • Les + attendus
    • Soluces
    • Tous les Jeux
    • Gaming
  • RetourActu Gaming
    • News
    • Astuces
    • Tests
    • Previews
    • Toute l'actu gaming
  • RetourHigh-Tech
    • Actus High-Tech
    • Hardware
    • Smartphones
    • Image et son
    • Tutoriels
    • Tests produits High-Tech
    • Guides d'achat High-Tech
    • High-Tech
  • RetourCulture
    • Actus Culture
    • Culture
  • RetourVidéos
    • A la une
    • Gaming Live
    • Vidéos Tests
    • Vidéos Previews
    • Gameplay
    • Trailers
    • Chroniques
    • Replay Web TV
    • Toutes les vidéos
  • RetourForums
    • Hardware PC
    • PS5
    • Switch 2
    • Xbox Series
    • Switch
    • Pokemon pocket
    • FC 25 Ultimate Team
    • League of Legends
    • Tous les Forums
  • PC
  • PS5
  • Xbox Series
  • Switch 2
En ce moment Genshin Impact Valhalla Breath of the wild Animal Crossing GTA 5 Red dead 2
Liste des sujets

DAG : Question à la con...

Pseudo supprimé
Pseudo supprimé 22 janvier 2013 à 23:36:00

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 :)

chris_27
chris_27
Niveau 10
22 janvier 2013 à 23:45:16

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).

Pseudo supprimé
Pseudo supprimé 22 janvier 2013 à 23:55:09

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 !

Sous forums
  • Aide à l'achat Mac
  • Steam Deck
  • Création de sites web
  • Création de Jeux
  • Linux
  • Programmation
  • Internet
  • Macintosh
  • Hardware
La vidéo du moment