problème de 3 couleurs

La question :

Bonjour messieurs,
Voici un algorithme pour 3 couleurs :
Soit G un graphe planaire qui a 3-clique comme clique maximum, on note
chaque 3-clique par triangle.

G contient plusieurs triangles, placer les un à coter des autres, ou
séparer par des arrêts.

1) Zone de colorisation obligatoire simple :
Si on donne à un triangle les couleurs 1,2 et 3, on peut trouver des
arrêts qui seront coloré d'une manière obligatoire, après avoir
tous les zones on a le résultat suivant :
a- il y a une zone avec 4 couleurs, cela applique que G ne peut être
colore avec 3 couleurs.
b- Il n y a pas des zones avec 4 couleurs, on ne peut rien dire...


2) Zone de colorisation obligatoire composée :
Une zone est dite composée si il contient 2 ou plus des zones simples
de tel manière que la colorisation de zone i oblige la colorisation du
zone j, après avoir tous les zones on a le résultat suivant :
a- il y a une zone avec 4 couleurs, cela applique que G ne peut être
colore avec 3 couleurs.
b- Il n y a pas des zones avec 4 couleurs, alors G est colorer avec 3
couleurs.

Alors quelle est vos commentaires ?

Poser votre question sur le forum Programmation

Les 6 réponses :

On 30 Sep 2006 05:06:49 -0700, "mimouni" :


Alors quelle est vos commentaires ?


Je t'invite à consulter ton professeur d'algorithmique, ainsi que ton
professeur de français.

Le Sat, 30 Sep 2006 14:35:13 +0200, Fabien LE LEZ a écrit :


Je t'invite à consulter ton professeur d'algorithmique, ainsi que ton
professeur de français.


Je crois deviner qu'il n'est pas francophone à la base. On peut donc lui
pardonner ses problèmes de langage.

--
Tom

Le Sat, 30 Sep 2006 05:06:49 -0700, mimouni a écrit :


Alors quelle est vos commentaires ?


T'aurais pas une question plus précise par hasard ?

--
Tom

Tom a écrit :


Le Sat, 30 Sep 2006 05:06:49 -0700, mimouni a écrit :


Alors quelle est vos commentaires ?


T'aurais pas une question plus précise par hasard ?

--
Tom


je veut seulement savoir la compexité de l'algorithme, et un contre
exemple.
--
mimouni

Le Sat, 30 Sep 2006 16:37:39 -0700, mimouni a écrit :


je veut seulement savoir la compexité de l'algorithme, et un contre
exemple.


Bah il est pas très précis ton algo. Tu cherche à faire quoi ? A
déterminer si un graphe planaire de clique maximum 3 est colorable avec 3
couleurs ? Pourquoi n'y a-t-il que ces deux cas là ? De toutes manières
pour une clique de taille 3 il faut 3 couleurs. Utilise-tu le fait que le
graphe est planaire ? Comment ?
Pour trouver la complexité il faudrait quelque chose de plus précis. Pour
donner un contre exemple il faudrait savoir un contre-exemple de quoi :
validité ? optimalité ?

--
Tom

Poser votre question sur le forum Programmation

Questions similaires :

Idees pour resoudre un probleme

Bonjour, Je recherche une ligne directrice pour trouver un algo efficace pour resoudre le probleme suivant: "Etant donne une liste de rectangles (decrit par leur longueur et leur largeur), trouver un rectangle dont l'aire est la plus petite possible et recouvrant tous les rectangles donnes en...

couleurs automatiques

Bonjour, je travaille sur un site de géolocalisation en PHP, javascript. Je souhaiterais différencier différents parcours dont certains peuvent se chevaucher en différentes couleurs, suffisament différentes pour être visibles ainsi que les zones de superposition. J'aimerais éviter des tables...

Petit problème de géographie.

Bonjour. "dvanhee" a écrit dans le message de news J'avais ébauché un truc de ce genre il y a longtemps, à base de géométrie constructive... De mémoire: on parcours les points du contour (polygone) en considérant pour chaque nouveau point: - le triangle qu'il forme avec les...

Autre problème graphisme

Bonjour à tous Me revoilà avec un nouveau petit problème : J'ai une image couleur codée sur 24 bits (8 bits pour le Rouge, 8 bits pour le Vert et 8 bits pour le Bleu) Je dois arriver à réduire le nombre de couleurs dans l'image finale car chaque pixel est codé sur un nombre de bits variable de 1 bit...

Trouver des frontières entre couleurs

Bonjour, je traite des images prises par une caméra digitale (24bpp) et je cherche à localiser un rectangle blanc ou coloré sur un fond "uniforme" noir. mon problème est que selon la taille et l'albedo de la zone à repérer le dispositif d'acquisition fait de équilibrages de couleurs / balance...