Gloutonner - Claude Bernard University Lyon 1
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 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
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 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
Gloutonner
G. Aldon - J. Germoni - J.-M. Meny
mars 2012IREM de LYON ()gloutonmars 2012 1 / 23
Algorithme glouton
Le principe de l'algorithme glouton (greedy algorithm) : faire toujours un choix localement optimal dans l'espoir que ce choix menera a une solution globalement optimale.IREM de LYON ()gloutonmars 2012 2 / 23
Coloration des sommets d'un graphe
On cherche a obtenir une coloration des sommets d'un graphe qui satisfasse a la contrainte suivante : deux sommets voisins n'ont jamais la m^eme couleur. On cherche a optimiser le nombre de couleurs utilisees. Le plus petit nombre de couleurs permettant la coloration est appele nombre chromatique du graphe.IREM de LYON ()gloutonmars 2012 3 / 23
Algorithme glouton
On considere l'algorithme suivant :Input. Un graphe G et des couleurs 1,2,3,4...Les sommets deGsont numerotes de 1 an(s1,s2,...,sn).Output. Une coloration valide du grapheG. Mais le nombre de couleurs utilisees est-il minimal?Traitement. Pouriallant de 1 an, aecter au sommetsila plus petite couleur non deja aectee a ses voisins deja colories (c'est-a-dire la plus petite couleur non deja aectee a ceux des sommets s1,s2,...,si1qui lui sont adjacents). En d'autres termes, on
gloutonne : on s'attache, localement, a ne pas augmenter le nombre de couleurs lorsque c'est possible.IREM de LYON ()gloutonmars 2012 4 / 23
Algorithme glouton
On considere l'algorithme suivant :Input. Un graphe G et des couleurs 1,2,3,4...Les sommets deGsont numerotes de 1 an(s1,s2,...,sn).Output. Une coloration valide du grapheG. Mais le nombre de couleurs utilisees est-il minimal?Traitement. Pouriallant de 1 an, aecter au sommetsila plus petite couleur non deja aectee a ses voisins deja colories (c'est-a-dire la plus petite couleur non deja aectee a ceux des sommets s1,s2,...,si1qui lui sont adjacents). En d'autres termes, on
gloutonne : on s'attache, localement, a ne pas augmenter le nombre de couleurs lorsque c'est possible.IREM de LYON ()gloutonmars 2012 4 / 23
Algorithme glouton
On considere l'algorithme suivant :Input. Un graphe G et des couleurs 1,2,3,4...Les sommets deGsont numerotes de 1 an(s1,s2,...,sn).Output. Une coloration valide du grapheG. Mais le nombre de couleurs utilisees est-il minimal?Traitement. Pouriallant de 1 an, aecter au sommetsila plus petite couleur non deja aectee a ses voisins deja colories (c'est-a-dire la plus petite couleur non deja aectee a ceux des sommets s1,s2,...,si1qui lui sont adjacents). En d'autres termes, on
gloutonne : on s'attache, localement, a ne pas augmenter le nombre de couleurs lorsque c'est possible.IREM de LYON ()gloutonmars 2012 4 / 23
Une coloration non necessairement optimale
Appliquer l'algorithme au graphe ci-dessous avec plusieurs numerotions des sommets et en deduire que l'algorithme ne donne pas necessairement le nombre chromatique.IREM de LYON ()gloutonmars 2012 5 / 23
Une coloration non necessairement optimale
Premiere numerotation :
1342Seconde numerotation :
1234IREM de LYON ()gloutonmars 2012 6 / 23
La coloration peut ^etre optimale
Exercice.Etablir qu'on peut toujours numeroter les sommets de facon a obtenir le nombre chromatique en appliquant l'algorithme.Preuve. On suppose disposer d'une coloration optimale par les couleursc1,c2, c3, ...,c.On numerote d'abord les sommets de couleurc1, puis les sommets de
couleurc2, puis les sommets de couleurc3...L'algorithme colorie alors les sommets de couleurc1en une couleur
c01, les sommets de couleursc2en couleurc01ouc02, les sommets de
couleurc3en couleurc01ouc02ouc03...IREM de LYON ()gloutonmars 2012 7 / 23La coloration peut ^etre optimale
Exercice.Etablir qu'on peut toujours numeroter les sommets de facon a obtenir le nombre chromatique en appliquant l'algorithme.Preuve. On suppose disposer d'une coloration optimale par les couleursc1,c2, c3, ...,c.On numerote d'abord les sommets de couleurc1, puis les sommets de
couleurc2, puis les sommets de couleurc3...L'algorithme colorie alors les sommets de couleurc1en une couleur
c01, les sommets de couleursc2en couleurc01ouc02, les sommets de
couleurc3en couleurc01ouc02ouc03...IREM de LYON ()gloutonmars 2012 7 / 23Illustration
Appliquer le principe de la demonstration precedente au graphe ci-dessous pour lequel on a donne une coloration optimale.IREM de LYON ()gloutonmars 2012 8 / 23
Illustration
On numerote, par exemple, comme suit suivant l'ordre,,des couleurs :1 8259
46
73
IREM de LYON ()gloutonmars 2012 9 / 23
Illustration
Les sommets rouges reprennent la couleur rouge :1
8259
46
73
IREM de LYON ()gloutonmars 2012 10 / 23
Illustration
Les sommets 5, 6, 7 voisins de sommets rouges prennent la couleur jaune :1 8259
46
73
IREM de LYON ()gloutonmars 2012 11 / 23
Illustration
Le sommet 8 ne reprend pas sa couleur initiale :1
8259
46
73
IREM de LYON ()gloutonmars 2012 12 / 23
Illustration
Le sommet 9 doit prendre une troisieme couleur :1
8259
46
73
IREM de LYON ()gloutonmars 2012 13 / 23
Un glouton tres mauvais?
L'algorithme glouton propose ne donne pas necessairement le nombre minimum de couleurs. Mais peut-il ^etre tres mauvais (du point de vue du nombre de couleurs utilisees)? Montrer que oui avec des graphes construits comme le suivant :IREM de LYON ()gloutonmars 2012 14 / 23
Un glouton tres mauvais
On numerote d'abord ligne par ligne de gauche a droite. L'algorithme donne 4 couleurs :1357 2468IREM de LYON ()gloutonmars 2012 15 / 23
Un glouton tres mauvais
On numerote maintenant par colonne, l'algorithme donne 2 couleurs :1234 5678IREM de LYON ()gloutonmars 2012 16 / 23
Un glouton tres mauvais
En generalisant sur ce type de graphe, on obtient des graphes colores avec l'algorithme, aveckcouleurs,kentier xe a l'avance aussi grand que desire, alors que le nombre chromatique est 2.IREM de LYON ()gloutonmars 2012 17 / 23
Les epreuves du gymnase
On reprend le probleme du gymnase : on veut que se deroule, sur 24 h, le plus grand nombre possible d'epreuves, chaque epreuve etant caracterisee par une heure de debut et une heure de n. On cherche maintenant le nombre minimal de gymnases permettant le deroulement de toutes les epreuves.IREM de LYON ()gloutonmars 2012 18 / 23
Glouton 1
Les dates de n au plus t^ot ayant permis le deroulement d'un nombre optimal d'epreuves avec un seul gymnase, on essaie de "remplir" le gymnase 1 au maximum avec ce principe, puis on passe a un gymnase 2, puis ...Verier que le resultat n'est pas optimal avec la situation suivante : h ab def gcIREM de LYON ()gloutonmars 2012 19 / 23
Glouton 1
Les dates de n au plus t^ot ayant permis le deroulement d'un nombre optimal d'epreuves avec un seul gymnase, on essaie de "remplir" le gymnase 1 au maximum avec ce principe, puis on passe a un gymnase 2, puis ...Verier que le resultat n'est pas optimal avec la situation suivante : h ab def gcIREM de LYON ()gloutonmars 2012 19 / 23
Glouton 1
Le gymnase 1 verra se derouler les epreuves :h;d;e, le gymnase 2 :a;f le gymnase 3 :b;g le gymnase 4 :c. Alors que 3 gymnases susent :h;c;f{a;d;e{b;g.IREM de LYON ()gloutonmars 2012 20 / 23Glouton 2
On represente les intervalles de tempsh
ab def gc par le graphe des incompatibilites : h ab cd feg Montrer qu'une coloration du graphe par notre algorithme glouton de coloration utilise un nombre de couleurs egal au nombre chromatique avec une numerotation des sommets correspondant a l'ordre croissant des extremites gauche des intervalles.IREM de LYON ()gloutonmars 2012 21 / 23
Glouton 2
On represente les intervalles de tempsh
ab def gc par le graphe des incompatibilites : h ab cd feg Montrer qu'une coloration du graphe par notre algorithme glouton de coloration utilise un nombre de couleurs egal au nombre chromatique avec une numerotation des sommets correspondant a l'ordre croissant des extremites gauche des intervalles.IREM de LYON ()gloutonmars 2012 21 / 23
Glouton 2 { Illustration
Numerotation des sommets pour l'application de l'algorithme (ordre croissant des debuts d'epreuves) :1 2345
768
ce qui donne la coloration suivante : c1c2c3c1c2c1c2c3IREM de LYON ()gloutonmars 2012 22 / 23