Allocation de Fréquences par Coloration de Graphes

Algorithme glouton On consid ere l’algorithme suivant : Input Un graphe G et des couleurs 1,2,3,4 Les sommets de G sont num erot es de 1 a n (s 1,s 2, ,s n) Output Une coloration valide du graphe G Mais le nombre de couleurs utilis ees est-il minimal? Traitement Pour i allant de 1 a n, a ecter au sommet s i la plus

Coloration de graphes - unifrch

Coloration de graphes Paul Melotti L’algorithme glouton consiste à trouver un coloriage du graphe de la façon suivante : on numérotelessommetsv 1,

Arbre Couvrants de Poids Minimum Coloration de graphes

Coloration de graphe : algorithme glouton Algorithme glouton : avance étape par étape, choisit une solution optimale localement, sans souci d’optimalité globale Principe : on parcourt le graphe (en profondeur, largeur ou autre), et à chaque nœud on assigne la première couleur possible (en fonctions des voisins déjà colorés)

Coloration de graphes: algorithmes et structures

coloration a un facteur n1 avec un algorithme polynomial N Bousquet Coloration de graphes: algorithmes et structures Introduction Structure de graphes et coloration

Travaux pratiques Coloration d’un graphe

a) Montrer que pour un graphe d’intervalles, l’algorithme glouton fournit une coloration minimale lorsque les sommets sont ordonnés par valeurs de a i croissantes b) Montrer que pour un graphe Gquelconque il existe toujours un ordonnancement des sommets pour lequel l’algorithme glouton fournit un résultat optimal Algorithme DSATUR

Allocation de Fréquences par Coloration de Graphes

2 1 Coloration séquentielle : l’algorithme glouton Une première approche pour colorer le graphe est de prendre ses sommets les uns après les autres aﬁn de leur aﬀecter une couleur, tout en veillant à ce que deux sommets adjacents n’aient jamais la même couleur : c’est l’algorithme de coloration séquentielle Nous obtenons

UNIVERSITÉ DE MONTRÉAL UN ALGORITHME CONSTRUCTIF EFFICACE

Le problème de coloration de graphe est connu comme étant NP-difficile [5], c’est-à-dire qu’il n’existe pas à ce jour un algorithme polynomial qui donne la coloration optimale pour tout graphe Dès lors, la coloration de graphe a fait l’objet de nombreuses études résultant en une

1 VOCABULAIRE DE BASE a Graphe - Beziers Accueil

L’algorithme glouton ne donne pas nécessairement le nombre chromatique Par exemple, en colorant le graphe ci-dessous par l’algorithme glouton, on obtient une coloration avec 3 couleurs, alors que le nombre chromatique est 2 C e Encadrement du nombre chromatique Propriété :

Coloration dun graphe - Meilleur en Maths

Coloration d'un graphe 1 Activité Pour une coupe du monde de football, les équipes qualifiées sont réparties en « poule » de quatre équipes Chaque équipe rencontre une et une seule fois les trois autres Toutes les équipes de la même poule, jouent le même jour un match et un seul

[PDF] algorithme de coloration de welsh et powell

[PDF] algorithme de coloration de graphe en java

[PDF] coloration des graphes pdf

[PDF] coloration graphe terminale es

[PDF] algorithme de coloration de graphe en c

[PDF] algorithme de coloration de graphe en python

[PDF] coloriage magique avec les puissances correction

[PDF] coloriage numérique isabelle guillot

[PDF] écrire une fraction sous la forme d'un entier et d'une fraction cm2

[PDF] les fractions supérieures ? 1

[PDF] fractions inférieures supérieures ou égales ? 1

[PDF] cours cap coiffure la permanente

[PDF] cours coloration cap coiffure

[PDF] règles des couleurs en coiffure

[PDF] reglement boxe anglaise

Allocation de Fréquences par Coloration

de Graphes

Table des matières

1 Généralités2

1.1 Le problème d"allocation de fréquences . . . . . . . . . . . . . .. . . . . . . . . . . 2

1.2 Graphes, définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 3

1.3 Le problème de coloration . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 3

2 Graphes quelconques : des algorithmes d"approximation 4

2.1 Coloration séquentielle : l"algorithme glouton . . . . . .. . . . . . . . . . . . . . . 4

2.2 Deux heuristiques différentes . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 5

2.2.1 Welsh & Powell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2.2.2 DSATUR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Graphes triangulés : un algorithme linéaire de colorationoptimale 6

3.1 Généralités sur les graphes triangulés . . . . . . . . . . . . . .. . . . . . . . . . . . 6

3.2 Parcours en largeur lexicographique - LexBFS . . . . . . . . .. . . . . . . . . . . . 6

3.3 Affinage de partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 7

4 Résultats expérimentaux8

4.1 Sur des graphes pseudo-aléatoires . . . . . . . . . . . . . . . . . .. . . . . . . . . . 8

4.2 Sur des graphes de DIMACS . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 10

Conclusion et perspectives12

Références12

1 Généralités1.1 Le problème d"allocation de fréquences

Imaginons que l"on veuille construire un réseau d"antennesradios. Il faudra réserver certaines

fréquences de communication, que l"on attribuera à nos antennes afin qu"elles puissent communi-

quer entre elles. Il faut aussi minimiser le nombre de fréquences à réserver, car chaque réservation

a un coût. Une première modélisation du problème, en radio AMpar exemple, montre que si deux

antennes "assez proches" géographiquement émettent dans des fréquences trop voisines l"une de

l"autre, leur spectres en fréquences se recouvrent et il devient impossible d"extraire l"information

nécessaire du signal reçu. On dit alors que les antennes interfèrent.

On modélise ainsi le réseau d"antenne par un graphe, appelégraphe d"interférences, dont les

sommets sont les antennes, et les arêtes relient deux antennes qui interfèrent entre elles. Les fré-

quences à allouer correspondent à des couleurs (représentées par des entiers) avec lesquelles nous

colorons les sommets du graphe. La coloration doit être une coloration propre : deux sommets adjacents ne peuvent recevoir la même couleur. Le graphe sera de plus non-orienté, la relation "interfère" étant supposé symétrique.

Figure1 - Un réseau d"antennes

1.2 Graphes, définitions

Supposons maintenant le graphe d"interférence du réseau connu. Rappelons quelques définitions

et notations utilisées par la suite : •Ungrapheest un coupleG= (V,E) oùVest un ensemble fini, ses éléments sont lessommets du graphe, etE?V2, ses éléments sont lesarcsdu graphe. Ici les graphes sontsimples(?a?V,(a,a)/?E) etnon-orientés(?a,b?V,(a,b)?E?? (b,a)?E. Les arcs sont alors appelés desarêtes. L"ordre(resp. lataille) d"un graphe est le nombre de ses sommets (resp. arêtes). Par la suite nous prendronsV=?0,n-1?, oùn=|V|, et on noteram=|E|. •Deux sommetsaetbsont ditadjacentsouvoisinssi (a,b)?Eou (b,a)?E. Soita?V, on note alorsN(a) ={b?V,(a,b)?E ou(b,a)?E}l"ensemble des voisins àa, ouvoisinage dea. On noted(a) =|N(a)|le nombre de voisins dea, oudegrédea. •H= (V?,E?) est unsous-graphedeGsiV??VetE??E. SoitS?V, on noteG[S] le graphe (S,E∩(S×S)), appelésous-graphedeGinduit, ouengendré, parS. •Unechaînedelongueurkest une suite finie de sommets deux à deux adjacentsv0v1...vk, i.e. telle que?i??1,k?,(vi-1,vi)?E. Uncyclede longueurkest une chaînev0v1...vktelle quev0=vk. Dans une chaînev0v1...vk, unecordeest une arête (vi,vj)?E, avecj?=i±1.

Enfin, untrouest un cycle sans corde.

1.3 Le problème de coloration

SoitG= (V,E) un graphe simple non-orienté. Une applicationσ:V→Nest appelée une coloration propredeGsi?(a,b)?E,σ(a)?=σ(b), i.e. deux sommets adjacents n"ont jamais la même couleur. Soitk=|σ?V?|, on dit alors queσest unek-coloration propredeG, et queGestk- colorable. Le plus petit entierkpour lequelGestk-colorable est appelénombre chromatiquedeG,

notéχ(G). Nous recherchons ainsi une coloration optimale deG, c"est-à-dire uneχ(G)-coloration

propre deG.

Allouer des fréquences au réseau d"antennes revient alors àcolorer proprement son graphe d"in-

terférences. Notons qu"en raison de contraintes géographiques, technologiques, ou autres (présence

de montagnes, etc.), nous ne pouvons pas faire d"hypothèsesa priorisur la structure du graphe d"interférences. Nous donnerons donc un exemple de méthode employée pour colorer un graphe d"une manière

plus générale. Trouver une coloration optimale d"un graphequelconque étant un problème NP-

Complet, nous exposerons tout d"abord des algorithmes de coloration non-optimale dans le cas général, ainsi qu"un algorithme optimal dans un cas particulier. 1 03 4 2 5 6

Figure2 - Un graphe d"interférence coloré

2 Graphes quelconques : des algorithmes d"approximation2.1 Coloration séquentielle : l"algorithme glouton

Une première approche pour colorer le graphe est de prendre ses sommets les uns après les

autres afin de leur affecter une couleur, tout en veillant à ce que deux sommets adjacents n"aient

jamais la même couleur : c"est l"algorithme de coloration séquentielle. Nous obtenons ainsi une

coloration propre du graphe, pas forcément optimale, et quidépend fortement de l"ordre de visite

des sommets.

Programme 1Coloration séquentielle

Entrée :Un graphe quelconqueG= (V,E), une permutation des sommetsσ:?0;n-1?→V

Sortie :Une coloration proprec:V→N

1:n :=|V|;

2:Couleur := Tableau(Taille : n) (Défaut :-1);

3:Pouri = 0 à n-1faire

4:x :=σ(i);

5: # Recherche de la plus petite couleur non utilisée dansN(x) #

6:Libre := Tableau(Taille :???) (Défaut :vrai);

7:Poury? N(x)faire

8:SiCouleur.(y)?= -1alors

9:Libre.(Couleur.(y))←faux

10:Fin Si

11:Fin Pour

12:index := 0;

13:Tant QueLibre.(index) =fauxfaire

14:index := index + 1

15:Fin Tant Que

16: # Affecter la couleur donnée parindexàx#

17:Couleur.(x)←index

18:Fin Pour

19:RenvoyerCouleur

La complexité temporelle de l"algorithme estO(n+m). 0 1 2

Figure3 - Coloration séquentielle d"un graphe

2.2 Deux heuristiques différentes2.2.1 Welsh & Powell

Il s"agit maintenant d"utiliser l"algorithme de coloration séquentiel avec un ordre judicieux, en vue d"obtenir une coloration propre la plus "acceptable"possible. L"algorithme de Welsh & Powell consiste ainsi à colorer séquentiellement le grapheen visitant les sommets par ordre de

degré décroissant. L"idée est que les sommets ayant beaucoup de voisins seront plus difficiles à

colorer, et donc il faut les colorer en premier. La complexité de l"algorithme devientO(nlnn+m) en utilisant un tri par comparaison, mais resteO(n+m) avec un tri par dénombrement. Cependant on peut parfois aboutir aux pires colorations possibles (n

2au lieu de 2). L"heuristique

DSATUR propose une amélioration du principe de l"algorithme de Welsh & Powell afin d"éviter ce problème.

2.2.2 DSATUR

Ici, l"idée est que les sommets difficiles à colorer sont ceux qui ont le plus de voisins de couleurs

différentes, puis ceux qui ont le plus de voisins tout court. Concrètement, on définit ledegré de

saturationd"un sommeta, notéDSAT(a) comme suit : •Sian"a aucun voisin colorié alorsDSAT(a) = degré dea. •Sinon,DSAT(a) = nombre de couleurs différentes utilisées pour colorer lesvoisins dea. Ou encore, siσdésigne la fonction de coloration partielle,DSAT(a) =?d(a)si σ?N(a)?=∅ |σ?N(a)?|sinon

Après initialisation deDSAT(a) àd(a) pour touta, on répète alors les opérations suivantes :

1. Prendre un sommet non coloréxdeDSATmaximum.

2. Colorerxavec la plus petite couleur disponible.

3. Mettre à jourDSAT(y) poury? N(x).

La complexité temporelle de l"algorithme dépend de l"implémentation effectuée. Elle peut être

O?n2?ouO?n2+nm?selon la structure utilisée.

DSAT= 1

DSAT= 1←2DSAT= 1←2

1 03 4 52
6

Sommet visit´es : 1,6,2

Figure4 - Une étape de l"algorithme DSATUR

3 Graphes triangulés : un algorithme linéaire de coloration

optimale

3.1 Généralités sur les graphes triangulés

Nous allons maintenant donner un algorithme optimal qui permet de colorer une classe de

graphe bien particulière : les graphes triangulés. Nous présentons ici les définitions et propriétés

utiles à cet algorithme. •Un grapheG= (V,E) est dittriangulés"il ne contient pas de trou de longueur≥4. •Un sommetadeGestsimplicialsi tous ses voisins sont adjacents 2 à 2. •Unschéma(ouordre)d"élimination simplicialest une permutationσ:?0,n-1?→Vtelle que pour toutidans?0,n-1?,σ(i) soit simplicial dansG[σ??0,i??]. On peut alors démontrer la caractérisation suivante, sur laquelle repose l"algorithme LexBFS :

Propriété 1.Gest triangulé si et seulement si il admet un schéma d"élimination simplicial.

L"utilité d"une telle caractérisation est manifeste, car on peut montrer qu"une coloration sé-

quentielle selon un tel ordre offre une coloration optimale.Le problème consiste donc à trouver

efficacement un tel schéma dans le cas des graphes triangulés,c"est le but de l"algorithme LexBFS.

Graphe Triangul´e

Sommet simplicial :

Tous ses voisins sont adjacents 2 `a 2

Sch´ema d"´elimination simplicial :

x1,x2,...,xn xi x 2 x 1x pxi x 2 x 1x p (p≥4) xx1x 2x ix n

Figure5 - Illustrations

3.2 Parcours en largeur lexicographique - LexBFS

Il se présente comme une variante du parcours en largeur classique de graphe (dit BFS pour "Breadth First Search"). Considérons l"alphabetA=?1,n?, et munissons l"ensemble des mots surAde l"ordre lexicographique?, défini intuitivement comme étant l"ordre du dictionnaire.On

associe alors à chaque sommetxune étiquetteL(x)?A?, initialement égale àε, oùεdésigne le

mot vide deA?.

On effectue ensuite les opérations suivantes :

Pourivariant de0àn-1 :

1. Prendre un sommetxd"étiquette maximale pour?parmi les sommets non visités.

2. Affecter le numéroiàx.

3. Effectuer la mise à jourL(y)←L(y)·(n-i) poury? N(x)

Programme 2Parcours en Largeur Lexicographique

Entrée :Un graphe quelconqueG= (V,E), un sommet sources?V

Sortie :Une bijectionσ:V→?0,n-1?

1:n :=|V|;

2:Numero := Tableau(Taille : n) (Defaut : -1);

3:Label := Tableau(Taille : n) (Defaut : "");

4:Pouri = 0 à n-1faire

5:Soit x tel que Label.(x) = max{Label.(y), Numero.(y) = -1};

6:Numero.(x)←i;

7:Poury? N(x)faire

8:SiNumero.(y) = -1alors

9:Label.(y)←Label.(y) ˆ String_of_Int (n-i)

10:Fin Si

11:Fin Pour

12:Fin Pour

13:RenvoyerNumero

Nous obtenons alors un ordreσ:V→?0,n-1?sur les sommets du graphe, appelé "ordre lexicographique", qui vérifie la propriété suivante :quotesdbs_dbs29.pdfusesText_35

[PDF] Allocation de Fréquences par Coloration de Graphes

Allocation de Fréquences par Coloration

Table des matières

1 Généralités2

1.1 Le problème d"allocation de fréquences . . . . . . . . . . . . . .. . . . . . . . . . . 2

1.2 Graphes, définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 3

1.3 Le problème de coloration . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 3

2 Graphes quelconques : des algorithmes d"approximation 4

2.1 Coloration séquentielle : l"algorithme glouton . . . . . .. . . . . . . . . . . . . . . 4

2.2 Deux heuristiques différentes . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 5

2.2.1 Welsh & Powell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2.2.2 DSATUR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Graphes triangulés : un algorithme linéaire de colorationoptimale 6

3.1 Généralités sur les graphes triangulés . . . . . . . . . . . . . .. . . . . . . . . . . . 6

3.2 Parcours en largeur lexicographique - LexBFS . . . . . . . . .. . . . . . . . . . . . 6

3.3 Affinage de partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 7

4 Résultats expérimentaux8

4.1 Sur des graphes pseudo-aléatoires . . . . . . . . . . . . . . . . . .. . . . . . . . . . 8

4.2 Sur des graphes de DIMACS . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 10

Conclusion et perspectives12

Références12

1 Généralités1.1 Le problème d"allocation de fréquences

Figure1 - Un réseau d"antennes

1.2 Graphes, définitions

Enfin, untrouest un cycle sans corde.

1.3 Le problème de coloration

Figure2 - Un graphe d"interférence coloré

2 Graphes quelconques : des algorithmes d"approximation2.1 Coloration séquentielle : l"algorithme glouton

Programme 1Coloration séquentielle

Sortie :Une coloration proprec:V→N

1:n :=|V|;

2:Couleur := Tableau(Taille : n) (Défaut :-1);

3:Pouri = 0 à n-1faire

4:x :=σ(i);

6:Libre := Tableau(Taille :???) (Défaut :vrai);

7:Poury? N(x)faire

8:SiCouleur.(y)?= -1alors

9:Libre.(Couleur.(y))←faux

10:Fin Si

11:Fin Pour

12:index := 0;

13:Tant QueLibre.(index) =fauxfaire

14:index := index + 1

15:Fin Tant Que

17:Couleur.(x)←index

18:Fin Pour

19:RenvoyerCouleur

Figure3 - Coloration séquentielle d"un graphe

2.2 Deux heuristiques différentes2.2.1 Welsh & Powell

2au lieu de 2). L"heuristique

2.2.2 DSATUR

1. Prendre un sommet non coloréxdeDSATmaximum.

2. Colorerxavec la plus petite couleur disponible.

3. Mettre à jourDSAT(y) poury? N(x).

O?n2?ouO?n2+nm?selon la structure utilisée.

DSAT= 1

DSAT= 1

DSAT= 1←2DSAT= 1←2

Sommet visit´es : 1,6,2

Figure4 - Une étape de l"algorithme DSATUR

3 Graphes triangulés : un algorithme linéaire de coloration

3.1 Généralités sur les graphes triangulés

Graphe Triangul´e

Sommet simplicial :

Tous ses voisins sont adjacents 2 `a 2

Sch´ema d"´elimination simplicial :

Figure5 - Illustrations

3.2 Parcours en largeur lexicographique - LexBFS

On effectue ensuite les opérations suivantes :

Pourivariant de0àn-1 :

1. Prendre un sommetxd"étiquette maximale pour?parmi les sommets non visités.

2. Affecter le numéroiàx.

3. Effectuer la mise à jourL(y)←L(y)·(n-i) poury? N(x)

Programme 2Parcours en Largeur Lexicographique

Sortie :Une bijectionσ:V→?0,n-1?

1:n :=|V|;

2:Numero := Tableau(Taille : n) (Defaut : -1);

3:Label := Tableau(Taille : n) (Defaut : "");

4:Pouri = 0 à n-1faire

5:Soit x tel que Label.(x) = max{Label.(y), Numero.(y) = -1};