Coloriage des graphes - theorie des graphes [Résolu]

Exemple 1 : Le problème d'allocation de fréquence en télécom est un exemple classique. Chaque couleur désigne une fréquence, chaque sommet une antenne, deux sommets sont reliés si les deux antennes sont suffisamment proches pour interférer.

Exemple 2 : coloriage d'une carte géographique. Chaque pays est représenté par un sommet, si deux pays sont frontaliers on relie leurs sommets par une arète. On peut montrer que dans ce cas particulier, une borne supérieure du nombre chromatique est 4 car le graphe est planaire.

Exemple 3 : un problème de partitionnement peut être vue comme un problème de coloration. Chaque élément de l'ensemble à partitionner est représenté par un sommet. Chaque élément devant être situé dans une partition différente est relié par une arète. Chaque couleur désigne les partitions obtenues.

Bonne chance

1 problème peut se réduire a la résolution de coloration des graphes :
affecter des fréquences différentes a des cellules voisines dans 1 reseau de telephone mobile GSM (global_ system _for_ mobile_ communication).

merci

C'est marrant c'est le premier exemple que j'ai donné :-)

bonjour, je voudrai savoir comment appliquer la théorie de graphe en allocation de frequence en gsm car un site peut avoir plisieurs frequence tout en évitant les problème de frequence adjacent merci a+

Cf <1>

bnjour je suis étudiant en recherche opérationnelle Master 2 bah un tres bel exemple pour la coloration des sommets serais une intersection ou t'as les panneau de signalisation a mettre genre tu doit décider qui doit passer en premier , tu commence par definir tes sommets qui sont les différentes directions genre ah c'est la direction du chemin a vers h , une fois tout les sommets définies tu prends tes arretes par exemples et deux sommets sont adjacents si et seulement si les chemins se croisent une fois tn graphe tracé tu doit determiner une coloration minimale des sommets ( i.e determiner le nombre chromatique ) une fois tt es fait tu prends tn ensemble de couleurs par exmple Couleur 1 = { ab , cd , gf }
couleur 2 = { ec, gb ,vf } ... etc bah la tu prends les elements de l'ensemble 1 et ces les intersections ou y'auras la meme couleur genre de a vers b c'est vert de c vers d aussi la couleur 2 seras le rouge par exemple !!!!
j'espère tu m'as compris mais pour utiliser la théorie des graphes ds la vie réelle faut te tourner vers la modélisation ou L' Optimisation Combinatoire

voila je vous conseille ce lien le cours est bien détaillé :

http://coursuniversite.com/index.php?option=com_content&view=article&id=57&Itemid=43

;)
bon courage

Bonjour,
Je suis une etudiante en informatique de LMDet je cherche de l'aide sur le coloriage des graphes. Je voudrais chercher les problemes reels utilisant le coloriages des graphes surtout ceux qui utilisent essentiellement le coloriage des sommets. J'ai cherché mais j'ai pas su comment chercher. Je voudrais bien que vous me mettiez sur la bonne voix et m'aider à la recherche des problemes reels.
Merci d'avance.

On en a donné plusieurs exemples dans ce fil de discussion !
http://www.commentcamarche.net/...