Introduction à la théorie des graphes

Résumé du document

On recherche le chemin le plus long dans ce graphe ordonné par niveaux, et donc sans circuit, (sans quoi, le problème n'aurait pas de sens).
Ex. : le chemin le plus long ayant pour origine 4 et pour extrémité 7.
Tous les sommets de niveau inférieur ou égal à 4, et ceux de niveau supérieur ou égal à 7 ne peuvent être situés sur un tel chemin. On peut donc pour notre recherche les éliminer du graphe ainsi que tous les arcs dont ils sont l'origine ou l'extrémité (...)

Extraits

[...] On obtient ainsi cette date de début au + tard . Pour une opération ayant plusieurs suivants, on fait ce calcul pour chacun d'eux, et on retiendra la date la plus petite, c'est à dire la plus contraignante. 8ème étape : calcul de la marge totale = (date au + tard) (date au + tôt) 9ème étape : calcul de la marge libre = MIN parmi les suivants de l'opération de : (date au + tôt du suivant) - (date au + tôt de l'opération) (durée de l'opération) La marge totale s'interprète comme le retard maximum que peut prendre l'opération sans remettre en cause les dates de début au + tard des opérations suivantes. [...]

[...] Chaque mention du dictionnaire des précédents, allégé puis enrichi, fait l'objet d'un arc dont la longueur correspond à la durée de la tache origine, sauf pour α et les arcs délais 6ème étape : la section gauche correspond à la date de début au + tôt c'est à dire la longueur du chemin le plus long aboutissant à ce sommet, compte tenu de toutes les contraintes, c'est à dire de tous les arcs aboutissant à ce sommet. La marque attribuée au sommet final correspond à la date de fin prévu du projet. [...]

[...] Ainsi, au niveau les sommets qui n'ont pas de précédents, c'est à dire les magazines qui n'ont pas d'alternative qui leur soit préférable, dons les supports à sélectionner en priorité. Et ainsi, de suite, de niveau en niveau. Ici ) PROBLEME D'ORDONNANCEMENT Le tableau ci-dessus indique les durées en jour des opérations nécessaires à la construction d'une usine, ainsi que les contraintes auxquelles elles sont soumises : - Contraintes d'antériorité, l'ordre dans lequel elles doivent être exécutées, ici, un dictionnaire des suivants. - Contraintes de dates, avant lesquelles les opérations ne peuvent être entreprises. - Contraintes de délais, à respecter entre 2 opérations. [...]

[...] La matrice booléenne correspondant au graphe ci-dessus est la suivante : La lecture ligne par ligne de cette matrice donne le dictionnaire des suivants. La lecture colonne par colonne de cette matrice donne le dictionnaire des précédents. Un chemin est une suite ordonnée de sommets : telle que : Sur notre graphe ( ) est un chemin. La longueur de ce chemin au sens des arcs est égale à n-1. Un circuit est un chemin tel que : Le premier sommet est aussi le dernier : on décrit une boucle. [...]

[...] Un chemin est dit eulérien s'il passe une et une seule fois par chaque arc du graphe. Un chemin est préeulérien s'il passe au moins une fois par chaque arc du graphe ) DETERMINATION DES NIVEAUX D'UN GRAPHE Le niveau d'un sommet i est la longueur au sens des arcs du plus long chemin ayant pour extrémité i . Soit le graphe G suivant, défini par son tracé et par son dictionnaire des précédents : sommet sans précédent est de niveau 0. [...]