University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Mezouat ,Amira |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Les problèmes de Flots Type de document : texte imprimé Auteurs : Mezouat ,Amira, Auteur ; Abdelhamid Benhocine, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (57 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Flot maximum
Coupe minimum
coût minimumIndex. décimale : 510 Mathématique Résumé : Dans ce mémoire nous étudions un problème très important en recherche opérationnelle nommé les problèmes de flots qui joue un rôle important dans la théorie des graphes. Nous donnons des définitions, des domaines d’applications, des algorithmes avec des exemples illustré qui résoudre les problèmes qui lui correspondant qui sont le problème de flots maximum et le problème de flots maximum à coût minimum. Et aussi nous nous donnons l’utilisation de la théorie de graphes et de flots dans le domaine de traitement d’image. Note de contenu : Sommaire
matières
Dédicaces ............................................................................................................................................ III
Remerciement..................................................................................................................................... III
Table des matières ............................................................................................................................. III
Liste des figures ................................................................................................................................. III
Introduction générale .................................................................................................................. 1
Chapitre 01 : Terminologie de la théorie des graphes ............................ 3
1.1. Introduction ......................................................................................................................... 3
1.1. Définition ............................................................................................................................ 3
1.2.1. Graphe ........................................................................................................................... 4
1.2.1.1. Sous graphe ............................................................................................................. 4
1.2.1.2. Graphe partiel ......................................................................................................... 4
1.2.1.3. Graphe orienté ........................................................................................................ 4
1.2.1.4. Graphe non orienté ................................................................................................. 4
1.2.2. L’ensemble des successeurs, prédécesseurs et voisins d’un sommet ............................ 5
1.2.3. Source et puits ............................................................................................................... 5
1.2.4. Chaîne, cycle, chemin et circuit ................................................................................... 5
1.2.5. Le parcours ................................................................................................................... 6
1.2.5.1. Parcours profondeur (longueur) ............................................................................. 6
1.2.5.2. Parcours largeur ....................................................................................................... 6
1.2.6. La connexité ................................................................................................................. 7
1.2.7. Les arbres ..................................................................................................................... 8
1.2.8. Ordre topologique ........................................................................................................ 8
1.3. Ou nous avons trouvé les graphes ................................................................................... 8
1.4. Conclusion ........................................................................................................................... 9
Chapitre 02 : La théorie des flots ....................................................................... 10
2.1. Introduction ....................................................................................................................... 10
IV
2.2. Quelques application des flots .......................................................................................... 10
2.3. Notions de bases ................................................................................................................ 10
2.3.1. Définition de flot ......................................................................................................... 10
2.3.2. Opérations sur les flots ............................................................................................... 11
2.3.3. Capacité d’un arc ......................................................................................................... 11
2.3.4. Arc saturé et arc non saturé ......................................................................................... 11
2.3.5. Définition d’un réseau ................................................................................................. 12
2.3.6. Définition d’un réseau de transports ........................................................................... 12
2.3.7. Flot réalisable .............................................................................................................. 12
2.3.8. Chaîne augmentante .................................................................................................... 12
2.3.9. Définition d’une coupe ............................................................................................... 13
2.3.10. Graphe d’écart (résiduel) .......................................................................................... 13
2.3.11. Flot complet ............................................................................................................... 14
2.3.12. Flot compatible .......................................................................................................... 14
2.4. Conclusion ......................................................................................................................... 17
Chapitre 03 : Les problèmes des flots ............................................................. 18
3.1. Introduction ....................................................................................................................... 18
3.2. Problème de Flot maximal ................................................................................................ 18
3.2.1. Algorithme de Ford-Fulkerson (1961) ........................................................................ 18
3.2.1.1. Méthode de graphe d’écart .................................................................................... 18
3.2.1.2. Méthode de marquage ........................................................................................... 20
3.2.2. Algorithme de Dinic (1970) ....................................................................................... 33
3.2.3. Algorithme d’Edmonds-Karp (1972) ......................................................................... 34
3.3. Le problème de flot maximal à coût minimal .................................................................. 36
3.3.1. Algorithme de Busaker and Gowen (1961) ................................................................ 36
3.3.2. Algorithme de Bennington (1961) .............................................................................. 38
3.4. Conclusion ......................................................................................................................... 40
V
Chapitre 04 : Graphe et imagerie ...................................................................... 41
4.1. Introduction ...................................................................................................................... 41
4.2. Définitions ........................................................................................................................ 41
4.2.1. Image ........................................................................................................................... 41
4.2.2. Image numérique ....................................................................................................... 41
4.2.3. Pixel ........................................................................................................................... 41
4.2.3.1. Connexité ............................................................................................................ 41
4.3. Types d’image ................................................................................................................. 42
4.3.1. Image binaire ............................................................................................................. 42
4.3.2. Image en niveau de gris ............................................................................................. 42
4.3.3. Image couleur ............................................................................................................ 43
4.4. Représentation des images par des graphes ...................................................................... 43
4.4.1. La segmentation d’image ............................................................................................ 43
4.4.2. Représentation d’une image en niveaux de gris sur machine .................................... 44
4.5. Arbre couvrant de poids minimal ..................................................................................... 45
4.6. Arbre de Gomory-Hu ........................................................................................................ 46
4.7. Application ........................................................................................................................ 47
4.7.1. Exemple appliqué de Gomory-Hu ............................................................................... 47
4.7.2. Application de Gomory-Hu sur l’image ...................................................................... 54
4.8. Conclusion ......................................................................................................................... 55
Conclusion et perspective ......................................................................................................... 56
Bibliographie ............................................................................................................................ 57
RésuméCôte titre : MAM/0326 En ligne : https://drive.google.com/file/d/19JlvSJzp6nja9ttz28uEakrIWLNczC8Q/view?usp=shari [...] Format de la ressource électronique : Les problèmes de Flots [texte imprimé] / Mezouat ,Amira, Auteur ; Abdelhamid Benhocine, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (57 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Flot maximum
Coupe minimum
coût minimumIndex. décimale : 510 Mathématique Résumé : Dans ce mémoire nous étudions un problème très important en recherche opérationnelle nommé les problèmes de flots qui joue un rôle important dans la théorie des graphes. Nous donnons des définitions, des domaines d’applications, des algorithmes avec des exemples illustré qui résoudre les problèmes qui lui correspondant qui sont le problème de flots maximum et le problème de flots maximum à coût minimum. Et aussi nous nous donnons l’utilisation de la théorie de graphes et de flots dans le domaine de traitement d’image. Note de contenu : Sommaire
matières
Dédicaces ............................................................................................................................................ III
Remerciement..................................................................................................................................... III
Table des matières ............................................................................................................................. III
Liste des figures ................................................................................................................................. III
Introduction générale .................................................................................................................. 1
Chapitre 01 : Terminologie de la théorie des graphes ............................ 3
1.1. Introduction ......................................................................................................................... 3
1.1. Définition ............................................................................................................................ 3
1.2.1. Graphe ........................................................................................................................... 4
1.2.1.1. Sous graphe ............................................................................................................. 4
1.2.1.2. Graphe partiel ......................................................................................................... 4
1.2.1.3. Graphe orienté ........................................................................................................ 4
1.2.1.4. Graphe non orienté ................................................................................................. 4
1.2.2. L’ensemble des successeurs, prédécesseurs et voisins d’un sommet ............................ 5
1.2.3. Source et puits ............................................................................................................... 5
1.2.4. Chaîne, cycle, chemin et circuit ................................................................................... 5
1.2.5. Le parcours ................................................................................................................... 6
1.2.5.1. Parcours profondeur (longueur) ............................................................................. 6
1.2.5.2. Parcours largeur ....................................................................................................... 6
1.2.6. La connexité ................................................................................................................. 7
1.2.7. Les arbres ..................................................................................................................... 8
1.2.8. Ordre topologique ........................................................................................................ 8
1.3. Ou nous avons trouvé les graphes ................................................................................... 8
1.4. Conclusion ........................................................................................................................... 9
Chapitre 02 : La théorie des flots ....................................................................... 10
2.1. Introduction ....................................................................................................................... 10
IV
2.2. Quelques application des flots .......................................................................................... 10
2.3. Notions de bases ................................................................................................................ 10
2.3.1. Définition de flot ......................................................................................................... 10
2.3.2. Opérations sur les flots ............................................................................................... 11
2.3.3. Capacité d’un arc ......................................................................................................... 11
2.3.4. Arc saturé et arc non saturé ......................................................................................... 11
2.3.5. Définition d’un réseau ................................................................................................. 12
2.3.6. Définition d’un réseau de transports ........................................................................... 12
2.3.7. Flot réalisable .............................................................................................................. 12
2.3.8. Chaîne augmentante .................................................................................................... 12
2.3.9. Définition d’une coupe ............................................................................................... 13
2.3.10. Graphe d’écart (résiduel) .......................................................................................... 13
2.3.11. Flot complet ............................................................................................................... 14
2.3.12. Flot compatible .......................................................................................................... 14
2.4. Conclusion ......................................................................................................................... 17
Chapitre 03 : Les problèmes des flots ............................................................. 18
3.1. Introduction ....................................................................................................................... 18
3.2. Problème de Flot maximal ................................................................................................ 18
3.2.1. Algorithme de Ford-Fulkerson (1961) ........................................................................ 18
3.2.1.1. Méthode de graphe d’écart .................................................................................... 18
3.2.1.2. Méthode de marquage ........................................................................................... 20
3.2.2. Algorithme de Dinic (1970) ....................................................................................... 33
3.2.3. Algorithme d’Edmonds-Karp (1972) ......................................................................... 34
3.3. Le problème de flot maximal à coût minimal .................................................................. 36
3.3.1. Algorithme de Busaker and Gowen (1961) ................................................................ 36
3.3.2. Algorithme de Bennington (1961) .............................................................................. 38
3.4. Conclusion ......................................................................................................................... 40
V
Chapitre 04 : Graphe et imagerie ...................................................................... 41
4.1. Introduction ...................................................................................................................... 41
4.2. Définitions ........................................................................................................................ 41
4.2.1. Image ........................................................................................................................... 41
4.2.2. Image numérique ....................................................................................................... 41
4.2.3. Pixel ........................................................................................................................... 41
4.2.3.1. Connexité ............................................................................................................ 41
4.3. Types d’image ................................................................................................................. 42
4.3.1. Image binaire ............................................................................................................. 42
4.3.2. Image en niveau de gris ............................................................................................. 42
4.3.3. Image couleur ............................................................................................................ 43
4.4. Représentation des images par des graphes ...................................................................... 43
4.4.1. La segmentation d’image ............................................................................................ 43
4.4.2. Représentation d’une image en niveaux de gris sur machine .................................... 44
4.5. Arbre couvrant de poids minimal ..................................................................................... 45
4.6. Arbre de Gomory-Hu ........................................................................................................ 46
4.7. Application ........................................................................................................................ 47
4.7.1. Exemple appliqué de Gomory-Hu ............................................................................... 47
4.7.2. Application de Gomory-Hu sur l’image ...................................................................... 54
4.8. Conclusion ......................................................................................................................... 55
Conclusion et perspective ......................................................................................................... 56
Bibliographie ............................................................................................................................ 57
RésuméCôte titre : MAM/0326 En ligne : https://drive.google.com/file/d/19JlvSJzp6nja9ttz28uEakrIWLNczC8Q/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0326 MAM/0326 Mémoire Bibliothéque des sciences Français Disponible
Disponible