La théorie des graphes

Résumé du document

Cours d'Informatique consacré à la théorie des graphes qui permet d'étudier mathématiquement des relations, qui peuvent être de nature qualitative, entre les individus d'un univers donné. Il contient des tableaux, schémas, graphiques et algorithmes.

Extraits

[...] Définition : Il calcule les chemins les plus courts depuis un sommet source donné et tous les sommets. Elle initialise pour chaque sommet sa distance à la source, initialement plus l'infini, sauf pour la source. Ensuite, elle procède à des "étapes", jusqu'à terminaison. Une étape considère toutes les arêtes u à v du graphe, dans un ordre quelconque, et met à jour la distance de v par: min(D[v], où est la longueur de l'arc u vers v. Dès qu'une étape ne modifie plus la méthode a terminé. [...]

[...] Problème : Il s'agit de trouver tous les chemins de valeur optimale entre tous les couples de sommets. Pour résoudre ces problèmes on va utiliser les algorithmes des graphes. Ces algorithmes consistent à trouver des chemins optimaux (soit minimaux, soit maximaux) entre tous les couples de sommets ou bien entre deux sommets choisis, selon l'algorithme pris en charge. Généralités : La figure ci dessous représente un graphe valué comportant un ensemble de 5 sommets et de 7 arcs. Chaque arc relie un couple présente une valeur V(xi,xj) appelée la longueur de l'arc. [...]

[...] On suppose qu'entre deux sommets il y a au plus un arc. En effet, s'il en existe plusieurs, il suffit de ne retenir que le plus court. N.B: Si un chemin de longueur minimal joignant X à Y et qui passe par alors il se décompose en deux chemins de longueurs minimales l'un qui joint X à Z et l'autre qui joint Z à Y. Etape k=1 : On suppose les sommets numérotés X1, X2 Xn. On pose (V'(Xi,Xj)=la valeur si (Xi,Xj) existe etV'(Xi,Xj)=+( sinon) puis on met ces valeurs dans la matrice n(n appelé M0. [...]

[...] Donc alors on pose et on insère i=4 dans l'ensemble E qui devient . ( j ( E c-à-d Pour chaque j : On cherche D[j]=min{D[j] , + avec Donc on a : D[5]=min{D[5] , + = min(6,7)=6. Donc enfin pour et pour On cherche un i(E tel que : D[i]=min{ = min{D[5]} = min{6} =6. Donc alors on pose et on insère i=5 dans l'ensemble E qui devient . On ne passe plus a l'étape suivante car l'ensemble X=E c-à-d fin de l'algorithme. [...]

[...] partie pratique : à pour but d'exposer la manière de résoudre le problème informatiquement (complexité des algorithmes, l'analyse du problème, algorithmes & les fonctions utilisées partie théorique : quelques définitions generales : a. Graphe value : Un graphe value est un triplet ou : X : l'ensemble des sommets. T : l'ensemble des arcs. V : une fonction à valeurs dans un ensemble E tel que : V : T(E X * X0 * X * 10 X3 * b. Chemin optimal : C'est un chemin allant d'un sommet à l'autre et qui a une valeur extrémale (soit maximale et soit minimale) entre ces deux sommets. c. [...]