[PDF] [PDF] Gloutonner Le principe de l'algorithme





Previous PDF Next PDF



[PDF] Gloutonner

Le principe de l'algorithme glouton (greedy algorithm) : On cherche `a obtenir une coloration des sommets d'un graphe qui



[PDF] Coloriage de sommets

Une coloration du graphe de Petersen avec 3 couleurs L'algorithme glouton centralisé est correct et termine en n étapes Il utilise ? + 1 couleurs



[PDF] L3 Info Cours 10 : Algorithmes gloutons Coloration de graphe

Complexité des algorithmes de graphes Coloration de graphe Il n'existe pas toujours un algorithme glouton pour résoudre un problème d'optimisation



[PDF] Coloration de graphes

Montrer qu'un graphe est 2-coloriable si et seulement si il ne possède pas de cycle de longueur impaire 2 Algorithme glouton Le problème du 2-coloriage est 



[PDF] Coloration de graphes - Collège sciences et technologies

ENSM - Éléments de Théorie des Graphes Une k-coloration (propre) d'un graphe (simple sans l'algorithme glouton suivant :



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

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



[PDF] Gloutonner

Montrer qu'une coloration du graphe par notre algorithme glouton de coloration utilise un nombre de couleurs égal au nombre chromatique avec une numérotation 



[PDF] L3 Info Cours 10 : Algorithmes gloutons Coloration de graphe

Complexité des algorithmes de graphes Coloration de graphe Il n'existe pas toujours un algorithme glouton pour résoudre un problème d'optimisation



[PDF] Coloration dun graphe

L'algorithme glouton consiste à parcourir les sommets par ordre croissant d'index en attribuant à chaque sommet la plus petite couleur disponible (c'est-à-dire 



[PDF] Coloration de graphes

L'algorithme glouton consiste à trouver un coloriage du graphe de la façon suivante : on numérote les sommets v1 vn de G puis on les colorie dans cet ordre 



[PDF] Chapitre 4 Coloration de graphes

On peut considérer un algorithme glouton qui affecte une couleur d'indice la plus petite possible `a un sommet v en fonction des voisins déj`a coloriés suivant 



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

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



[PDF] L3: cours Graphes I6S3 Chapitre III : coloration de graphe

7 jan 2019 · Cet algorithme colorie tout graphe G en au plus ?(G)+1 couleurs o`u ?(G) est le degré maximum des sommets de G En pratique il vaut mieux 



[PDF] Écrit Blanc dinformatique Préparation au CAPES de Mathématiques

19 déc 2018 · L'algorithme glouton construit un coloriage L d'un graphe G en utilisant au plus d(G)+1 couleurs Son principe est le suivant :

  • Comment faire algorithme glouton ?

    2.1.
    L'algorithme glouton sélectionne la plus grande valeur vn et la compare à s. somme restant à rendre étant alors s ? vn. L'algorithme continue avec la même système de pi?s Sn et cette nouvelle somme à rendre s ? vn. L'algorithme est ainsi répété jusqu'à obtenir une somme à rendre nulle.

  • Quand utiliser un algorithme glouton ?

    Cas d'usages d'algorithmes gloutons
    optimiser la mise en cache de données ; compresser des données ; organiser au mieux le parcours d'un voyageur visitant un ensemble de villes ; organiser au mieux des plannings d'activité ou d'occupations de salles.

  • Quel est le principe de l'algorithme de Dsatur ?

    L'algorithme DSATUR est un algorithme de coloration séquentiel, au sens où il colore un seul sommet non déjà coloré à la fois et tel qu'au départ le graphe n'est pas coloré.
  • Le problème de coloration de graphe consiste à assigner à chaque sommet une couleur de sorte que deux sommets adjacents n'aient pas la même couleur, tout en utilisant un nombre minimal de couleurs. Ce dernier est le nombre chromatique ?( ) du graphe G.

Gloutonner

G. Aldon - J. Germoni - J.-M. Meny

mars 2012

IREM 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 s

1,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 s

1,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 s

1,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 :

1342

Seconde numerotation :

1234

IREM 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, c

3, ...,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

c

01, les sommets de couleursc2en couleurc01ouc02, les sommets de

couleurc3en couleurc01ouc02ouc03...IREM de LYON ()gloutonmars 2012 7 / 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, c

3, ...,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

c

01, les sommets de couleursc2en couleurc01ouc02, les sommets de

couleurc3en couleurc01ouc02ouc03...IREM de LYON ()gloutonmars 2012 7 / 23

Illustration

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 82
59
46
73

IREM de LYON ()gloutonmars 2012 9 / 23

Illustration

Les sommets rouges reprennent la couleur rouge :1

82
59
46
73

IREM de LYON ()gloutonmars 2012 10 / 23

Illustration

Les sommets 5, 6, 7 voisins de sommets rouges prennent la couleur jaune :1 82
59
46
73

IREM de LYON ()gloutonmars 2012 11 / 23

Illustration

Le sommet 8 ne reprend pas sa couleur initiale :1

82
59
46
73

IREM de LYON ()gloutonmars 2012 12 / 23

Illustration

Le sommet 9 doit prendre une troisieme couleur :1

82
59
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 2468

IREM de LYON ()gloutonmars 2012 15 / 23

Un glouton tres mauvais

On numerote maintenant par colonne, l'algorithme donne 2 couleurs :1234 5678

IREM 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 gc

IREM 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 gc

IREM 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 / 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

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 23
45
768
ce qui donne la coloration suivante : c1c2c3c1c2c1c2c3IREM de LYON ()gloutonmars 2012 22 / 23

Glouton 2 { Preuve de l'optimalite

Lorsqu'un sommetvrecoit une couleurk, c'est que l'extremite gauche de l'intervallevappartient a au moinsk1 intervalles (sinon on pourrait choisir une couleur6k1 pourv).Tous ces intervalles se coupent (l'extremite gauche devest commun a tous) : le graphe presente donc une clique d'ordre>k, donc le nombre chromatique est d'au moinsk.IREM de LYON ()gloutonmars 2012 23 / 23

Glouton 2 { Preuve de l'optimalite

Lorsqu'un sommetvrecoit une couleurk, c'est que l'extremite gauche de l'intervallevappartient a au moinsk1 intervalles (sinon on pourrait choisir une couleur6k1 pourv).Tous ces intervalles se coupent (l'extremite gauche devest commun a tous) : le graphe presente donc une clique d'ordre>k, donc le nombre chromatique est d'au moinsk.IREM de LYON ()gloutonmars 2012 23 / 23quotesdbs_dbs7.pdfusesText_13
[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] cours cap coiffure la permanente

[PDF] cours coloration cap coiffure

[PDF] boxe anglaise veteran

[PDF] reglement boxe anglaise

[PDF] boxe anglaise technique de base