Algorithme de détermination d’un ensemble indépendant maximal dans un graphe

Algorithme de détermination d’un ensemble indépendant maximal dans un graphe

La théorie des graphes est née en 1736 quand Euler démontra qu’il était impossible de traverser chacun des sept ponts de la ville de Königsberg une fois exactement et de revenir au point de départ . Le terme lui même vient du mot grec γρα∈iν qui veut dire écrire , dessiner . Il a été employé semble t-il la première fois , en langue Française par Sainte – Lague en 1926 . Pendant longtemps , les travaux sur les graphes ne déborderont guère le cadre des récréations mathématiques . Des recherches d’Euler au XVIIIème siècle , elle est devenue une branche des Mathématiques au début du XXème siècle , grâce aux travaux de König , de Kuratowski de Cayley et , plus récemment de Berge , d’Erdös et de Harary . Les recherches récentes en informatique et surtout en algorithmique lui donne un nouveau souffle . La théorie des graphes constitue un domaine des mathématiques qui , historiquement , s’est développée au sein de disciplines diverses telle que la chimie (modélisation de structures) , la biologie (génome) , les sciences sociales (modélisation des relations) ou en vue d’applications industrielles (problème du voyageur de commerce) . Elle est devenue l’un des instruments les plus efficaces pour représenter (modéliser) ; puis résoudre de nombreux problèmes discrets que pose la recherche opérationnelle. La théorie des graphes sert avant tout à représenter et à organiser les taches de façon optimale : après avoir traduit un problème sous forme de graphe , on cherche des méthodes systématiques qui permettent de trouver la succession la plus rapide ou la moins coûteuse pour effectuer toutes les tâches. Un graphe permet de représenter simplement la structure , les connexions , les cheminements possibles d’un ensemble complexe comprenant un grand nombre de situations , en exprimant les relations , les dépendances entre ses éléments (réseau de communication , réseaux ferroviaire ou routier , arbre généalogique , diagramme de succession de tâches en gestion de projet etc… ) . Elle permet de résoudre efficacement une grande variété de problèmes pratiques ou récréatifs en les ramenant à des configurations qui se dessinent simplement à l’aide de points et de liaisons entre ces points. Les problèmes classiques de la théorie des graphes sont : flots et connectivité , (« fiabilité d’un réseau ») ,couplage ( affectation ) , parcours eulérien ( qui traverse chaque arête : problème du « postier chinois » ) , parcours hamiltonien (qui traverse chaque sommet : « problème du voyageur de commerce » ) , coloration , ensemble stable , absorbant . Certains de ces problèmes ( flots maximum , couplage maximum parcours eulérien ) peuvent être résolus « efficacement » , mais la plupart sont NP-complets . En effet , de l’un de ces problèmes classiques , à savoir « ensemble stable » ressort le sujet de notre mémoire qui s’intitule comme suit : Algorithme de détermination d’un ensemble indépendant maximal . Ce thème est d’autant plus actuel à cause de ses nombreuses applications . Si l’on s’intéresse par exemple au domaine des Télécommunications, nous avons des solutions efficaces dans les problèmes de partage de ressources, l’affectation de ressources, le multiplexage des longueurs d’ondes (WDM) utilisé dans la technologie de la fibre optique, l’allocation des fréquences qui est un problème récurrent dans ce domaine etc.… La solution à la plus part de ces problèmes passent par le biais de la détermination d’un ensemble indépendant maximal dans un graphe bien déterminé . Il existe d’autres applications dans plusieurs domaines, comme l’ordonnancement des travaux , la gestion des emplois de temps etc.….

L’algorithme de détermination d’un ensemble indépendant maximal ne sera développé qu’au chapitre IV . Nous avons présenté un programme en langage C permettant , une fois qu’on dispose d’un graphe , après saisie sur une console de sa matrice d’adjacence , d’obtenir entre autres résultats , un ensemble indépendant maximal , puis de pouvoir vérifier si un sous- ensemble en notre possession est oui ou non indépendant maximal . Supposant que tous les lecteurs ne sont pas forcément outillés en programmation , nous avons préféré placer le code source du programme en annexe . Cependant , le langage C étant portable il est aisé de faire soi-même les tests et de faire tourner l’algorithme .

Eléments de Théorie des Graphes

Le sommets s est appelé le début de l’arc ε tandis que t est la fin . s et t sont des sommets extrémités de ε s et t sont adjacents s’il existe un arc ε tel que g(ε) = ( s , t ) . Deux arcs qui ont même début et même fin sont des arcs parallèles . Dans ce cas , on dit que G est un multigraphe . Un arc tel que le début et la fin coïncide est appelé boucle . On dit que G est un pseudographe. Un graphe qui n’a ni arc parallèle , ni boucle est un graphe simple . Remarque 2 En fait les graphes orientés dépourvus d’arcs parallèles correspondent aux relations binaires sur un ensemble fini et les relations binaires sur un ensemble fini correspondent aux graphes orientés dépourvus d’arcs parallèles . La possibilité d’avoir des arcs parallèles est donc une généralisation de la notion de relation binaire , qui autorise des objets à être liés de plusieurs façons en même temps . Théorème G = (S , A , g) est un multigraphe si et seulement si g n’est pas injective . Preuve Si G est un multigraphe , alors il admet au moins deux arcs parallèles . Par définition d’arc parallèle ; ∃ µ ∈ A ; ν ∈ A ; µ ≠ ν et ∃ i ; j des éléments de S tel que : g(µ) = (i , j) et g(ν) = (i , j) c’est à dire g(µ) = g(ν) . Ce qui entraîne que g n’est pas injective. Supposons que g n’est pas injective : Alors il existe au moins deux arcs u et v distincts tel que g(u) = g(v) . Ceci entraîne que les arcs u et v sont parallèles et ainsi G est un multigraphe . Exemple 3 Considérer le graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation.