Coloriage des graphes

Bonsoir à tous,

Bon voila je suis entrain de faire une recherche pour un rapport que je dois rendre portant sur les domaines d'application du coloriage des noeuds en theorie des graphes. Mais tous se que j'ai pu trouver se sont des informatinos non detailées telque : carte geographiques , alignement des etoiles , gestin d'emploie du temps

J'aimerais en savoir plus pour avancer dans mon rapport alors si quelqu'un on connait plus ou connait des sites sur lesquels je dois me rendre alors stp passer moi l'information

Merci

serenere a écrit:Bonsoir à tous,

Bon voila je suis entrain de faire une recherche pour un rapport que je dois rendre portant sur les domaines d'application du coloriage des noeuds en theorie des graphes. Mais tous se que j'ai pu trouver se sont des informatinos non detailées telque : carte geographiques , alignement des etoiles , gestin d'emploie du temps

J'aimerais en savoir plus pour avancer dans mon rapport alors si quelqu'un on connait plus ou connait des sites sur lesquels je dois me rendre alors stp passer moi l'information

Merci

Salut,
Alain Connes, un mathématicien français considère que les connaissances sur la théorie des graphes ne forment une théorie mais "un savoir, une série de faits".

[wikipedia]
Un graphe est un objet qui représente une relation binaire, orientée ou non, entre les éléments d'un ensemble. Avec les graphes, on peut modéliser plusieurs phénomènes et problèmes réels (plus court/long chemin d'un graphe, gestion de projets, optimisation de flots, etc...). Plusieurs problèmes académiques liés à la modélisation avec les graphes ont émergé. Leur étude a enrichi plusieurs autres domaines tels que L'algorithmique, la Complexité, la Recherche Opérationelle, l'Intelligence Artificielle...

Parmi les problèmes algorithmiques importants, on cite:
1. Isomorphisme de graphes (Complexité=NP-Complet)
2. Plus grand sous-graphe commun à deux graphes (Complexité=NP-Difficile)
3. Coloration de Graphe; (Complexité=NP-Complet)...

On va considérer le problème de , le définir et présenter l'essentiel de ses domaines d'applications.

A. Définition informelle
[à compléter]

B. Applications
Il existe plusieurs problèmes qui ont été résolu en ayant recours au problème de Coloration de Graphe. Ci-dessous une liste non exhaustive de ces problèmes. Pour voir les détails de la conception des solutions des ces problèmes, il suffit de taper dans un moteur de recherche telque [Vous devez être inscrit et connecté pour voir ce lien] des mots clés tels que "Time tabling + graph coloring +
Leignton", une liste de d'articles scientifiques publiés devraient être affichée. Attention: la majorité des articles ne sont malheureusement pas gratuits... Envoyez des emails à leurs propriétaires pour qu'ils vous fournissent des Working Papers concernant le sujet que vous demandeZ.

B.1 Time Tabling and Scheduling
Pour régler l'emploi du temps de toutes les classes dans une école, on a 3 types d'objets: (1) Matière enseignée (2) Enseignant (3) Classe. L'objectif c'est d'associer à chaque classe un nombre fixe de matières/enseignant, sachant qu'une matière ne peut pas être enseignée par le même PROF dans deux classes différentes à la même heure. C'est un problème de Coloration de Graphe. Il a été étudié par plusieurs chercheurs Leighton, Opsu and Roberts et Werra...
Pour plus de détails, se référer aux lienx ci-dessous.

B.2 Affectation des fréquence
Il s'agit d'affecter à chaque radio mobile une fréquence du spectre élctromagnétique. Une simple contrainte s'impose: deux entités assez proches en terme de distance, doivent avoir deux fréquences différentes, sachant que deux entités assez distantes peuvent se partager la même fréquence. Le problème de minimisation du nombre de fréquences affectées est un problème de Coloration de Graphe.

B.3 Allocation des registres Hardware
[à compléter]


C. Liens utilesIntroduction à la théorie des graphes
[Vous devez être inscrit et connecté pour voir ce lien]

A propos du problème de Coloriage de Graphes
[Vous devez être inscrit et connecté pour voir ce lien]

Applications du Coloriage de Graphe
[Vous devez être inscrit et connecté pour voir ce lien]


J'invite tous les intéressés à compléter ce qui manque dans cette réponse.
Merci d'avance pour la collaboration.

B.Nabil

serenere a écrit:Bonsoir à tous,

Bon voila je suis entrain de faire une recherche pour un rapport que je dois rendre portant sur les domaines d'application du coloriage des noeuds en theorie des graphes. Mais tous se que j'ai pu trouver se sont des informatinos non detailées telque : carte geographiques , alignement des etoiles , gestin d'emploie du temps

J'aimerais en savoir plus pour avancer dans mon rapport alors si quelqu'un on connait plus ou connait des sites sur lesquels je dois me rendre alors stp passer moi l'information

Merci

Merci à tous c 1 sujet trèssss intéressant!

Merci pour votre aide Nabil, c'est bon j'ai fini mon rapport et on m'a meme demandé d'en faire un exposé lol mais je tiens comme meme a completer se que t'as deja mis. Merci encore

II- Coloriage des nœuds d’un Graphe :
1-Définition :

Soit un ensemble fini C appelé l’ensemble des couleurs. Un coloriage d’un graphe
G est une fonction c : S(G) −→ C qui affecte une couleur à chaque sommet, et qui est telle que deux sommets voisins n’ont pas la même couleur. Un graphe est k-coloriable s’il peut être colorié au moyen d’un ensemble de k couleurs. Il existe d’autres notions de coloriage des graphes (on peut demander que chaque arc ait une couleur différente de celle des arcs incidents, on peut aussi mettre d’autres contraintes que la différence de couleur de deux sommets voisins).
Le nombre chromatique d’un graphe G est le nombre minimum χ(G) de
couleurs d’un coloriage. Il n’est pas très difficile de montrer que χ(G) ≤ Degré(G) + 1. (On construit un arbre recouvrant en profondeur et on colorie les sommets dans l’ordre associé en utilisant à chaque fois la plus petite couleur disponible.) L’égalité a lieu pour un graphe complet, ainsi que pour un cycle impair. Un théorème difficile de Brooks (1941) montre que ce sont les seuls cas où l’égalité est atteinte. Ainsi pour un graphe de degré d au moins 3
qui ne contient pas Kd+1 comme sous-graphe, on a χ(G) ≤ d.

2-Proprietés :
- Déterminer le nombre chromatique d'un graphe est un problème NP-Complet dans le cas général.
- Pour tout graphe biparti, γ(G) = 2.
- Si D est le degré maximal du graphe, c'est-à-dire le plus grand degré parmi les degrés des sommets, alors le nombre chromatique est inférieur ou égal à 1+D. Le nombre chromatique est aussi supérieur ou égal à l'ordre du plus grand sous graphe complet du graphe.

3-Methodes :
Algorithme de Welsh et Powell
1- Repérer le degré de chaque sommet.
2- Ranger les sommets par ordre de degrés décroissants.
3- Attribuer au premier sommet (A) de la liste une couleur.
4- Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A).
5- Suivre (si possible) la liste jusqu'au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
6- Continuer jusqu'à ce que la liste soit finie.
7- Prendre une deuxième couleur pour le premier sommet (D) non encore colorié de la liste.
8- Répéter les opérations 4 à 6.
9- Continuer jusqu'à avoir colorié tous les sommets.
Remarque : Cette méthode n'aboutit pas forcément à une coloration minimale. Il faut donc observer si on peut faire mieux (c'est-à-dire avec moins de couleurs).


-Allocation des registres Hardware :
Les registres sont des mémoires internes au processeur, généralement capables de contenir un mot machine. Les opérations sur des valeurs rangées dans des registres sont considérablement plus rapides que celles sur des valeurs en mémoire vive, quand ce ne sont pas les seules possibles. Mais ils sont en nombre très limité, et souvent trop faible pour ranger toutes les variables d'un programme. Il est donc crucial de choisir avec pertinence les variables qui doivent résider dans les registres à chaque étape de l'exécution. Cela étant difficile dans les premières étapes de la compilation, on commence par faire comme si l'on disposait d'un nombre illimité de registres, puis l'on attribue à ces registres virtuels des registres réels ou des emplacements en mémoire
L'une des méthodes classiques d'allocation de registres consiste à ramener le problème au coloriage du graphe d'interférence des variables. Les sommets de ce graphe sont les variables du programme, et deux sommets sont reliés par une arête si les variables correspondantes interfèrent.
On dit que deux variables interfèrent lorsque l'une est définie pendant que l'autre est active (c'est-à-dire susceptible d'être utilisée dans la suite de l'exécution). Deux variables qui interfèrent ne peuvent pas être placées dans le même registre à une nuance technique près : sur certains processeurs, les registres ne sont pas équivalents. On étend donc aux registres la relation d'interférence, en convenant qu'ils interfèrent tous entre eux, et qu'une variable interfère avec les registres qui lui sont interdits. Ainsi, on ne peux colorier avec le même registre deux variables qui sont voisines dans le graphe d'interférence. Attribuer k registres aux variables équivaut à colorier avec k couleurs le graphe d'interférences.
Le problème du k-coloriage est NP-complet (pour ) et pour un graphe quelconque. Comme pour n'importe quel graphe G il est possible de créer un programme dont le graphe d'interférences est G, le problème d'allocation de registres est aussi NP-complet. Aussi on utilise en général une heuristique qui fournit de bons résultats pratiques. Elle consiste à supprimer du graphe les sommets faciles à colorier : on cherche dans le graphe un sommet de degré strictement inférieur à k. On est certain de pouvoir colorier ce sommet puisque ses voisins utiliseront au plus k − 1 couleurs. Ainsi on le supprime du graphe et on le garde de côté. Si on arrive à colorier récursivement le graphe simplifié, alors on pourra le réinsérer et le colorier.
Si tous les sommets ont au moins pour degré k, plusieurs stratégies sont possibles :
• On peut continuer le coloriage et retirer à chaque étape un sommet de degré minimal, en espérant que deux de ses voisins auront la même couleur, de sorte que l'on parviendra à le colorier à la remontée. Lors de la remontée, on attribue alors à chaque sommet rencontré la première couleur disponible, quitte à dépasser k, puis on évalue le coût de rangement en mémoire des variables de chaque couleur, pour affecter à chacune un registre réel ou une case mémoire. Il est possible de faire un peu mieux, en essayant de choisir pour chaque sommet une couleur parmi celles des voisins de ses voisins.
• Une autre méthode consiste à sélectionner, au contraire, un sommet de degré maximal, dans l'espoir que sa suppression simplifiera considérablement le graphe. Si l'on dispose d'informations sur le coût de mise en mémoire, un meilleur indicateur est le quotient du coût de mise en pile par le degré. Les systèmes d'allocation de registres réels utilisent des heuristiques un peu plus perfectionnées, qui peuvent combiner ces deux méthodes. Notons enfin qu'il est parfois moins coûteux de recalculer une valeur (si les opérandes résident dans des registres, par exemple) que de l'enregistrer pour la relire.






Thx a lot

Salut serenere,
j'ai trouvé que ce site est très intéressant. Il pourrait t'aider énormément:

[Vous devez être inscrit et connecté pour voir ce lien]

Pour ton exposé, voilà de la matière première prête à consommer :

[Vous devez être inscrit et connecté pour voir ce lien]

On discutera plutard si jamais il y a encore des trucs ambigus.

B.NabiL

[Vous devez être inscrit et connecté pour voir ce lien]
J'ATTENDS VOS COMMENTAIRES
Merci

serenere a écrit:[Vous devez être inscrit et connecté pour voir ce lien]
J'ATTENDS VOS COMMENTAIRES
Merci

bravo serenere, c'est un bon exposé - il faut pas oublier une diapo de MERCI DE VOTRE ATTENTION à la fin de l'exposé

B.NabiL