University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Abdelhamid Benhocine |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Les différents Graphes pert Type de document : texte imprimé Auteurs : Gussoum ,Nabila, Auteur ; Abdelhamid Benhocine, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (75 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Ordonnancement de projet
Biparti complet
Graphe adjoint
Gantt
MPMRésumé : Après avoir étudié la modélisation de l‘ordonnancement de projet par le biais du
diagramme de Gantt, la méthode MPM et la méthode PERT, on conclue que les managers
de projet préfèrent travailler avec le graphe PERT malgré qu‘il est difficile à réaliser, alors
que le graphe des potentiels offre plus de simplicité.
Dans ce mémoire nous avons présenté deux idées originales de dessin du graphe PERT.
La première consiste à balayer la table d‘ordonnancement ligne par ligne et dessiner, à
chaque étape, un arc qui s‘ajoute à ce qui a été construit avant. La deuxième consiste à
localiser les bipartis complets dans le graphe des potentiels et les transformer au fur et à
mesure en étoiles adjacentes constituant le graphe PERT à l‘aide d‘un ensemble de
concepts et de résultats sur les graphes adjoints de graphe. Cette idée a été optimisée à deux
reprises en vue d‘avoir un graphe PERT moins encombrant, facile à lire et à contrôler.Note de contenu : Sommaire
Dédicaces………………………………………………………………………..
Remrciements……………………………………………………………......….
Table des matières.........................................................................................
Liste des figures..............................................................................................
Liste des tableaux..........................................................................................
Liste des abréviations.....................................................................................
Notations..............................................................................................................
Introduction générale...........................................................................................1
Chapitre1: Quelques rappels sur la théorie des graphes....................................1
1.1 Introduction...........................................................................................................................
1.2 Définitions et Concepts de bases.........................................................................................
1.2.1 Graphes non orientés...................................................................................................
1.2.2 Graphes orientés.........................................................................................................
1.2.3 Différents types de graphes.........................................................................................
1.2.3.1 Graphe simple.................................................................................................
1.2.3.2 Multi-graphe .................................................................................................
1.2.3.3 Graphe connexe...............................................................................................
1.2.3.4 Graphe complet...............................................................................................
1.2.3.5 Graphe biparti.................................................................................................
1.2.3.6 Sous-graphe....................................................................................................
1.2.3.7 Graphe partiel.................................................................................................
1.2.3.8 Sous-graphe partiel.........................................................................................
1.2.4 Représentations des graphes.......................................................................................
1.2.4.1 Matrice d’adjacence.......................................................................................
1.2.4.2 Liste d’adjacence...........................................................................................
1.2.5 Notions de chemin, chaine, cycle et circuit...............................................................
1.2.5.1 Cas des graphes orientés................................................................................
1.2.5.2 Cas des graphes non orientés.........................................................................
1.2.6 Connexité et forte connexité.....................................................................................
1.2.6.1 Connexité.....................................................................................................
1.2.6.2 Forte connexité...........................................................................................
1.2.7 Graphes Eulérien et graphes Hamiltonien................................................................
1.2.7.1 Graphe Eulérien...........................................................................................
1.2.7.2 Graphe Hamiltoniens...................................................................................
1.2.8 Graphe sans circuits.................................................................................................
3V
1.3 Conclusion............................................................................................................................
Chapitre 2 : Ordonnancement de projet.............................................................
2.1 Introduction......................................................................................................................
2.2 Définitions de la gestion de projet.....................................................................................
2.3 Définition d’un projet.........................................................................................................
2.3.1 Les caractéristiques d’un projet................................................................................
2.3.2 Les acteurs du projet.................................................................................................
2.3.3 Cycle de vie d’un projet............................................................................................
2.3.5 L’ordonnancement dans la gestion de projet...........................................................
2.4 Le problème central de l’ordonnancement.............................................................................
2.4.1 Éléments du problème d’ordonnancement....................................................................
2.4.1.1 Les tâches......................................................................................................
2.4.1.2 Les ressources.................................................................................................
2.4.1.3 Les contraintes...............................................................................................
2.4.1.4 Les objectifs..................................................................................................
2.4.2 Modélisation du problème central...............................................................................
2.4.2.1 Le diagramme de Gantt.................................................................................
2.4.2.1.1 Définition.......................................................................................
2.4.2.1.2 Présentations..................................................................................
2.4.2.1.3 La réalisation d’un diagramme de Gantt.......................................
2.4.2.1.4 Les avantages du diagramme de Gantt..........................................
2.4.2.1.5 Les inconvénients du diagramme de Gantt...................................
2.4.2.2 Méthode des potentiels (MPM).....................................................................
2.4.2.2.1 Définition.......................................................................................
2.4.2.2.2 Méthodologie de construction d’un réseau MPM.........................
2.4.2.2.3 Les avantages de MPM.................................................................
2.4.2.3 La méthode PERT.........................................................................................
2.4.2.3.1 Généralité.......................................................................................
2.4.2.3.2 Les objectifs de la méthode PERT...............................................
2.4.2.3.3 Les conditions préalables à la construction du graphe PERT……
2.4.2.3.4 La construction d’un graphe PERT..............................................
2.4.2.3.5 Dessin du graphe PERT................................................................
2.4.2.3.6 Notion de tâche fictive..................................................................
2.5 Résolution du problème central............................................................................................
2.5.1 Dates et marges associées à une tâche........................................................................
2.5.1.1 Dates d’une tâche...........................................................................................
2.5.1.2 Marges d’une tâche........................................................................................
2.5.2 Calcul des dates et marges..........................................................................................
2.5.2.1 Calcul des dates..............................................................................................
2.5.2.2 Calcul des marges ..........................................................................................
2.5.3 Qu’est-ce que le chemin critique? ...............................................................................
2.6 PERT probabilisé ou PERT aléatoire....................................................................................
2.6.1 Introduction ................................................................................................................
2.6.2 La fonction Bêta ()....................................................................................................
2.7 Le PERT coût........................................................................................................................
2.7.1 Introduction...............................................................................................................
2.7.2 Diminution du coût total du projet............................................................................
2.7.3 Accélération du projet au moindre coût....................................................................
2.8 Conclusion............................................................................................................................
Chapitre 3 : La construction du graphe PERT à partie du graphe des potentiels………………………………………………………………..………
3.1 Introduction...........................................................................................................................
3.2 Le graphe adjoint de graphe..................................................................................................
3.2.1 Le problème inverse....................................................................................................
3.2.1.1 Définition de la configuration « Z » et « »..................................................
3.2.1.1.1 La configuration « Z »....................................................................
3.2.1.1.2 La configuration « ».....................................................................
3.2.2 Quelques caractérisations des graphes adjoints...........................................................
3.3 Passage du graphe potentiel au graphe PERT......................................................................
3.3.1 Cas où le graphe des potentiels est un graphe adjoint................................................
3.3.2 Cas où le graphe des potentiels n’est pas un graphe adjoint......................................
3.4 Liens entre le graphe PERT et le graphe des potentiels.......................................................
3.5 Conclusion...........................................................................................................................
Chapitre 4 : Application……………………………………………………….
Conclusion générale……………………………………………….….………
Bibliographies…………………………………………………………………
Annexe…………………………………………………………………………
Résumé…………………………………………………………………………Côte titre : MAM/0278 En ligne : https://drive.google.com/file/d/1Im8PS6C4jzedgN_-spSit5kwX4deo90U/view?usp=shari [...] Format de la ressource électronique : Les différents Graphes pert [texte imprimé] / Gussoum ,Nabila, Auteur ; Abdelhamid Benhocine, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (75 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Ordonnancement de projet
Biparti complet
Graphe adjoint
Gantt
MPMRésumé : Après avoir étudié la modélisation de l‘ordonnancement de projet par le biais du
diagramme de Gantt, la méthode MPM et la méthode PERT, on conclue que les managers
de projet préfèrent travailler avec le graphe PERT malgré qu‘il est difficile à réaliser, alors
que le graphe des potentiels offre plus de simplicité.
Dans ce mémoire nous avons présenté deux idées originales de dessin du graphe PERT.
La première consiste à balayer la table d‘ordonnancement ligne par ligne et dessiner, à
chaque étape, un arc qui s‘ajoute à ce qui a été construit avant. La deuxième consiste à
localiser les bipartis complets dans le graphe des potentiels et les transformer au fur et à
mesure en étoiles adjacentes constituant le graphe PERT à l‘aide d‘un ensemble de
concepts et de résultats sur les graphes adjoints de graphe. Cette idée a été optimisée à deux
reprises en vue d‘avoir un graphe PERT moins encombrant, facile à lire et à contrôler.Note de contenu : Sommaire
Dédicaces………………………………………………………………………..
Remrciements……………………………………………………………......….
Table des matières.........................................................................................
Liste des figures..............................................................................................
Liste des tableaux..........................................................................................
Liste des abréviations.....................................................................................
Notations..............................................................................................................
Introduction générale...........................................................................................1
Chapitre1: Quelques rappels sur la théorie des graphes....................................1
1.1 Introduction...........................................................................................................................
1.2 Définitions et Concepts de bases.........................................................................................
1.2.1 Graphes non orientés...................................................................................................
1.2.2 Graphes orientés.........................................................................................................
1.2.3 Différents types de graphes.........................................................................................
1.2.3.1 Graphe simple.................................................................................................
1.2.3.2 Multi-graphe .................................................................................................
1.2.3.3 Graphe connexe...............................................................................................
1.2.3.4 Graphe complet...............................................................................................
1.2.3.5 Graphe biparti.................................................................................................
1.2.3.6 Sous-graphe....................................................................................................
1.2.3.7 Graphe partiel.................................................................................................
1.2.3.8 Sous-graphe partiel.........................................................................................
1.2.4 Représentations des graphes.......................................................................................
1.2.4.1 Matrice d’adjacence.......................................................................................
1.2.4.2 Liste d’adjacence...........................................................................................
1.2.5 Notions de chemin, chaine, cycle et circuit...............................................................
1.2.5.1 Cas des graphes orientés................................................................................
1.2.5.2 Cas des graphes non orientés.........................................................................
1.2.6 Connexité et forte connexité.....................................................................................
1.2.6.1 Connexité.....................................................................................................
1.2.6.2 Forte connexité...........................................................................................
1.2.7 Graphes Eulérien et graphes Hamiltonien................................................................
1.2.7.1 Graphe Eulérien...........................................................................................
1.2.7.2 Graphe Hamiltoniens...................................................................................
1.2.8 Graphe sans circuits.................................................................................................
3V
1.3 Conclusion............................................................................................................................
Chapitre 2 : Ordonnancement de projet.............................................................
2.1 Introduction......................................................................................................................
2.2 Définitions de la gestion de projet.....................................................................................
2.3 Définition d’un projet.........................................................................................................
2.3.1 Les caractéristiques d’un projet................................................................................
2.3.2 Les acteurs du projet.................................................................................................
2.3.3 Cycle de vie d’un projet............................................................................................
2.3.5 L’ordonnancement dans la gestion de projet...........................................................
2.4 Le problème central de l’ordonnancement.............................................................................
2.4.1 Éléments du problème d’ordonnancement....................................................................
2.4.1.1 Les tâches......................................................................................................
2.4.1.2 Les ressources.................................................................................................
2.4.1.3 Les contraintes...............................................................................................
2.4.1.4 Les objectifs..................................................................................................
2.4.2 Modélisation du problème central...............................................................................
2.4.2.1 Le diagramme de Gantt.................................................................................
2.4.2.1.1 Définition.......................................................................................
2.4.2.1.2 Présentations..................................................................................
2.4.2.1.3 La réalisation d’un diagramme de Gantt.......................................
2.4.2.1.4 Les avantages du diagramme de Gantt..........................................
2.4.2.1.5 Les inconvénients du diagramme de Gantt...................................
2.4.2.2 Méthode des potentiels (MPM).....................................................................
2.4.2.2.1 Définition.......................................................................................
2.4.2.2.2 Méthodologie de construction d’un réseau MPM.........................
2.4.2.2.3 Les avantages de MPM.................................................................
2.4.2.3 La méthode PERT.........................................................................................
2.4.2.3.1 Généralité.......................................................................................
2.4.2.3.2 Les objectifs de la méthode PERT...............................................
2.4.2.3.3 Les conditions préalables à la construction du graphe PERT……
2.4.2.3.4 La construction d’un graphe PERT..............................................
2.4.2.3.5 Dessin du graphe PERT................................................................
2.4.2.3.6 Notion de tâche fictive..................................................................
2.5 Résolution du problème central............................................................................................
2.5.1 Dates et marges associées à une tâche........................................................................
2.5.1.1 Dates d’une tâche...........................................................................................
2.5.1.2 Marges d’une tâche........................................................................................
2.5.2 Calcul des dates et marges..........................................................................................
2.5.2.1 Calcul des dates..............................................................................................
2.5.2.2 Calcul des marges ..........................................................................................
2.5.3 Qu’est-ce que le chemin critique? ...............................................................................
2.6 PERT probabilisé ou PERT aléatoire....................................................................................
2.6.1 Introduction ................................................................................................................
2.6.2 La fonction Bêta ()....................................................................................................
2.7 Le PERT coût........................................................................................................................
2.7.1 Introduction...............................................................................................................
2.7.2 Diminution du coût total du projet............................................................................
2.7.3 Accélération du projet au moindre coût....................................................................
2.8 Conclusion............................................................................................................................
Chapitre 3 : La construction du graphe PERT à partie du graphe des potentiels………………………………………………………………..………
3.1 Introduction...........................................................................................................................
3.2 Le graphe adjoint de graphe..................................................................................................
3.2.1 Le problème inverse....................................................................................................
3.2.1.1 Définition de la configuration « Z » et « »..................................................
3.2.1.1.1 La configuration « Z »....................................................................
3.2.1.1.2 La configuration « ».....................................................................
3.2.2 Quelques caractérisations des graphes adjoints...........................................................
3.3 Passage du graphe potentiel au graphe PERT......................................................................
3.3.1 Cas où le graphe des potentiels est un graphe adjoint................................................
3.3.2 Cas où le graphe des potentiels n’est pas un graphe adjoint......................................
3.4 Liens entre le graphe PERT et le graphe des potentiels.......................................................
3.5 Conclusion...........................................................................................................................
Chapitre 4 : Application……………………………………………………….
Conclusion générale……………………………………………….….………
Bibliographies…………………………………………………………………
Annexe…………………………………………………………………………
Résumé…………………………………………………………………………Côte titre : MAM/0278 En ligne : https://drive.google.com/file/d/1Im8PS6C4jzedgN_-spSit5kwX4deo90U/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0278 MAM/0278 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Graphes Aléatoires et Application à la Coloration des Sommets d’un graphe Type de document : texte imprimé Auteurs : Rechidi,imane, Auteur ; Abdelhamid Benhocine, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (50 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématique Index. décimale : 510 Mathématique Résumé : Sommaire
Remerciement ........................................................................................................................... I
Dédicace ................................................................................................................................... II
Table des matières .................................................................................................................. III
Liste des figures ...................................................................................................................... VI
Liste des tableaux ................................................................................................................... VII
Liste des abréviations ............................................................................................................ VIII
Introduction générale ........................................................................................................ 1
Chapitre 01 : Terminologie de la théorie des graphes .......................................... 3
1.1 Introduction ........................................................................................................................ 3
1.2 Qu'est-ce qu'un graphe ........................................................................................................ 3
1.3 Graphe orienté ..................................................................................................................... 3
1.3.1 Les éléments de base d'un graphe orienté ................................................................ 4
1.3.2 L'ensemble des voisins ............................................................................................. 4
1.3.3 Degré d'un sommet .................................................................................................. 5
1.4 Graphe non orienté ............................................................................................................. 5
1.4.1 Les éléments de base d'un graphe non orienté .......................................................... 6
1.5 Chemin, Chaîne, Cycle, Circuit .......................................................................................... 6
1.5.1 Chemin, Chaîne, Cycle et Circuit simple ................................................................. 6
1.5.2 Chemin, Chaîne, Cycle et Circuit élémentaires ........................................................ 6
1.5.3 Chemin, Chaîne, Cycle et Circuit hamiltoniens ....................................................... 6
1.5.4 Chemin, Chaîne, Cycle et Circuit eulériens ............................................................. 6
1.6 Quelques graphes particuliers ............................................................................................ 6
1.6.1 Graphe simple .......................................................................................................... 6
1.6.2 Graphe complet ........................................................................................................ 7
1.6.3 Graphe biparti ........................................................................................................... 7
1.6.4 Graphe biparti complet ............................................................................................ 8
1.6.5 Graphe pondéré ........................................................................................................ 8
1.6.6 Graphe partiel et sous graphe ................................................................................... 8
1.7 Les graphes sans circuit ....................................................................................................... 9
1.8 Les graphes avec circuit .................................................................................................... 10
1.9 Connexité et forte connexité ............................................................................................. 11
1.9.1 Connexité d’un graphe ........................................................................................... 11
1.9.2 Forte connexité d’un graphe ................................................................................... 12
1.10 Mode de représentation graphique .................................................................................. 12
1.10.1 Liste de successeurs ou voisins ............................................................................ 12
1.10.2 Matrice d'adjacence sommets-sommets (matss) ................................................. 13
1.10.3 Matrice d'incidence sommets-arcs ........................................................................ 13
1.11 Conclusion ....................................................................................................................... 14
IV
Chapitre 02 : Les heuristiques et les métaheuristiques ....................................... 15
2.1 Introduction ...................................................................................................................... 15
2.2 Définition d’un problème d’optimisation combinatoire ................................................... 15
2.3 Classification des méthodes d’optimisation (résolution) ................................................. 15
2.3.1 Les méthodes exactes .......................................................................................... 16
2.3.2 Les méthodes approchées ................................................................................... 16
2.3.3 Les méthodes hybrides ........................................................................................ 17
2.4 Les méthodes approchées .................................................................................................. 17
2.4.1 Les heuristiques .................................................................................................... 17
2.4.2 Les métaheuristiques ........................................................................................... 17
2.5 Classification des métaheuristiques ................................................................................. 18
2.5.1 Algorithme de glouton ........................................................................................ 18
2.5.2 Recuit simulé ....................................................................................................... 18
2.5.3 Recherche tabou .................................................................................................. 19
2.5.4 Algorithme génétique .......................................................................................... 19
2.5.5 Algorithme colonies de fourmis .......................................................................... 19
2.6 Conclusion ......................................................................................................................... 20
Chapitre 03 : Quelques graphes aléatoires et étude mathématique .............. 21
3.1 Introduction ....................................................................................................................... 21
3.2 Ce qu’est un graphe aléatoire ............................................................................................ 21
3.3 L’utilité des graphes aléatoires .......................................................................................... 21
3.4 Différents modèles de graphes aléatoires .......................................................................... 22
3.4.1 Modèle d’Erdös et Rényi ...................................................................................... 22
3.4.2 Modèle de Molloy et Reed ................................................................................... 22
3.4.3 Modèle d’Albert et Barad’asi ............................................................................... 22
3.5 Génération de quelques graphes aléatoires ....................................................................... 22
3.5.1 Génération d’un graphe aléatoire orienté quelconque .......................................... 22
3.5.2 Génération des arbres aléatoires ........................................................................... 23
3.5.3 Génération des graphes aléatoires connexes à l’aide des arbres aléatoires .......... 26
3.5.4 Génération des graphes aléatoires non connexes à l’aide des arbres aléatoires ... 27
3.5.5 Génération des graphes aléatoires avec chemin Hamiltonien .............................. 27
3.5.6 Génération des graphes aléatoires avec circuit Hamiltonien ............................... 27
3.6 Conclusion ......................................................................................................................... 28
Chapitre 04 : Coloration des sommets d’un graphe ............................................ 29
4.1 Introduction ....................................................................................................................... 29
4.2 Un peu d’histoire .............................................................................................................. 29
4.3 Coloration des sommets d’un graphe ................................................................................ 29
4.4 Domaines d’application de la coloration des graphes ....................................................... 30
4.5 Coloration des arêtes d’un graphe ..................................................................................... 32
V
4.6 Coloration des faces d’un graphe planaire ........................................................................ 33
4.7 Nombre chromatique d’un graphe G ................................................................................. 35
4.7.1 Définition .............................................................................................................. 35
4.7.2 Ensemble stable .................................................................................................... 35
4.7.3 Définition d’une clique ......................................................................................... 36
4.7.4 Quelques bornes pour le nombre chromatique d’un graphe ................................. 36
4.8 Quelques algorithmes de coloration des sommets d’un graphe ........................................ 37
4.8.1 L’algorithme glouton élémentaire ......................................................................... 37
4.8.2 L’algorithme de Welsh et Powell .......................................................................... 38
4.8.3 L’algorithme DSATUR ......................................................................................... 39
4.8.4 L’algorithme de Vitavert ...................................................................................... 39
4.9 Quelques familles des graphes dont le nombre chromatique est connu ............................ 40
4.9.1 La famille des graphes bipartis .............................................................................. 40
4.9.2 La famille des graphes Petersen ............................................................................ 41
4.10 Conclusion ....................................................................................................................... 46
Chapitre 05 : Application ............................................................................................... 47
5.1 Introduction ...................................................................................................................... 47
5.2 Stratégie ............................................................................................................................. 47
5.3 La construction de quelques familles des graphes ........................................................... 47
5.3.1 Familles avec nombre chromatique connu ........................................................... 47
5.3.2 Familles avec nombre chromatique non connu .................................................... 50
5.4 Application d’algorithmes de la coloration sur quelques familles ................................... 53
5.4.1 Algorithme de Vitavert sur la famille de Petersen ................................................ 53
5.4.2 Algorithme de glouton sur la famille biparti ......................................................... 56
Conclusion générale ................................................................................................................. 59
Bibliographie ............................................................................................................................ 60
ملخص ......................................................................................................................................... 61
Résumé ..................................................................................................................................... 61
Abstract .................................................................................................................................... 61Côte titre : MAM/0367 En ligne : https://drive.google.com/file/d/1UEoNQVoQMTMwPuO4H7sKrvqFmS1c4Rjw/view?usp=shari [...] Format de la ressource électronique : Graphes Aléatoires et Application à la Coloration des Sommets d’un graphe [texte imprimé] / Rechidi,imane, Auteur ; Abdelhamid Benhocine, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (50 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématique Index. décimale : 510 Mathématique Résumé : Sommaire
Remerciement ........................................................................................................................... I
Dédicace ................................................................................................................................... II
Table des matières .................................................................................................................. III
Liste des figures ...................................................................................................................... VI
Liste des tableaux ................................................................................................................... VII
Liste des abréviations ............................................................................................................ VIII
Introduction générale ........................................................................................................ 1
Chapitre 01 : Terminologie de la théorie des graphes .......................................... 3
1.1 Introduction ........................................................................................................................ 3
1.2 Qu'est-ce qu'un graphe ........................................................................................................ 3
1.3 Graphe orienté ..................................................................................................................... 3
1.3.1 Les éléments de base d'un graphe orienté ................................................................ 4
1.3.2 L'ensemble des voisins ............................................................................................. 4
1.3.3 Degré d'un sommet .................................................................................................. 5
1.4 Graphe non orienté ............................................................................................................. 5
1.4.1 Les éléments de base d'un graphe non orienté .......................................................... 6
1.5 Chemin, Chaîne, Cycle, Circuit .......................................................................................... 6
1.5.1 Chemin, Chaîne, Cycle et Circuit simple ................................................................. 6
1.5.2 Chemin, Chaîne, Cycle et Circuit élémentaires ........................................................ 6
1.5.3 Chemin, Chaîne, Cycle et Circuit hamiltoniens ....................................................... 6
1.5.4 Chemin, Chaîne, Cycle et Circuit eulériens ............................................................. 6
1.6 Quelques graphes particuliers ............................................................................................ 6
1.6.1 Graphe simple .......................................................................................................... 6
1.6.2 Graphe complet ........................................................................................................ 7
1.6.3 Graphe biparti ........................................................................................................... 7
1.6.4 Graphe biparti complet ............................................................................................ 8
1.6.5 Graphe pondéré ........................................................................................................ 8
1.6.6 Graphe partiel et sous graphe ................................................................................... 8
1.7 Les graphes sans circuit ....................................................................................................... 9
1.8 Les graphes avec circuit .................................................................................................... 10
1.9 Connexité et forte connexité ............................................................................................. 11
1.9.1 Connexité d’un graphe ........................................................................................... 11
1.9.2 Forte connexité d’un graphe ................................................................................... 12
1.10 Mode de représentation graphique .................................................................................. 12
1.10.1 Liste de successeurs ou voisins ............................................................................ 12
1.10.2 Matrice d'adjacence sommets-sommets (matss) ................................................. 13
1.10.3 Matrice d'incidence sommets-arcs ........................................................................ 13
1.11 Conclusion ....................................................................................................................... 14
IV
Chapitre 02 : Les heuristiques et les métaheuristiques ....................................... 15
2.1 Introduction ...................................................................................................................... 15
2.2 Définition d’un problème d’optimisation combinatoire ................................................... 15
2.3 Classification des méthodes d’optimisation (résolution) ................................................. 15
2.3.1 Les méthodes exactes .......................................................................................... 16
2.3.2 Les méthodes approchées ................................................................................... 16
2.3.3 Les méthodes hybrides ........................................................................................ 17
2.4 Les méthodes approchées .................................................................................................. 17
2.4.1 Les heuristiques .................................................................................................... 17
2.4.2 Les métaheuristiques ........................................................................................... 17
2.5 Classification des métaheuristiques ................................................................................. 18
2.5.1 Algorithme de glouton ........................................................................................ 18
2.5.2 Recuit simulé ....................................................................................................... 18
2.5.3 Recherche tabou .................................................................................................. 19
2.5.4 Algorithme génétique .......................................................................................... 19
2.5.5 Algorithme colonies de fourmis .......................................................................... 19
2.6 Conclusion ......................................................................................................................... 20
Chapitre 03 : Quelques graphes aléatoires et étude mathématique .............. 21
3.1 Introduction ....................................................................................................................... 21
3.2 Ce qu’est un graphe aléatoire ............................................................................................ 21
3.3 L’utilité des graphes aléatoires .......................................................................................... 21
3.4 Différents modèles de graphes aléatoires .......................................................................... 22
3.4.1 Modèle d’Erdös et Rényi ...................................................................................... 22
3.4.2 Modèle de Molloy et Reed ................................................................................... 22
3.4.3 Modèle d’Albert et Barad’asi ............................................................................... 22
3.5 Génération de quelques graphes aléatoires ....................................................................... 22
3.5.1 Génération d’un graphe aléatoire orienté quelconque .......................................... 22
3.5.2 Génération des arbres aléatoires ........................................................................... 23
3.5.3 Génération des graphes aléatoires connexes à l’aide des arbres aléatoires .......... 26
3.5.4 Génération des graphes aléatoires non connexes à l’aide des arbres aléatoires ... 27
3.5.5 Génération des graphes aléatoires avec chemin Hamiltonien .............................. 27
3.5.6 Génération des graphes aléatoires avec circuit Hamiltonien ............................... 27
3.6 Conclusion ......................................................................................................................... 28
Chapitre 04 : Coloration des sommets d’un graphe ............................................ 29
4.1 Introduction ....................................................................................................................... 29
4.2 Un peu d’histoire .............................................................................................................. 29
4.3 Coloration des sommets d’un graphe ................................................................................ 29
4.4 Domaines d’application de la coloration des graphes ....................................................... 30
4.5 Coloration des arêtes d’un graphe ..................................................................................... 32
V
4.6 Coloration des faces d’un graphe planaire ........................................................................ 33
4.7 Nombre chromatique d’un graphe G ................................................................................. 35
4.7.1 Définition .............................................................................................................. 35
4.7.2 Ensemble stable .................................................................................................... 35
4.7.3 Définition d’une clique ......................................................................................... 36
4.7.4 Quelques bornes pour le nombre chromatique d’un graphe ................................. 36
4.8 Quelques algorithmes de coloration des sommets d’un graphe ........................................ 37
4.8.1 L’algorithme glouton élémentaire ......................................................................... 37
4.8.2 L’algorithme de Welsh et Powell .......................................................................... 38
4.8.3 L’algorithme DSATUR ......................................................................................... 39
4.8.4 L’algorithme de Vitavert ...................................................................................... 39
4.9 Quelques familles des graphes dont le nombre chromatique est connu ............................ 40
4.9.1 La famille des graphes bipartis .............................................................................. 40
4.9.2 La famille des graphes Petersen ............................................................................ 41
4.10 Conclusion ....................................................................................................................... 46
Chapitre 05 : Application ............................................................................................... 47
5.1 Introduction ...................................................................................................................... 47
5.2 Stratégie ............................................................................................................................. 47
5.3 La construction de quelques familles des graphes ........................................................... 47
5.3.1 Familles avec nombre chromatique connu ........................................................... 47
5.3.2 Familles avec nombre chromatique non connu .................................................... 50
5.4 Application d’algorithmes de la coloration sur quelques familles ................................... 53
5.4.1 Algorithme de Vitavert sur la famille de Petersen ................................................ 53
5.4.2 Algorithme de glouton sur la famille biparti ......................................................... 56
Conclusion générale ................................................................................................................. 59
Bibliographie ............................................................................................................................ 60
ملخص ......................................................................................................................................... 61
Résumé ..................................................................................................................................... 61
Abstract .................................................................................................................................... 61Côte titre : MAM/0367 En ligne : https://drive.google.com/file/d/1UEoNQVoQMTMwPuO4H7sKrvqFmS1c4Rjw/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0367 MAM/0367 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Les heuistiques de bin packing Type de document : texte imprimé Auteurs : Nesrine Kourichi, Auteur ; Abdelhamid Benhocine, Directeur de thèse Editeur : Setif:UFA Année de publication : 2021 Importance : 1 vol (48 f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Optimisation combinatoire
Bin packing
HeuristiqueIndex. décimale : 510 Mathématique Résumé : Le problème de bin packing se retrouve dans plusieurs domaines d’application, essentiellement dans l’industrie : tôle, bois, verre, papier etc.
Dans ce mémoire, nous traitons le problème de minimisation de l’utilisation des nombres de bins identique pour ranger un nombre fini d’objets. Ce problème d’optimisation combinatoire étant du type NP-difficile, nous avons utilisé des heuristiques pour le résoudre vu que les algorithmes exacts exigeraient plus de ressources temporelles. L’objective est d’utiliser la meilleure façon (heuristique) possible pour résoudre ce problème.
Côte titre : MAM/0524 En ligne : https://docs.google.com/document/d/13DqBqyzi4-guOkF-zkXfB-wV-vlarjQP/edit?usp=sh [...] Format de la ressource électronique : doc Les heuistiques de bin packing [texte imprimé] / Nesrine Kourichi, Auteur ; Abdelhamid Benhocine, Directeur de thèse . - [S.l.] : Setif:UFA, 2021 . - 1 vol (48 f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Optimisation combinatoire
Bin packing
HeuristiqueIndex. décimale : 510 Mathématique Résumé : Le problème de bin packing se retrouve dans plusieurs domaines d’application, essentiellement dans l’industrie : tôle, bois, verre, papier etc.
Dans ce mémoire, nous traitons le problème de minimisation de l’utilisation des nombres de bins identique pour ranger un nombre fini d’objets. Ce problème d’optimisation combinatoire étant du type NP-difficile, nous avons utilisé des heuristiques pour le résoudre vu que les algorithmes exacts exigeraient plus de ressources temporelles. L’objective est d’utiliser la meilleure façon (heuristique) possible pour résoudre ce problème.
Côte titre : MAM/0524 En ligne : https://docs.google.com/document/d/13DqBqyzi4-guOkF-zkXfB-wV-vlarjQP/edit?usp=sh [...] Format de la ressource électronique : doc Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0524 MAM/0524 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Heuristiques de la Coloration de Graphes Type de document : texte imprimé Auteurs : Asma Kheribeche, Auteur ; Abdelhamid Benhocine, Directeur de thèse Editeur : Setif:UFA Année de publication : 2021 Importance : 1 vol (55 f.) Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Graphe
Coloration des sommetsIndex. décimale : 510 Mathématique Résumé :
Le problème de coloration des graphes est un problème célèbre, dont on distingue trois types (la coloration des sommets, la coloration des arêtes et la coloration des faces).
Ce mémoire s’intéresser à la coloration des sommets. On cherche à minimiser le nombre de couleurs utilisées. Le plus petit nombre de couleurs permettant la coloration des sommets d’un graphe est appelé le nombre chromatique.
Les heuristiques de la coloration des sommets d’un graphe ne donnent pas forcement le nombre minimum de couleurs.
Côte titre : MAM/0527 En ligne : https://docs.google.com/document/d/1fFuw4pLbw-bM_rE8RbBLXPyMg0FRxPyI/edit?usp=sh [...] Format de la ressource électronique : doc Heuristiques de la Coloration de Graphes [texte imprimé] / Asma Kheribeche, Auteur ; Abdelhamid Benhocine, Directeur de thèse . - [S.l.] : Setif:UFA, 2021 . - 1 vol (55 f.).
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Graphe
Coloration des sommetsIndex. décimale : 510 Mathématique Résumé :
Le problème de coloration des graphes est un problème célèbre, dont on distingue trois types (la coloration des sommets, la coloration des arêtes et la coloration des faces).
Ce mémoire s’intéresser à la coloration des sommets. On cherche à minimiser le nombre de couleurs utilisées. Le plus petit nombre de couleurs permettant la coloration des sommets d’un graphe est appelé le nombre chromatique.
Les heuristiques de la coloration des sommets d’un graphe ne donnent pas forcement le nombre minimum de couleurs.
Côte titre : MAM/0527 En ligne : https://docs.google.com/document/d/1fFuw4pLbw-bM_rE8RbBLXPyMg0FRxPyI/edit?usp=sh [...] Format de la ressource électronique : doc Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0527 MAM/0527 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Optimisation dans les problèmes d’ordonnancement de projets Type de document : texte imprimé Auteurs : Chaima Belhaouchat, Auteur ; Abdelhamid Benhocine, Directeur de thèse Editeur : Setif:UFA Année de publication : 2021 Importance : 1 vol (50 f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Ordonnancement de projet
GanttIndex. décimale : 510 Mathématique Résumé :
Dans cette mémoire, nous étudions l’ordonnancement des projets en utilisant le diagramme de
Gantt, la méthode de MPM, la méthode de PERT. Il a été constaté que la direction de projet préfère
utiliser la méthode PERT, malgré la difficulté de la réaliser. Nous avons également abordé le
problème des tâches fictives dans un diagramme PERT.
Nous avons présenté une méthode pour améliorer et réduire au minimum le problème des
tâches fictives dans le graphe PERT.Côte titre : MAM/0526 En ligne : https://drive.google.com/file/d/17l61w0ZZ1t5IKmID1fJVV3ebja1qDMaZ/view?usp=shari [...] Format de la ressource électronique : Optimisation dans les problèmes d’ordonnancement de projets [texte imprimé] / Chaima Belhaouchat, Auteur ; Abdelhamid Benhocine, Directeur de thèse . - [S.l.] : Setif:UFA, 2021 . - 1 vol (50 f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Ordonnancement de projet
GanttIndex. décimale : 510 Mathématique Résumé :
Dans cette mémoire, nous étudions l’ordonnancement des projets en utilisant le diagramme de
Gantt, la méthode de MPM, la méthode de PERT. Il a été constaté que la direction de projet préfère
utiliser la méthode PERT, malgré la difficulté de la réaliser. Nous avons également abordé le
problème des tâches fictives dans un diagramme PERT.
Nous avons présenté une méthode pour améliorer et réduire au minimum le problème des
tâches fictives dans le graphe PERT.Côte titre : MAM/0526 En ligne : https://drive.google.com/file/d/17l61w0ZZ1t5IKmID1fJVV3ebja1qDMaZ/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0526 MAM/0526 Mémoire Bibliothéque des sciences Français Disponible
DisponiblePermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalink