Thèse de Nour Dyab


Sujet :
Un nouveau modèle de protection de graphes : problème de l'ensemble de rebouclement eternel

Date de soutenance : 24/10/2023

Encadrant : Hamamache Kheddouci

Résumé :

Cette thèse vise à développer un modèle de protection de graphes à l'aide de gardes mobiles, en se basant spécifiquement sur le concept d'ensemble de feedback éternel. Le problème de protection d'un graphe à l'aide de gardes mobiles a été largement étudié dans la littérature. Ce problème consiste à défendre les sommets ainsi que les arêtes d'un graphe donné G contre toute attaque à l'aide d'unités de défense, appelées gardes, positionnés sur certains sommets de G. Notre intérêt principal réside dans la protection des graphes contre des séquences infinies d'attaques, exécutée une par une. Le problème de protection peut être modélisé par un jeu à deux joueurs; un défenseur et un attaquant. Dans ce jeu, le défenseur choisit la configuration initiale des gardes au premier tour et doit défendre tous les sommets de G contre toute attaque en reconfigurant les gardes à chacun des tours suivants. D'autre part, l'attaquant choisit le sommet à attaquer à chaque tour. Une attaque est considérée comme défendue si un garde peut être déplacé vers le sommet attaqué via une arête. Le défenseur remporte le jeu s'il parvient à défendre avec succès le graphe contre chaque séquence d'attaques, tandis que l'attaquant gagne s'il parvient à casser cette défense. Il est important de noter que la séquence d'attaques peut avoir une longueur infinie. Des variantes de ce problème, telles que l'ensemble dominant éternel, l'ensemble indépendant éternel et la couverture éternelle, ont été largement explorées dans la littérature.  L'organisation de cette thèse est la suivante : Le chapitre 1 est une introduction à la théorie des graphes, qui présente des notions classiques sur les graphes, des problèmes et paramètres de graphes les plus importants ; des classes de graphes que nous étudierons par la suite ; ainsi que des domaines d’applications de la théorie des graphes. Dans le chapitre 2, nous présentons les modèles de protection de graphes par des gardes. Le modèle où l’ensemble des gardes forme à tout moment un ensemble dominant (premier modèle de protection de graphe à avoir été étudié) est détaillé, dans sa version classique ainsi que sa version multiple qui permet au défenseur de déplacer un nombre quelconque de gardes, à chaque tour, pour assurer la défense et/ou la dominance. Les principaux résultats de la littérature sur ces deux paramètres sont présentés. Les modèles où l’ensemble des sommets avec gardes doit être un ensemble indépendant ou une couverture par sommets sont également présentés succinctement. Le chapitre 3 présente une première contribution avec l’introduction du nouveau modèle de protection pour lequel l’ensemble des gardes doit, à tout instant, être un ensemble de sommets dominant et de feedback. Les liens entre les deux paramètres F∞ et Fm∞, qui représentent le nombre minimum de gardes permettant de protéger le graphe éternellement dans la version classique et la version multiple, respectivement, aux autres paramètres de protection sont établis, puis des bornes sont données pour les trois classes de graphes : à savoir les graphes distances, les graphes circulants et les grilles carrées.  Dans le chapitre 4, nous calculons la valeur de F∞ fonction des tailles des cliques dans la décomposition du graphe en cliques, ensuite nous présentons un algorithme linéaire qui construit l’ensemble éternelle avec un tel nombre de gardes. Ceci en se basant sur l’observation que dans un graphe complet de n sommets, n − 2 gardes sont nécessaires pour couper tous les cycles. Le chapitre 5 est consacré au calcul du F∞ pour les k-arbres. Une solution a été proposée en utilisant leur structure en cliques. Ce résultat est complété par une série de résultats exacts ou quasi-exacts sur différentes classes de graphes avec une structure particulière obtenue à partir d’un noyau formé d’un graphe complet, d’un cycle ou d’un chemin, par ajout de sommets reliés à certains sommets du noyau et éventuellement à certains sommets hors noyau. En particulier, la valeur exacte de F∞ est calculée pour les graphes k-spiral, et la preuve a donné lieu à un algorithme linéaire pour trouver l’ensemble de sommets correspondant. Le chapitre 6 récapitule les contributions de la thèse et proposes des perspectives de recherche en continuité aux travaux de cette thèse. 

 


Jury :
Pr. Olivier TogniProfesseur(e)Université de BourgogneRapporteur(e)
Pr. Abdallah MakhoulProfesseur(e)Université de Franche-ComtéRapporteur(e)
Pr. Salima BenbernouProfesseur(e)Université Paris CitéExaminateur​(trice)
Dr. Maidoun MortadaMaître de conférenceUniversité libanaiseExaminateur​(trice)
Dr. Nora FaciMaître de conférenceUniversité Lyon 1Examinateur​(trice)
Dr. Mohamed LalouMaître de conférenceUniversité de BourgogneExaminateur​(trice)
Pr. Hamamache KheddouciProfesseur(e)Université Lyon 1Directeur(trice) de thèse