Les graphes colores ont ete introduits pour repondre a un besoin de
modelisation des reseaux multiniveaux dans une optique de planification
de la tolerance aux pannes. Ils decoulent du concept de Shared Risk
Resource Group (SRRG) ou groupe de ressources partageant un risque
d'indisponibilite. Par exemple dans un reseau de telecom, deux
connections routees via un meme cable tombent en panne simultanement
lorsque ce cable est coupe, ces deux connections partagent donc un
risque et ainsi forment un SRRG.
Un graphe colore est un graphe dont les aretes sont partitionnees en
couleurs. Dans les graphes classiques de nombreux problemes consistent
a trouver des ensembles d'aretes verifiant certaines proprietes (chemin,
coupe ...). Or dans un graphe colore les aretes sont liees entre elles
par leur couleur et non plus independantes et la donnee des aretes ne
suffit plus a determiner la structure du graphe. C'est pourquoi dans les
graphes colores, les problemes etudies consistent a trouver des
ensembles de couleurs.
En particulier, on defini un chemin colore entre deux sommets comme un
ensemble de couleur tel que le sous graphe induit par ses aretes
contient un chemin au sens classique entre ces sommets. De la meme facon
on defini une st-coupe coloree, une coupe coloree et un arbre couvrant
colore.
Nous verons que la complexite et l'approximabilite des problemes
d'optimisation associes (coupe colore minimum ...) sont tres differentes
de celles de leurs equivalents classiques.