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

Sous-ensembles d’un graphe et coloration

Dans la première partie ce chapitre, nous allons faire le point sur quelques sous-ensembles, dont les cliques , qui correspondent aux sous-ensembles indépendants quand on passe au complémentaire du graphe. L’autre grande partie aborde la coloration qui oblige deux sommets ou arcs adjacents à être identifiés différemment . Cette identification qui se fait souvent avec un ensemble de couleurs usuelles (d’où le nom de coloration donné à cette notion), pourra aussi se faire à l’aide d’entiers . Dans la suite du mémoire , sauf indication contraire , nous noterons G = ( S ; A ) les graphes , qui sont supposés finis avec S et A de cardinaux respectifs n et m. Pour d’avantage de simplification , à la place de G = ( S ; A ) , on écrira simplement G .

Sous-ensemble indépendant

Considérons un graphe G . Un sous-ensemble I de S est dit indépendant ou stable si et seulement si : ∀ i ∈ I ; ∀ j ∈ I , alors ( i , j ) ∉ A . Donc un sous-ensemble de S est indépendant si ses éléments ne sont pas mutuellement adjacents . On peut aussi le définir comme suit : Un ensemble indépendant d’un graphe G est un sous-ensemble S’ ⊆ S de sommets tel que chaque arête de A est incidente à au plus un sommet de S’ . Exemple 1 Considérons le graphe ci-dessous : Les sous-ensembles { 1 , 5 , 6 , 9 } et { 1 , 3 , 8 , 10 } sont indépendants . Le sous-ensemble { 1 , 5 , 9 , 10 } n’est pas indépendant car { 5 , 10 } est une arête de G II-2 Sous-ensemble dépendant Définition Soit le graphe G et C un sous- ensemble de S . On dit que C est un sous-ensemble dépendant si C est une clique de G c’est à dire un sous-ensemble complet de G . 17 Soit C l’ensemble des cliques de G . On appelle degré de dépendance de G , le nombre θ ( G ) = max { card ( C ) } C ∈ C C’est le nombre maximal de sommets constituant une clique de G . Exemple 2 Les sous-ensembles { 0 , 3 , 4 , 5 , 7 } et { 1 , 2 , 6 } sont des cliques du graphe ci-dessous . Cependant l’ensemble { 1 , 2 , 6 , 7 } n’est pas une clique car { 6 , 7 } n’est pas une arête . Remarque 1 Un sous-ensemble sommets I est un stable si et seulement si I est une clique du graphe complémentaire G’ de G . II-3 Sous-ensemble recouvrant Soit le graphe G et R ⊂ S un sous-ensemble de S . On dit que R est recouvrant si : ∀ ( u , v ) ∈ A alors u ∈ R ou v ∈ R . On appelle degré de recouvrement de G , le nombre δ ( G ) = min ( R) ; R∈R où R est l’ensemble des sous-ensembles recouvrant de G . Donc un sous-ensemble de G est recouvrant si et seulement si tout arc de G lui est incident .Exemple 3 L’ensemble { a , c , e } du graphe ci-dessous est recouvrant b • c a • • e • d Remarque 2 Ces sous-ensembles interviennent très souvent directement ou indirectement dans beaucoup d’applications faisant intervenir la coloration de graphe. Cette dernière est l’objet de la prochaine section . II-4 Coloration Définition On appellera coloration du graphe G , toute coloration des sommets telle que deux sommets adjacents ne soient pas de même couleur . Formellement , une coloration des sommets d’un graphe non orienté G sans boucle est une application θ : S C avec C un ensemble de couleurs . Une coloration , est donc une partition de G en stables . On essaie le plus souvent de déterminer le nombre minimal de couleurs nécessaires .

Application 1

L’allocation des fréquences est un problème récurrent en télécommunication . Il consiste à allouer des fréquences à des transmetteurs de manière à éviter les interférences et en utilisant le moins de fréquences possibles . Une première modélisation de ce problème en terme de coloration d’un graphe est la suivante : Les sommets du graphe représentent les transmetteurs , deux sommets sont reliés par une arête si les transmetteurs correspondant peuvent interférer et les couleurs représentent les fréquences . Affecter les longueurs d’onde revient à trouver une bonne coloration du graphe . A) Nombre chromatique d’un graphe Définition On appelle nombre chromatique d’un graphe G , le nombre minimal de couleurs servant à le colorier . On le notera γ ( G ) . Partition des sommets d’un graphe Soit le graphe G . Considérons un sommet X1 et construisons un ensemble S1 tel que : 19 • X1 ∈ S1 • S1 est stable • S1 est de cardinal maximum Considérons maintenant un sommet X2 ∉ S1 et construisons un ensemble S2 tel que : • X2 ∈ S2 • X2 est stable • S1 et S2 sont disjoints • S2 est de cardinal maximum Considérons maintenant un sommet X3 ∉ S1 ∪ S2 et construisons un ensemble S3 tel que : • X3 ∈ S3 • X3 est stable • S1 S2 et S3 sont disjoints • S3 est de cardinal maximum En continuant ainsi j’usqu’à épuisement de l’ensemble S , on obtient une partition de S : { S1 , S2 , ….., Sq }. Si on choisit une couleur par sous-ensemble Si , on obtient ainsi une q-coloration du graphe et on aura nécessairement γ ( G ) ≤ q . Application 2 Soit une carte géographique représentant plusieurs pays . On souhaite colorier chaque pays de manière à ce qu’il n’ait pas la même couleur que chacun de ses voisins . Ce problème peut être résolu en cherchant une partition en stables du graphe obtenu en associant chaque pays à un sommet et chaque arc à une frontière commune entre deux pays . Il suffit alors d’associer une couleur à chaque stable obtenu . Une majoration de γ ( G ) Considérons maintenant un sommet x ∈ Sq . Ce sommet est lié à au moins un sommet appartenant à S1 (sinon , on pourrait le mettre dans S1 , ce qui contredirait la maximalité de S1) De même , il est lié à au moins un sommet de S2 (sinon , il serait dans S2 ) . On en déduit donc en raisonnant de la même manière sur S3 , ….., Sq-1 que deg ( x ) ≥ q-1 . Si on appelle r le degré maximum des sommets du graphe , on a alors : r ≥ deg ( x ) ≥ q-1 ≥ γ ( G ) – 1 et donc γ ( G ) ≤ r + 1 Une minoration de γ ( G ) En notant θ ( G ) le cardinal de la plus grande clique de G , on a : γ ( G ) ≥ θ ( G ) 20 Exemple 4 2 • • 5 3 • 1 • • 7 • • 4 6 Le graphe contient un sous-graphe complet d’ordre 4 (1-2-3-4) , donc γ ( G ) ≥ 4. Le degré maximum des sommets est 6 , donc γ ( G ) ≤ 6+1 = 7 Ainsi , on a : 4 ≤ γ ( G ) ≤ 7 . Exemple 5 Problème d’emploi du temps Une université doit organiser les horaires des examens . On suppose qu’il y a 7 épreuves à planifier correspondant aux cours numérotés de 1 à 7 et que les pairs de cours suivants ont des étudiants en commun : 1 et 2 ; 1 et 3 ; 1 et 4 ; 1 et 7 ; 2 et 3 ; 2 et 4 ; 2 et 5 ; 2 et 7 ; 3 et 4 ; 3 et 6 ; 3 et 7 ; 4 et 5 ; 4 et 6 ; 5 et 6 ; 5 et 7 ; 6 et 7 . Comment organiser ces épreuves de façon qu’aucun étudiant n’ait à passer deux épreuves en même temps et cela sur une durée minimale ? Pour cela , construisons le graphe G dont les sommets sont les épreuves numérotés de 1 à 7 , une arête relie deux sommets lorsque les deux cours correspondant possédant des étudiants en commun . 1 • 7 • • 2 6 • • 3 • • 21 5 4 Planifier les examens en un temps minimal consiste une k-coloration de G , avec k = γ ( G ) . G possède un sous-graphe complet d’ordre 4 ( de sommets 1 , 2 , 3 , 4 ) , donc γ ( G ) ≥ 4 . Déterminons une partition des sommets de G en sous-ensembles stables : S1 = { 1 , 6 } S2 = { 2 } S3 = { 3 , 5 } S4 = { 4 , 7 } D’où γ ( G ) ≤ 4 et finalement γ ( G ) = 4 . Les examens peuvent être répartis en 4 périodes de la manière suivante : 1ère Période : épreuves des cours 1 et 6 2ème Période : épreuve du cours 2 3ème Période : épreuves des cours 3 et 5 4ème Période : épreuves des cours 4 et 7.