Approche Heuristique pour Le Problème De L’ensemble Dominant à Poids Minimal Dans Les Graphes Orientés / Rihab Aissa

Public ISBD Titre : Approche Heuristique pour Le Problème De L’ensemble Dominant à Poids Minimal Dans Les Graphes Orientés Type de document : document électronique Auteurs : Rihab Aissa, Auteur ; Chaima Cherfouh, Auteur ; Samir Balbal, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2024 Importance : 1 vol (69 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : L’ensemble dominant minimal Heuristiques Sommets Graphe orienté Algorithme glouton Index. décimale : 004 Informatique Résumé : Il existe de nombreuses approches heuristiques et exactes dans la littérature pour résoudre le problème de l’ensemble dominant de poids minimum (MWDS) sur les graphes non orientés pondérés par les sommets, qui est un problème NP-difficile bien connu. Cependant, peu d’attention a été accordée à son équivalent dans les graphes orientés pondérés par les sommets, appelé problème de l’ensemble dominant de poids minimum dans les graphes orientés (MWDDS). Le problème de l’ensemble dominant orienté à poids minimal (MWDDS) cherche un ensemble dominant orienté avec la somme minimale des poids des noeuds qui le composent Il s’agit d’un problème d’optimisation combinatoire N Pdifficile qui trouve des applications dans la modélisation d’une grande variété d’interactions dirigées dans des réseaux hétérogènes complexes comme la réaction chimique, la régulation métabolique, la propagation d’une maladie infectieuse. Dans ce sujet, nous voulons explorer les méthodes heuristiques pour résoudre ce problème MWDDS des graphes. On a appliquer une technique puis la comparer aux approches trouvées dans la littérature. L’objectif est de comprendre le problème MWDDS, proposer des solutions heuristiques, et comparer leurs performances aux méthodes établies. En conclusion, les approches heuristiques offrent un bon compromis entre qualité des solutions et efficacité computationnelle pour le problème de l’ensemble dominant à poids minimal dans les graphes orientés, faisant d’elles des outils précieux pour la résolution de problèmes complexes en temps limité. Note de contenu : Sommaire 1 Théorie des graphes et les ensembles dominants 9 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Qu’est-ce qu’un graphe ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.2 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Représentation structurelle des graphes . . . . . . . . . . . . . . . . . . . 5 1.4.1 Représentation structurelle d’un graphe non orienté . . . . . . . . . 5 1.4.2 Représentation structurelle d’un graphe orienté . . . . . . . . . . . 7 1.5 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.2 Exemple illustratif d’un ensemble dominant . . . . . . . . . . . . . 9 1.6 Ensemble minimal dominant MDS . . . . . . . . . . . . . . . . . . . . . . 9 1.6.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6.2 Exemple illustratif d’un ensemble dominant minimal . . . . . . . . 10 1.7 Ensemble dominant dirigé à poids minimal(MWDDS) . . . . . . . . . . . . 10 1.7.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7.2 Exemple illustratif d’un ensemble dominant dirigé à poids minimal 11 1.7.3 Formalisation mathématique . . . . . . . . . . . . . . . . . . . . . 11 1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Optimisation combinatoire 13 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Le probléme d’optimisation combinatoire . . . . . . . . . . . . . . . . . . . 14 2.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Elément de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Les méthodes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.2 Les méthodes Approchées . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Contributions et résultats 26 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.1 Algorithme de problème MWDDS . . . . . . . . . . . . . . . . . . . 27 3.2.2 Exemple illustratif pour MWDDS . . . . . . . . . . . . . . . . . . . 32 3.3 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Résultats et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.5.1 Résultats pour Type 1 . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.5.2 Résultats pour Type 2 . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.3 Résultats pour UDG . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Côte titre : MAI/0941 Approche Heuristique pour Le Problème De L’ensemble Dominant à Poids Minimal Dans Les Graphes Orientés [document électronique] / Rihab Aissa, Auteur ; Chaima Cherfouh, Auteur ; Samir Balbal, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (69 f .) ; 29 cm. Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : L’ensemble dominant minimal Heuristiques Sommets Graphe orienté Algorithme glouton Index. décimale : 004 Informatique Résumé : Il existe de nombreuses approches heuristiques et exactes dans la littérature pour résoudre le problème de l’ensemble dominant de poids minimum (MWDS) sur les graphes non orientés pondérés par les sommets, qui est un problème NP-difficile bien connu. Cependant, peu d’attention a été accordée à son équivalent dans les graphes orientés pondérés par les sommets, appelé problème de l’ensemble dominant de poids minimum dans les graphes orientés (MWDDS). Le problème de l’ensemble dominant orienté à poids minimal (MWDDS) cherche un ensemble dominant orienté avec la somme minimale des poids des noeuds qui le composent Il s’agit d’un problème d’optimisation combinatoire N Pdifficile qui trouve des applications dans la modélisation d’une grande variété d’interactions dirigées dans des réseaux hétérogènes complexes comme la réaction chimique, la régulation métabolique, la propagation d’une maladie infectieuse. Dans ce sujet, nous voulons explorer les méthodes heuristiques pour résoudre ce problème MWDDS des graphes. On a appliquer une technique puis la comparer aux approches trouvées dans la littérature. L’objectif est de comprendre le problème MWDDS, proposer des solutions heuristiques, et comparer leurs performances aux méthodes établies. En conclusion, les approches heuristiques offrent un bon compromis entre qualité des solutions et efficacité computationnelle pour le problème de l’ensemble dominant à poids minimal dans les graphes orientés, faisant d’elles des outils précieux pour la résolution de problèmes complexes en temps limité. Note de contenu : Sommaire 1 Théorie des graphes et les ensembles dominants 9 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Qu’est-ce qu’un graphe ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.2 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Représentation structurelle des graphes . . . . . . . . . . . . . . . . . . . 5 1.4.1 Représentation structurelle d’un graphe non orienté . . . . . . . . . 5 1.4.2 Représentation structurelle d’un graphe orienté . . . . . . . . . . . 7 1.5 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.2 Exemple illustratif d’un ensemble dominant . . . . . . . . . . . . . 9 1.6 Ensemble minimal dominant MDS . . . . . . . . . . . . . . . . . . . . . . 9 1.6.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6.2 Exemple illustratif d’un ensemble dominant minimal . . . . . . . . 10 1.7 Ensemble dominant dirigé à poids minimal(MWDDS) . . . . . . . . . . . . 10 1.7.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7.2 Exemple illustratif d’un ensemble dominant dirigé à poids minimal 11 1.7.3 Formalisation mathématique . . . . . . . . . . . . . . . . . . . . . 11 1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Optimisation combinatoire 13 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Le probléme d’optimisation combinatoire . . . . . . . . . . . . . . . . . . . 14 2.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Elément de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Les méthodes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.2 Les méthodes Approchées . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Contributions et résultats 26 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.1 Algorithme de problème MWDDS . . . . . . . . . . . . . . . . . . . 27 3.2.2 Exemple illustratif pour MWDDS . . . . . . . . . . . . . . . . . . . 32 3.3 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Résultats et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.5.1 Résultats pour Type 1 . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.5.2 Résultats pour Type 2 . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.3 Résultats pour UDG . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Côte titre : MAI/0941

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
MAI/0941	MAI/0941	Mémoire	Bibliothéque des sciences	Français	Disponible Disponible

---

1 (1 - 1 / 1)