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