Coloration de graphes: structures et algorithmes
15 nov. 2007 donc àassocier àchaque sommet du graphe une couleur ... Une coloration optimale d'un graphe est une coloration qui utilise le moins.
1. Colorations
Le nombre chromatique d'un graphe G noté ?(G)
Couplages et colorations darêtes
lieu chaque jour ce qui nécessite donc au moins n jours pour l'ensemble des matchs. En termes de graphes
3–Coloration dun graphe
Démonstration. Étape 1 : 3Col ? NP. Ce problème est bien dans NP car on peut vérifier en temps polynomial (en le nombre d'arêtes du graphe) qu'une
Colorations des sommets
Le plus petit nombre de couleurs nécessaire pour colorer les sommets d'un graphe G est appelé « le nombre chromatique » de G et est noté ?(G). On peut aussi
Colorations des sommets
Le plus petit nombre de couleurs nécessaire pour colorer les sommets d'un graphe G est appelé « le nombre chromatique » de G et est noté ?(G). On peut aussi
Les graphes planaires
Francis Guthrie a donc voulu savoir s'il est toujours possible de colorer les sommets d'un graphe planaire en utilisant uniquement 4 couleurs avec comme unique
Gloutonner
Le plus petit nombre de couleurs permettant la coloration est appelé nombre chromatique du graphe. IREM de LYON () glouton mars 2012. 3 / 23
Coloriage de sommets
Colorer un réseaux signifie attribuer une couleur `a chacun de Une coloration du graphe de Petersen avec 3 couleurs. Algorithmique répartie - Cours de ...
Coloration dun 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 ai
Travaux pratiquesoption informatique
Coloration d"un grapheOn considère un graphe non orientéG= (V;E), et on appellek-colorationdeGune applicationc:V!~0;k1telle que
(a;b)2E=)c(a),c(b). Le problème de la coloration d"un graphe consiste à trouver unek-coloration deGpour laquelle la
valeur dekest la moins élevée possible.Les sommets d"un grapheGd"ordrenseront désignés par les entiers0;1;:::;n1etGsera représenté par les listes
d"adjacence de ses sommets; autrement dit, nous définissons les types :typevoisinage == int list ;;
typegraphe == voisinage vect ;;Unek-colorationcsera représentée par un vecteurcouleurde typeint vectdéfini parcouleur.(i)=c(i), 06i6n1.
Question 1.
Rédiger une fonctioncoloration_validequi prend en argument un grapheGet un vecteurcouleuretqui retournetruesicouleurest une coloration de G, etfalsesinon.coloration_valide : graphe> int vect> boolIndication. On pourra utiliser la fonctionnellefor_allde type("a> bool)> "a list> bool.
Exprimer en fonction den=jVjetp=jEjle coût de cette fonction.Graphe biparti
Un graphe qui possède une 2-coloration est ditbiparti: il existe une partition deVen deux ensemblesAetBtelle que
toute arête de E relie un sommet de A à un sommet de B.0246 1357Figure1 - Un exemple de graphe biparti.
Question 2.
Rédiger une fonctionbipartiqui prend en argument un graphesupposé bipartiet retourne une 2-coloration
de ce dernier.biparti : graphe> int vectÉvaluer en fonction denetple coût de cet algorithme.Un algorithme glouton
La question précédente a montré que le problème de la 2-coloration possède une solution en temps polynomial enn. Ce
n"est malheureusement pas le cas du problème général : tous les algorithmes connus garantissant une coloration optimale
sont de complexité exponentielle. C"est la raison pour laquelle nous allons nous intéresser à des solutions gloutonnes qui,
à défaut de garantir une solution minimale, fournissent des colorations acceptables.Question 3.
L"algorithme glouton consiste à parcourir les sommets par ordre croissant d"index, en attribuant à chaque
sommet la plus petite couleur disponible (c"est-à-dire non déjà donnée à un de ses voisins). Rédiger la fonctionglouton
correspondante.glouton : graphe> int vectCette fonction retourne-t-elle une coloration optimale pour le graphe biparti présenté figure 1?
www.info-llg.frpage 1Graphes d"intervallesÀ un ensemble fini d"intervalles[ai;bi[,06i6n1on associe un grapheG= (V;E)pour lequel les sommets deVsont les
intervalles et dont les arêtes relient les couples d"intervalles dont l"intersection est non vide. Un tel graphe est appelé
graphe d"intervalle.v 0v 1v 2v 3v 4v 5v 6v 70123 4 5 67
Figure2 - Un exemple de graphe d"intervalles.
Question 4.
a)Montrer que pour un graphe d"intervalles, l"algorithmegloutonfournit une coloration minimale lorsque les sommets
sont ordonnés par valeurs deaicroissantes. b)Montrer que pour un grapheGquelconque il existe toujours un ordonnancement des sommets pour lequel l"algorithme
glouton fournit un résultat optimal.Algorithme DSATUR
Cet algorithme est une variante de l"algorithme glouton, dans lequel on essaie de choisir " au mieux » le prochain sommet
à devoir être coloré. Pour cela on introduit la notion dedegré de saturation: en cours d"exécution, et pour toutv2V,ds(v)
est le nombre de couleurs distinctes d"ors et déjà utilisées pour colorer les voisins dev.À chaque étape, l"algorithme DSATUR attribue au sommet vierge de degré de saturation maximal la plus petite couleur
disponible. En cas d"égalité, c"est le sommet de degré maximal qui est choisi. Question 5.On suppose désormais les sommets triés par degré décroissant.Rédiger une fonctiondsqui prend en arguments un grapheGen cours de coloriage, le tableaucouleurdes couleurs déjà
attribuées et un sommetvet qui retourne le degré de saturation dev.ds : graphe> int vect> int> int
Rédiger une fonctionsatmaxqui prend en arguments un grapheGen cours de coloriage et le tableaucouleurdes couleurs
déjà attribuées et qui retourne le sommet vierge de saturation maximale (et en cas d"égalité, celui de degré maximal).satmax : graphe> int vect> int
En déduire une fonctiondsaturqui prend en argument un graphe trié par ordre décroissant de degré et retourne la
coloration de ce dernier obtenue par application de l"algorithme DSATUR.dsatur : graphe> int vectQuestion 6.
a)Montrer qu"appliqué à un graphe biparti, l"algorithme DSATUR retourne une 2-coloration. b)Appliquer cet algorithme au graphe ci-dessous. La coloration obtenue est-elle optimale?70 6 1425 3 page 2quotesdbs_dbs28.pdfusesText_34
[PDF] 5: La coloration de Gram - BiOutils
[PDF] 5: La coloration de Gram - BiOutils
[PDF] COLORATION AU BLEU DE METHYLENE COLORATION DE GRAM
[PDF] Une nouvelle méthode simple et rapide de coloration différentielle
[PDF] COLORATION AU BLEU DE METHYLENE COLORATION DE GRAM
[PDF] Coloriages magiques
[PDF] Coloriages magiques avec les lettres 5-7 ans
[PDF] Coloriages magiques avec les lettres 5-7 ans
[PDF] Images correspondant ? coloriage petit loup imprimer filetype:pdf
[PDF] Faut-il dépister le cancer colo-rectal chez la personne âgée?
[PDF] Quand faut-il faire une coloscopie de contrôle après une - HAS
[PDF] Dépistage et prévention du cancer colorectal - HAS
[PDF] Quel rythme de surveillance après une coloscopie - Hepatowebcom
[PDF] Réglement de la Banque d 'Algérie 2016 - Douanes Algériennes
