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 .................................................................................................................................... 61 |
Côte titre : |
MAM/0367 |
En ligne : |
https://drive.google.com/file/d/1UEoNQVoQMTMwPuO4H7sKrvqFmS1c4Rjw/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
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 .................................................................................................................................... 61 |
Côte titre : |
MAM/0367 |
En ligne : |
https://drive.google.com/file/d/1UEoNQVoQMTMwPuO4H7sKrvqFmS1c4Rjw/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
|