L'ensemble du Feedback minimum Combinatoire et Sécurisation
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ummto
Abstract
Nous traitons dans ce document le problème du feedback minimum dans les graphes d'intervalles non valués non orientés. Le feedback est un ensemble de sommets qu'à leurs suppression le graphe devient acyclique, cet ensemble est dit minimum si a cardinalité est minimum parmi tous les autres ensembles, cet ensemble est noté Fmin.
Dans le but de calculer Fmin, nous avons procédé la méthode (algorithme) proposé par Pal et Saha, ensuite on a travaillé sur la sécurisation de cet ensemble. La sécurisation consiste à trouver pour chaque sommet un autre sommet qui assure la même tâche que lui.
Si Fmin n'est pas sécurisé, on a opté pour une autre méthode qui est l'ajout des sommets et dans ce cas l'ensemble ne sera plus minimum. La sécurisation prend l'ampleur sur la notion du minimum.
On adonné plusieurs exemples qui facilitent la compréhension de ce problème, suivi d'un exemple réel qui est l'assurance d'un éclairage permanent et uniforme dans un supermarché.
A la fin de ce document on a programmé l'algorithme MARK,qui est un vecteur booléen qui calcule le Fminà l'aide du langage python qui est un langage très performant et contemporain
Description
43f.;30cm
Keywords
Graphe d'intervalles, Graphe acyclique, Algorithme MARK, Python
Citation
Rechercfhe opérationnelle