Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours theorie graphes version etudiant

Université Cadi Ayyad Ecole Nationale des Sciences Appliquées ?? Marrakech Filière Génie Industriel et Logistique Niveau ème année du Cycle Ingénieur Réalisé par Pr Badr DAKKAK Docteur en Génie Industriel Ecole Nationale des Sciences Appliquées - Marrakech Année universitaire CTable des matières CHAPITRE INTRODUCTION A LA THEORIE DES GRAPHES Introduction Exemples de situations pouvant être traduites en un graphe Objectifs pédagogiques Dé ?nition d ? un graphe Remarques et dé ?nitions Représentation d ? un graphe Représentation par dictionnaire Représentation matricielle Degré d ? un graphe Vocabulaire de la théorie des Graphes Chemin Chemin hamiltonien Chemin simple Circuit Cha? ne Graphe complet Connexité Recherche de niveau dans un graphe sans circuits Chemin de longueur K Matrice booléenne Matrice aux arcs Chemins élémentaires ?? chemins hamiltoniens Dé ?nition Chemin élémentaire de longueur Chemin élémentaire de longueur Chemin élémentaire de longueur Chemin élémentaire de longueur Fermeture transitive d ? un graphe Dé ?nition Exemple Exercice CHAPITRE RECHERCHE DE CHEMINS OPTIMAUX DANS UN GRAPHE Introduction Algorithme de Ford pour la recherche de plus long chemin Problème Algorithme de Ford Algorithme de Ford pour la recherche du plus court chemin Algorithme de Dijkstra Cas des valeurs positives CHAPITRE PROBLEMES D ? ORDONNANCEMENT Introduction Données d ? un problème d ? ordonnancement Les t? ches Les ressources Résolution d ? un problème d ? ordonnancement Méthode PERT Program Evaluation and Review Technique Méthode des potentiels Métra MPM Représentation graphique du réseau MPM Construction du réseau MPM Méthode du tableau pour la recherche des chemins critiques et des dates attendues CHAPITRE PROBLEMES D ? AFFECTATION Introduction Méthode de résolution du problème d ? a ?ectation Méthode Hongroise CHAPITRE LES PROGRAMMES DE TRANSPORT Position du problème Exemple Recherche d ? une solution de base Méthode du coin Nord- Ouest Méthode Procédure MINILI MINI-LINE Méthode MINICO minimum des colonnes Méthode MINITAB Méthode de la di ?érence ?? maximale ou de BALAS ?? HAMMER Pr Badr DAKKAK CCHAPITRE INTRODUCTION A LA THEORIE DES GRAPHES Introduction La théorie des graphes née en quand Euler démontra qu ? il était impossible de traverser chacun des sept ponts de la ville de K? nigsberg ?gure une fois exactement et y revenir au point de départ B D A C Figure Les sept ponts de la ville de K? nigsberg La théorie des graphes est un des instruments les plus courants et les plus e ?caces pour résoudre des problèmes concrets à l ? aide d ? un graphe La théorie des graphes est une tentative de visualisation concrète des faits au moyen de dessin permettant d ? exprimer le problème posé L ? ingénieur moderne ne peut plus limiter ses préoccupations à l ? organisation de la fabrication ou la direction de la recherche il est intégré à la gestion de l ? entreprise toute entière et son souci doit être de fabriquer au meilleur prix et d ? inventer au moindre coût Il doit donc appliquer les méthodes de la RO et de la théorie des graphes Exemples de situations pouvant