Depot Institutionnel de l'UMBB >
Mémoires de Master 2 >
Faculté des Sciences >
Recherche opérationnelle >
R. O. >
Veuillez utiliser cette adresse pour citer ce document :
http://dlibrary.univ-boumerdes.dz:8080/handle/123456789/8417
|
Titre: | Ensembles sécurisés et les alliances défensives dans les graphes |
Auteur(s): | Belhadi, Mouna Boukhari, Amina |
Mots-clés: | Théorie des graphes Ensembles sécurisés Alliances défensives |
Date de publication: | 2020 |
Editeur: | M'hamed Bougara faculté des sciences |
Résumé: | Ce mémoire s’inscrit dans le cadre de la théorie des graphes, nous nous sommes intéressés
à l’étude des alliances défensives et les ensembles sécurisés dans les graphes. Nous avons relaté
l’historique de l’étude des ces ensembles particuliers ainsi que les paramètres qui y sont liés.
Nous avons passé en revue les principaux résultats établis à ce jour.
Nous nous sommes focalisés principalement à l’aspect algorithmique où nous avons repris
les démonstrations relatives à la NP-complétude et la Co-NP-complétudes des problèmes de dé-
cisions liés à l’existence d’une alliance défensive globale de taille au plus k et celui de l’existence
d’un ensemble sécurisé de taille au plus k dans un graphe.
Notre travail particulier repose sur l’algorithme a paramètre xe réalisé par K. Amano et
al en 2015 [1] qui trouve un ensemble sécurisé minimal en un temps O(23kk2n) meilleur que
celui de Dutton [14] O(2klog2kn) réalisé en 2008.
Nous avons donc implémenté cet algorithme dans le langage Matlab qui nous a permis
d’exhiber des ensembles sécurisés minimaux dans un graphe. Cette étude revêt une importance
capitale vu le grand intérêt des ensembles sécurisés et des alliances en générale dans les graphes.
Nous souhaitons que notre modeste étude servira comme référence pour les générations à venir. |
Description: | 82 p. : ill. ; 30 cm. |
URI/URL: | http://dlibrary.univ-boumerdes.dz:8080/handle/123456789/8417 |
Collection(s) : | R. O.
|
Fichier(s) constituant ce document :
|
Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.
|