On considère des graphes simples valués, c’est-à-dire dont chaque arc est muni d’un poids (nombre réel). Un chemin a pour poids la somme des poids des arcs qui le constituent.
Le problème des plus courts chemins consiste à déterminer le poids minimal d’un chemin d’un sommet à un autre, en supposant les poids positifs. Algorithme de Floyd On représente un graphe orienté valué à n sommets par une matrice carrée (n,n) de nombres : M[i,j] a pour valeur le poids de l’arc i->j(+ si cet arc n’existe pas).
Une (...)
Articles les plus récents
-
Algorithmes de plus court chemin
29 mars 2006 -
Correction de 09/2005
25 septembre 2005Exercice 1 : les bases (8 points)
Soit un graphe orienté G=(S,A), avec S=A,B,C,D,E,F,G,H,I,J,K et
A=AB,BA,BB,DC,DD,DE,EF,FC,FD,GF,GG,GH,GI,HI,IJ,JJ,JK,KI
Quelles sont les composantes connexes de G ? Ses composantes fortement connexes ?
Composantes connexes : A,BC,D,E,F,G,H,I,J,K
Composantes fortement connexes : A,BCD,E,FGHI,J,K
Donnez trois représentations de G : liste de sommets et d’arcs, matrice d’adjacence, matrice d’incidence. Ne notez pas les zéros dans les matrices.
Liste de sommet (...) -
Applications des parcours de graphes
17 août 2005Accessibilité Pour connaître les sommets accessibles depuis un sommet donné d’un graphe (orienté ou non), il suffit de faire un parcours en profondeur à partir de ce sommet, en marquant les sommets visités : marquage des accessibles depuis un sommet s : visiter s visiter un sommet t : SI t n’a pas encore été visité ALORS marquer t ; visiter tous les successeurs de t FIN SI Composantes connexes d’un graphe non orienté La composante connexe d’un sommet est l’ensemble des sommets accessibles (...)
-
Généralités sur les graphes
16 août 2005Graphes orientés et non orientés Un graphe orienté (directed graph) est caractérisé par un ensemble S de sommets (vertices ; un sommet : a vertex) un ensemble A d’arcs (edges), chaque arc ayant une origine (source) et un but (target) ; un arc a d’origine s, de but t, est généralement noté s->t. On dit alors que t est un successeur de s, et s un prédécesseur de t.
Figure 1.Un exemple de graphe orienté (noté G0 par la suite)
Si l’on ne s’intéresse pas au sens des arcs, on parlera de graphe non orienté (...) -
Téléchargements
16 août 2005Les cours sous divers formats
-
Parcours des graphes
16 août 2005Parcours des arborescences en largeur Le parcours en largeur (breadth-first search) d’une arborescence consiste à visiter les nœuds dans l’ordre « de gauche à droite et de haut en bas » : parcourir une arborescence en largeur : enfiler la racine ; TANT QUE la file n’est pas vide soit n le premier noeud de la file ; traitement de n défiler ; enfiler tous les fils de n FIN TANT QUE
Figure 14.Ordre de parcours en largeur : 1, 2, 3, 4, 5, 6, 7 Parcours des arborescences en profondeur Le (...) -
Examen du 26 Février 2005
19 juillet 2005Date : 26/02/2005 Session : 1 Durée : 2h
Professeur : M. Donnadieu Valeur : ½ Nature : Cours
Examen : Graphes et Algorithmes A5 Documents autorisés
Formation : HTO Code Enseignement : 19535 -
Programme officiel
18 juillet 2005Objectifs :
Apprendre comment modéliser des problèmes notamment d’optimisation, issus de l’informatique et de la recherche opérationnelle, comment les résoudre à l’aide d’un algorithme et de structures de données appropriées. -
Accueil
17 juillet 2005Page d’accueil
