Algorithmes appliqués aux graphes

Voici quelques algorithmes qui s'appliquent au domaine des graphes. Nous allons nous intéresser à certains d'entre-eux (vous pouvez cliquer sur les liens pour plus de détails).

  • Parcourir un graphe
  • Chemins et circuits
    • Détecter la simple présence d'un chemin entre 2 sommets
    • Détecter un chemin de longueur déterminée entre 2 sommets
    • Calculer le nombre de longueur déterminée (>1) entre 2 sommets
    • Calculer la matrice M ou M' : Algorithme de Warshall, complexité de Ordre de grandeur(n3).
    • Détecter un circuit dans un graphe
    • Détecter un circuit passant par un sommet donné
    • Détecter un circuit passant par un arc donné
  • Rechercher un ou plusieurs chemins extrémaux des graphes pondérés (les plus courts ou les plus longs)
    • Algorithme de Bellman-Kalaba (pas de circuits), complexité de Ordre de grandeur(n2).
    • Algorithme de Moore-Dijkstra (circuits nécessaires, poids positifs ou nuls), complexité de Ordre de grandeur(n2).
    • Algorithme de Ford-Bellman (avec ou sans circuits, détection de circuits absorbants, poids quelconques), complexité de Ordre de grandeur(n3).
    • Heusistique A* (avec ou sans circuits, bornes, et sommet destination pré-déterminé)
    • Algorithme de Floyd-Warshall (accepte les poids négatifs, mais pas de cycle strictement négatif)
    • Algorithme de Ford-Dantzig (graphe orienté, avec ou sans circuit, poids positifs et négatifs)
  • Arbres couvrant (ARPM[1], ou ACM[2])
    • Algorithme de Kruskal (graphe connexe, valué, non orienté)
    • Algorithme de Prim (graphe connexe, valué, non orienté)
  • Flux extémaux (minimum ou maximum)
    • Algorithme de Ford-Fulkerson
    • Algorithme de Edmonds-Karp
    • Algorithme de flux bloquant de Dinitz
  • Divers
    • Construire la fermeture transitive d'un graphe orienté ou non orienté
    • Construire les composantes simplement connexes d'un graphe (via DFS), complexité de Ordre de grandeur(m+n).
    • Construire les composantes fortement connexes d'un graphe
    • Décomposer en niveaux. (sans circuit), complexité de Ordre de grandeur(n2).
    • Aide à la décision multicritère : ELECTRE

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Notes

  1.  ARPM : Arbre Recouvrant de Poids Minimum

  2.  ACM : Arbre Couvrant Minimum

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-11328
Document créé le 27/11/09 23:45, dernière modification le Vendredi 17 Juin 2011, 12:11
Source du document imprimé : http:///www.gaudry.be/graphes-algo.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,06 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Le bonheur n'est pas dans l'absence de luttes, dans l'absence de souffrances. Le véritable bonheur est dans la capacité à rester en paix malgré la souffrance, malgré que le monde ne fonctionne pas selon nos souhaits.

Za Rinpoché
 
l'infobrol
Nous sommes le Lundi 24 Juillet 2017, 22:52, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)