Soutenance mémoire
De nos jours, grâce au développement considérable de la science et de la technologie, l’être humain essayait de créer de diverses innovations à l’aide de la découverte, la pratique se réfère toutefois basée sur des théories, constituant un modèle adéquate à l’élaboration des projets de construction tels que les réseaux routières, des réseaux de communication, etc.
Actuellement, des nombreux pays au monde demeurent encore sous développé du point de vue économique comme Madagascar qui est toujours à la recherche des plans pour éradiquer la pauvreté de la population, la théorie des graphes constitue un atout considérable dans le but d’optimiser autant que possible la construction des biens selon les moyens disponibles.
QUELQUES ELEMENTS DES GRAPHES
HISTORIQUE DE LA THEORIE DES GRAPHES
La théorie des graphes est née en 1736 quand Euler démontra qu’il était impossible de traverser chacun des sept ponts de la ville de Königsberg une fois exactement et de revenir au point de départ. La théorie des graphes constitue une branche à part entière de mathématiques, grâce aux travaux de Koenig, Menger, Cayley puis de Berge et d’Erdös. Elle s’est alors développée dans diverses disciplines telles que la chimie, la biologie, les sciences sociales. D’une manière générale un graphe permet de représenter la structure, les connexions d’un ensemble complexe en exprimant les relations entre ses éléments : réseaux de communications, réseaux routières, interaction de diverses espèces animales, circuits électriques,… Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande variété des problèmes en se ramenant à l’étude des sommets et d’arcs. Les derniers travaux en théorie des graphes sont souvent effectués par des informaticiens du fait de l’importance qu’y revêt d’aspect algorithmique.
Algorithme de Edsger Dijkstra
Présentation
Edsger Dijkstra était un mathématicien hollandais né en 1930, il fut d’abord des études en physiques théoriques avant de se pencher sur les premiers problèmes reliés à l’informatique. Il fut l’un des premiers à se pencher sur le concept de sémaphore en 1962, concept qui est maintenant bien intégré dans les langages modernes pour la gestion et la synchronisation des processus. L’algorithme de Dijkstra est pratique pour résoudre les problèmes de plus court chemin dans les graphes.
Algorithme de Dijkstra
Numérotons les sommets du graphe de 1 à n. Cet algorithme calcule le plus court chemin du sommet 1 à tout le sommet du graphe (il donnera donc la première ligne de la matrice de cout minimum).
On construit un vecteur ? = (? (I), ? (2), …,? (n))
Ayant n composantes tels que ? (i) soit égal à la longueur du plus court chemin allant de 1 au sommet i. On initialise ce vecteur à (C1,i) c’est-à-dire à la première ligne de la matrice des coûts du graphe. On considère ensuite deux ensembles de sommets, S est initialisé à {1} et S son complémentaire dans X.
A chaque pas de l’algorithme, on ajoute à S des sommets jusqu’à ce que S = X de telle sorte que le vecteur ? donne, à chaque étape, le coût minimal des chemins de 1 aux sommets de S.
Algorithme de construction d’un arbre de recouvrement
Description
On choisit un sommet arbitraire du graphe, puis on construit à partir de ce sommet une chaîne simple en ajoutant des arêtes de G tant que c’est possible. Si la chaine ainsi construite contient tous les sommets du graphe, la chaine est un arbre de recouvrement. Sinon, on retourne à l’avant dernier sommet de la chaîne et à partir de celui-ci, et si c’est possible, on construit une nouvelle chaine simple aussi longue que possible et ne contenant aucun sommet du premier chemin construit. Si ce n’est pas possible, il faut remonter à l’antépénultième sommet et recommencer. Si le graphe est connexe, on peut réitérer ce processus jusqu’à épuisement des sommets pour obtenir un arbre de recouvrement.
Méthode d’ordonnancement des taches
Un ordonnancement consiste à placer dans un certain ordre chronologique des opérations qui ne sont pas généralement pas indépendantes et qui font intervenir des dépenses des ressources des performances et du temps. Alors il consiste à organiser l’exécution des tâches en vue d’atteindre un objectif fixé. Ces tâches sont soumises à un ensemble des contraintes qui peuvent être classées en trois types :
Les contraintes
Les contraintes potentielles
Ceux sont des contraintes de localisation temporelle dans les quelles se situent la date limite et la date initiale des tâches
a) Date initiale : la tâche i ne doit pas commencer avant telle date.
b) Date limite : la tâche i doit être impérativement achevée à telle date.
Les contraintes disjonctives
Elles interdisent la réalisation simultanée de deux tâches utilisant un moyen unique Dans certains cas, ces contraintes peuvent être ramenées aux types potentiels .
Les contraintes cumulatives
Elles considèrent un certain niveau maximal de disponibilité à un instant donné, et des différents moyens indispensables pour la réalisation d’un projet. Nous allons voir comment la théorie des graphes peut être efficace à la recherche des solutions de divers problèmes d’ordonnancement Pour cela, on va utiliser la méthode MPM.
Méthode MPM (ou Méthode des potentiels METRA ou Méthode potentielstâches) .
C’est une méthode étudiée en France dès 1957 sous la direction de B.ROY et ayant été appliquée à la construction du paquebot France en 1960. Cette méthode est fondée sur la théorie des graphes. En effet, elle considère un graphe orienté sans circuit G= (X, Γ) ou X est la liste des tâches (sommets) et Γest l’ensemble des contraintes (arcs) Elle permet :
– d’établir un ordonnancement, dès l’instant qu’aucune contrainte n’est contradictoire avec un autre.
– de déterminer le meilleur temps total nécessaire à la réalisation de l’objectif (la date au plus tôt de la fin du projet et les dates au plus tard de l’exécution de chaque tâche) .
|
Table des matières
INTRODUCTION GENERALE
PREMIERE PARTIE : QUELQUES ELEMENTS DES GRAPHES
I. Historique de la théorie des graphes
I.1. Rappels mathématiques des ensembles
I.2. Relation binaire d’un ensemble
I.3. Représentation schématique d’une relation binaire
I.4. Propriétés d’une relation binaire
II. Graphes
II.1. Graphe non orienté
II.2. Graphe orienté
III. Degré d’un sommet d’un graphe
IV. Chemin dans un graphe
V. Graphe Eulerien
VI. Graphe Hamiltonien
VII. CONNEXITE
VIII. Arbre et Arborescence
IX. Matrice d’adjacence
IX.1. Recherche du nombre de chemins de longueur k
IX.2. Matrice du coût d’un chemin d’un graphe valué
IX.3. Matrice du coût minimum
X. Coloration minimale d’un graphe
X.1. Nombre chromatique
X.2. Partie stable d’un graphe
Conclusion de la première partie
DEUXIEME PARTIE : APPLICATION DES GRAPHES DANS CERTAINS PROJETS
Chapitre 1 : Problème du court chemin
I. Algorithme de Edsger Dijkstra
I.1. Présentation
I.2. Algorithme de Dijkstra
I.3. Application dans le programme du vol
I.4. Problème de sécurité
I.5. Problème des ponts de Königsberg
II. Algorithme de FORD
II.1. Présentation
II.2. Application dans le problème de circulation
III. Algorithme de DANTZIG
III.1. Description
III.2. Application dans le problème de circulation
Chapitre 2 : Problème de coloriages
I. Problème des Provinces
II. Problème d’une carte
III. Algorithme de Welch et Powell
III.1. Description
III.2. Application dans le problème d’une carte
IV. Problème du Parc
V. Problème d’emploi du temps
VI. Problème d’aquariophilie
Chapitre 3 : Construction d’un arbre de recouvrement
I. Algorithme de construction d’un arbre de recouvrement
I.1. Description
I.2. Application de l’algorithme
I.3. Problème routier
II. Algorithme de Solin Calestagne
II.1. Description
II.2. Problème de réseau de communication
Chapitre 4 : Méthode d’ordonnancement des tâches
I.Les contraintes
II. Méthode M.P.M
III. Application de la méthode MPM : Problème de commande
III.1. Les dates au plus tôt des débuts des tâches
III.2. Les dates au plus tard des débuts des tâches
III.3. La marge (intervalle de flottement)
IV. Modification d’un ordonnancement
V. Méthode PERT
Conclusion partielle
TROISIEME PARTIE : IMPORTANCE DES ELEMENTS DES GRAPHES AU LYCEE
I. Application de l’arbre de choix
I.1. Jeu de pile ou face
I.2. Organigramme d’une hiérarchie scolaire
II. Conservation du flux
II.1. Recherche d’intensité
II.2. Conservation de l’énergie
III. Coloration de quelques molécules
III.1. Géométrie de quelques molécules
III.2. Coloration des molécules
CONCLUSION GENERALE
