Coloriage des graphes - theorie des graphes
Résolu/Fermé
la_l
Messages postés
15
Date d'inscription
jeudi 30 novembre 2006
Statut
Membre
Dernière intervention
6 avril 2008
-
22 mars 2007 à 10:37
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 23 mars 2012 à 19:27
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 23 mars 2012 à 19:27
A voir également:
- Coloriage des graphes - theorie des graphes
- Coloriage 2 - Télécharger - Études & Formations
- Coloriage sur ordinateur gratuit - Télécharger - Dessin & Illustration
- Comment faire des graphes sur excel - Guide
- Graphes excel - Guide
- Dessiner des graphes en ligne - Guide
10 réponses
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
22 mars 2007 à 16:18
22 mars 2007 à 16:18
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
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).
affecter des fréquences différentes a des cellules voisines dans 1 reseau de telephone mobile GSM (global_ system _for_ mobile_ communication).
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
8 mars 2008 à 16:37
8 mars 2008 à 16:37
C'est marrant c'est le premier exemple que j'ai donné :-)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
gyara
Messages postés
2
Date d'inscription
lundi 14 juillet 2008
Statut
Membre
Dernière intervention
14 juillet 2008
14 juil. 2008 à 09:14
14 juil. 2008 à 09:14
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+
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
23 mars 2012 à 19:27
23 mars 2012 à 19:27
https://forums.commentcamarche.net/forum/oldest/2790935-coloriage-des-graphes-theorie-des-graphes#5
Deux sites qui peuvent interférer sont reliés par un arcs.
Une fréquence correspond à une couleur.
Deux sites qui peuvent interférer sont reliés par un arcs.
Une fréquence correspond à une couleur.
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
15 juil. 2008 à 00:50
15 juil. 2008 à 00:50
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
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
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.
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.
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
14 janv. 2011 à 00:06
14 janv. 2011 à 00:06
On en a donné plusieurs exemples dans ce fil de discussion !
https://forums.commentcamarche.net/forum/affich-2790935-coloriage-des-graphes-theorie-des-graphes#1
https://forums.commentcamarche.net/forum/affich-2790935-coloriage-des-graphes-theorie-des-graphes#1
22 mars 2007 à 23:39