Discussion :

[shenz]

Bonjour à tous.

Je bloque actuellement sur un petit problème de conception sur une problématique d'affectation de valeurs.

Voila ce que je dois faire:
Dans un amphi, je dois placer les élèves de plusieurs classes en leur attribuant un numéro de table.
Les élèves d'une même classe ne doivent jamais être côte à côte.
Le nombre d'élève par classe est très aléatoire. Certaines formations comptent jusqu'à 50 élèves alors que d'autres n'en comptent qu'une dizaine.

Ne connaissant pas le nombre de place dans chaque amphi, on va partir du principe que la personne qui utilisera l'appli vérifiera que le nombre total d'élève est inférieur au nombre de place dans l'amphi. Mais on verra aussi que cela m’empêche certains contrôles.

Le classement se ferait amphi par amphi, donc le traitement concernerait au max 150 élèves à chaque fois.

En entrée:
La liste des élèves au départ est un fichier excel. Je pensais donc passer par un extract en csv dans un 1er temps.
Ma méthode principale prendrait donc en entrée mon fichier csv.

Les colonnes du fichier serait du type:
NOM;PRENOM;CLASSE

En sortie:
Après traitement, je voudrais une sortie CSV du type:
PLACE;NOM;PRENOM;CLASSE

TODO:
Pour l'instant, au niveau de la lecture du CSV, j'ai fait un tableau de String[] à partir de chaque ligne du fichier (ce qui correspond aux info sur chaque élève).
Je pensais partir sur une HashMap ayant pour clé le nom de la classe et en valeur un autre tableau de String[] des élèves correspondants.
HashMap<NOM CLASSE, ArrayList<String[]>>

C'est là que ça se complique. Le positionnement des élèves me pose problème.

Je pensais pour chaque "clé" de la Map, vérifier le nombre d'élèves associés (taille de chaque tableau).
Puis placer les élèves dans une Map triée (TreeMap ??) avec en clé le numéro de table dans l'amphi et en valeur le String[] correspondant aux infos de l'élève concerné. Le positionnement se faisant, modulo le nombre de classe (ou de clés) en commençant par la classe contenant le moins d'élèves.

Exemple/Problématique:
Sur 3 classes A (7 élèves), B (3 élèves) et C (9 élèves).
Avec x, une position non attribuée.
1ère boucle sur la classe B Modulo 3 classes:
B,x,x,B,x,x,B
2ème boucle sur la classe A Modulo 3 classes en commençant à la position +1.
B,A,x,B,A,x,B,A,x,x,A,x,x,A,x,x,A,x,x,A
3ème boucle sur la classe C, Modulo 3 en commençant à la position +2.
B,A,C,B,A,C,B,A,C,x,A,C,x,A,C,x,A,C,x,A,C,x,x,C,x,x,C

==> On voit bien mon problème ici. Des places restent vides. Ce qui signifie avec cette méthode que le nombre de place que j'attribue peut devenir supérieur au nombre de places dans l'amphi.
==> Il faudrait alors refaire un nouveau passage pour décaler chaque élève.
==> Sachant qu'il faut être sûr que les élèves d'une même classe ne soient pas à côté (au pire ils doivent être séparés d'une table) => on a été élèves, on sait bien que certains sont tentés de regarder sur la feuille du voisin

Je n'ai pas non plus (pour l'instant) d'impératif d'ordonnancement alphabétique par classe.

Une fois ma Map finalisée, il faudrait réécrire dans mon fichier csv de sortie tel que défini plus haut.


Je ne sais pas si mes explications sont très claires.
J'ai essayé d'illustrer par un exemple pour vous faire comprendre la problématique.
Je voudrais donc des conseils, à savoir si vous connaissez une méthode plus simple, et surtout valide, qui me permettrait de positionner mes élèves?
Peut être que ce que je souhaite faire existe déjà, et je n'ai peut être pas besoin de réinventer la roue... mais je n'ai rien trouvé pour l'instant.

Merci d'avance pour vos réponses.

Bonne journée à tous.

Cordialement.

[Mopmop]

Bonjour,

Les élèves d'une même classe ne doivent jamais être côte à côte.

Côte à côte veut dire deux numéros qui se suivent ? Ou il y a des subtilité genre les places juste devant et juste derrière sont considérées comme "à coté" ?

Le nombre d'élève par classe est très aléatoire. Certaines formations comptent jusqu'à 50 élèves alors que d'autres n'en comptent qu'une dizaine.
Ne connaissant pas le nombre de place dans chaque amphi, on va partir du principe que la personne qui utilisera l'appli vérifiera que le nombre total d'élève est inférieur au nombre de place dans l'amphi. Mais on verra aussi que cela m’empêche certains contrôles.

On part du principe que le problème peut être résolu ou il faut aussi vérifier ça ? Par exemple si on prend N le nombre de place, il ne faut pas de classe ayant plus de N/2 élèves... sauf si on prend en compte les rangs.

En entrée:
La liste des élèves au départ est un fichier excel. Je pensais donc passer par un extract en csv dans un 1er temps.
Ma méthode principale prendrait donc en entrée mon fichier csv.

Les colonnes du fichier serait du type:
NOM;PRENOM;CLASSE

En sortie:
Après traitement, je voudrais une sortie CSV du type:
PLACE;NOM;PRENOM;CLASSE

TODO:
Pour l'instant, au niveau de la lecture du CSV, j'ai fait un tableau de String[] à partir de chaque ligne du fichier (ce qui correspond aux info sur chaque élève).
Je pensais partir sur une HashMap ayant pour clé le nom de la classe et en valeur un autre tableau de String[] des élèves correspondants.
HashMap<NOM CLASSE, ArrayList<String[]>>

Je ne partirais pas comme ça. Autant utiliser les objets, pour que ça soit plus facile si besoin d'évolution (genre ordre alphabétique...)
Du coup je me ferais une classe "Eleve" contenant nom, prénom, numéro de place (initialement 0), et une classe "Classe" contenant la liste des élèves (une Arraylist<Eleve>).
Du coup t'as le nombre d'élèves par classe avec la méthode size(), et il sera facile par la suite d'ordonner les élèves si besoin.

C'est là que ça se complique. Le positionnement des élèves me pose problème.

La je suis d'accord . Pour que ça marche tout le temps c'est pas évident. Par exemple ton algo ne marche pas à chaque fois.
S'il y a 20 places, 10 éleves dans une classe et 5 dans les deux autres, tu peux pas faire modulo(3). Il faut faire modulo(2) et compléter les autres places en mettant les élèves des deux autres classes.. et des cas particuliers comme ça il doit y en avoir pas mal.


Si on a le nombre de places dans l'amphi, comment considère-t-on que deux places sont côtes à côtes?
Parce que considérer que deux places sont à côté si elles ont des numéros successifs, c'est plus simple mais plus contraignant. Par exemple si on a des rangées de 10 places, la place 11 n'est pas a côté de la place 10, et c'est dommage de ne pas s'en servir...

Donc selon moi si on veut résoudre tous les cas qui ont une solution il faudrait qu'on aie une "carte" des amphis...


Bref, du coup si on n'a effectivement que les infos que vous donnez (donc la liste des élèves, l'algorithme suivant devrait fonctionner :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
int numeroDePlace = 1 ;
Eleve theEleve1, theEleve2 ;
while (il existe un eleve qui n' pas d'emplacement)
{
  theEleve1 = prendre un élève (sans place) dans la classe ayant le plus d'élèves non placés.
  theEleve2 = prendre un élève (sans place) dans la seconde classe ayant le plus d'élèves non placés ; // permet d'assurer que deux élèves de la même classe ne se retrouvent pas côte à côte.
  theEleve.place = numeroDePlace++ ;
  theEleve.place = numeroDePlace++ ;
}

Donc du coup ma Classe "Classe" contiendrait deux liste : celles des élèves non placés et celle des élèves placées, mises à jour à chaque tour de boucle.
A priori cet algo marche dans tous les cas solvables ( pas de classe ayant plus de N/2 élèves pour un amphi de N places).

[druzy]

Amon avis, avec tu devrais faire une classe virtuelle comportant le nombre de place restant dans l'amphi. Ce sera plus facile de gérer les places vides.
Ensuite, ce que je ferais c'est de sélectionner la classe la plus grande, de placer un élève à la place 1, ensuite prendre la classe la plus grand en excluant la dernière classe placée, choisir un élève au hasard et le placer à la place 2, rechoisir la la classe la plus grande en excluant la dernier placée...

J'espère que tu vois l'idée.

[Mopmop]

Ensuite, ce que je ferais c'est de sélectionner la classe la plus grande, de placer un élève à la place 1, ensuite prendre la classe la plus grand en excluant la dernière classe placée, choisir un élève au hasard et le placer à la place 2, rechoisir la la classe la plus grande en excluant la dernier placée...

J'espère que tu vois l'idée.

Plagia, je demande des droits d'auteur

[shenz]

Bonjour,

Merci à vous d'essayer de me venir en aide.

Côte à côte veut dire deux numéros qui se suivent ? Ou il y a des subtilité genre les places juste devant et juste derrière sont considérées comme "à coté" ?

Effectivement j'étais parti sur les numéros qui se suivent, je n'avais pas pensé à cette subtilité du devant/derrière. Dans certains cas 2 élèves d'une même classe pourrait se retrouver effectivement l'un derrière l'autre. Et comme tu dis Mopmop, sans un plan de chaque amphi, ça devient impossible à gérer!

Donc restons pour l'exemple sur la considération que 2 élèves côte à côte correspondent à 2 numéros qui se suivent.

On part du principe que le problème peut être résolu ou il faut aussi vérifier ça ? Par exemple si on prend N le nombre de place, il ne faut pas de classe ayant plus de N/2 élèves... sauf si on prend en compte les rangs.

Je pense que je peux me débrouiller pour qu'on me fournisse le nombre de places par amphi, ce qui facilitera déjà certains points de vérifications pour mon code.

Je ne partirais pas comme ça. Autant utiliser les objets, pour que ça soit plus facile si besoin d'évolution (genre ordre alphabétique...)
Du coup je me ferais une classe "Eleve" contenant nom, prénom, numéro de place (initialement 0), et une classe "Classe" contenant la liste des élèves (une Arraylist<Eleve>).
Du coup t'as le nombre d'élèves par classe avec la méthode size(), et il sera facile par la suite d'ordonner les élèves si besoin

Effectivement, on est en java, donc autant utiliser les objets.
Je partirai donc de mon tableau de String[] récupéré lors de la lecture de mon csv.
Je fais ensuite une boucle sur ce tableau. En fonction de la taille de mon tableau je connais le nombre total d'élèves. Je pourrais donc déjà faire une 1ere vérification par rapport au nombre de places dans l'amphi. A chaque boucle je rempli donc ma classe "Eleve" (nom, prénom, classe, numéro de place) que je remet dans une liste d'<"Eleve"> comme tu le dis. On va dire que le numéro de la place sera à zéro si l'élève n'est pas encore placé.

prendre un élève (sans place) dans la classe ayant le plus d'élèves non placés.

Sauf que du coup il va me falloir un tableau par classe pour connaitre le nombre d'élèves non placés dans chaque classe et vérifier dans quelle classe, j'ai le plus d'Eleves non encore placés.
Le nombre de classe n'étant pas fixe pour chaque journée d'exam, je ne peux pas prédéfinir d'avance le nombre de tableaux/classes que j'aurai dans le code. D'où mon idée de départ avec la HasMap qui deviendrait avec ces nouveaux éléments une Map<NOM CLASSE, Arraylist<Eleve>>
En fonction du Eleve.getNomClasse, je peux rajouter un nouveau tableau dans ma Map ou ajouter un nouvel élève dans un tableau correspondant à une classe déjà connue.

Donc du coup ma Classe "Classe" contiendrait deux liste : celles des élèves non placés et celle des élèves placées, mises à jour à chaque tour de boucle.

Ok, pour cette idée, je complète chaque tableau au fur et à mesure, mais on n'a pas la notion de classe là dedans, seulement d'élève.

Dernier point par rapport à l'algo que tu proposes Mopmop, si je prends un exemple où j'ai 1 classe de 9 élèves , une classe de 15 élèves et une classe de 50 élèves.
Une fois que les 9 + 15 = 24 élèves des classes 1 et 2 sont placés. Il restera environ 25 élèves de la classe 3 à positionner. Tu ne peux donc plus, à partir de ce moment prendre le theEleve2 de ton algo, puisqu'il n'existe plus. Il faut donc pouvoir sauter une place à chaque fois dans ce cas là (c'est à dire faire le numeroDePlace++ sans l'affecter à un élève)

[Mopmop]

Effectivement, on est en java, donc autant utiliser les objets.
Je partirai donc de mon tableau de String[] récupéré lors de la lecture de mon csv.
Je fais ensuite une boucle sur ce tableau. En fonction de la taille de mon tableau je connais le nombre total d'élèves. Je pourrais donc déjà faire une 1ere vérification par rapport au nombre de places dans l'amphi. A chaque boucle je rempli donc ma classe "Eleve" (nom, prénom, classe, numéro de place) que je remet dans une liste d'<"Eleve"> comme tu le dis. On va dire que le numéro de la place sera à zéro si l'élève n'est pas encore placé.

Tu n'es pas obligé de garder la tableau de String[] et créer directement tes objets à la lecture du CVS...

Sauf que du coup il va me falloir un tableau par classe pour connaitre le nombre d'élèves non placés dans chaque classe et vérifier dans quelle classe, j'ai le plus d'Eleves non encore placés.

Exact, je proposais donc une ArrayList par classe. Je disais même deux ArrayList, une contenant les élèves placés et une contenant ceux non-placés histoire de garder les élèves placés dans un coin (sinon à la fin on risque d'avoir des problèmes lors de la sortie ).

Le nombre de classe n'étant pas fixe pour chaque journée d'exam, je ne peux pas prédéfinir d'avance le nombre de tableaux/classes que j'aurai dans le code. D'où mon idée de départ avec la HasMap qui deviendrait avec ces nouveaux éléments une Map<NOM CLASSE, Arraylist<Eleve>>
En fonction du Eleve.getNomClasse, je peux rajouter un nouveau tableau dans ma Map ou ajouter un nouvel élève dans un tableau correspondant à une classe déjà connue.

Oui effectivement il te faut une HashMap, mais tu n'es pas forcé de la faire comme ça. Tu peux faire une Map<NOM CLASSE, ObjetClasse> et donc en fonction du Eleve.getNomClasse, tu peux créer un nouvel objet "classe" ou ajouter un nouvel élève dans l'objet correspondant à une classe déjà connue.
D'ailleurs si on veut pouvoir séparer les élèves placés des autres, il faut deux listes et donc la HashMap<NOM CLASSE, Arraylist<Eleve>> ne suffit pas.

Ok, pour cette idée, je complète chaque tableau au fur et à mesure, mais on n'a pas la notion de classe là dedans, seulement d'élève.

Si, puisque les tableaux en question sont contenus par un objet "Classe".

Dernier point par rapport à l'algo que tu proposes Mopmop, si je prends un exemple où j'ai 1 classe de 9 élèves , une classe de 15 élèves et une classe de 50 élèves.
Une fois que les 9 + 15 = 24 élèves des classes 1 et 2 sont placés. Il restera environ 25 élèves de la classe 3 à positionner. Tu ne peux donc plus, à partir de ce moment prendre le theEleve2 de ton algo, puisqu'il n'existe plus. Il faut donc pouvoir sauter une place à chaque fois dans ce cas là (c'est à dire faire le numeroDePlace++ sans l'affecter à un élève)

Absolument c'est pas dur à faire mais il faut pas oublier ce détail (que j'avais as vu ).

Voilà voilà, bonne chance !

[hwoarang]

Salut,

Sans avoir réfléchi beaucoup au probleme, si on choisit de placer les eleves de la classe qui a le plus d'eleves à celle qui en a le moins. On cherche la premiere place vide. Puis on place les eleves de la classe en cours 1 place sur 2. Ensuite, on prend la classe avec le maximum d'eleve suivante. On a un placement optimal, non (au feeling, ca devrait meme permettre de trouver la taille minimum d'amphi pour caser tout le monde) ?

[Mopmop]

Salut,

Sans avoir réfléchi beaucoup au probleme, si on choisit de placer les eleves de la classe qui a le plus d'eleves à celle qui en a le moins. On cherche la premiere place vide. Puis on place les eleves de la classe en cours 1 place sur 2. Ensuite, on prend la classe avec le maximum d'eleve suivante. On a un placement optimal, non (au feeling, ca devrait meme permettre de trouver la taille minimum d'amphi pour caser tout le monde) ?

En effet, cet algo marche si tu connais le nombre de place dans l'amphi à l'avance, ce qui n'est pas le cas (ou du moins ce n'était pas le cas).

[benratti]

Il me semble que ce problème peut se rapporter facilement au problème de coloration des graphes.. problème que l'on sait résoudre :

http://fr.wikipedia.org/wiki/Coloration_de_graphe

Tes tables seront les sommets de ton graphe,
les tables voisines seront les aretes de ton graphe;
les étudiants seront les couleurs.

Il faudra surement adapter un peu l'algorithme car tu as des contraintes supplémentaires : le nombre de sommet par couleur t'es imposé... et tu auras potentiellement droit à une couleur supplémentaire qui est le nombre... par contre, comme tu ne connais pas le nombre de place de l'amphi, tu peux partir sur une approximation qui correspond au nombre total d'étudiant à placer.

[hwoarang]

En effet, cet algo marche si tu connais le nombre de place dans l'amphi à l'avance, ce qui n'est pas le cas (ou du moins ce n'était pas le cas).

Oui mais vu qu'il permet de determiner un optimum... Donc soit ca rentre, et on peut resoudre le probleme. Soit ca rentre pas et on peut pas résoudre. Et d'apres ce que j'ai compris, il n'y a pas de contrainte si l'amphi est tres grand. Autrement dit, si on n'utilise que 1/10 de l'amphi (en respectant les contraintes de placement bien sur), ce n'est pas un probleme. Donc je ne vois pas pourquoi chercher plus loin...

[Mopmop]

Oui mais vu qu'il permet de determiner un optimum... Donc soit ca rentre, et on peut resoudre le probleme. Soit ca rentre pas et on peut pas résoudre. Et d'apres ce que j'ai compris, il n'y a pas de contrainte si l'amphi est tres grand. Autrement dit, si on n'utilise que 1/10 de l'amphi (en respectant les contraintes de placement bien sur), ce n'est pas un probleme. Donc je ne vois pas pourquoi chercher plus loin...

Que nenni, ça détermine pas un optimum (mon algo oui par contre ). Donc je persiste et je signe, si on a pas a l'avance le nombre de places dans l'amphi, ton algo ne marche pas et il permet encore moins d'avoir un optimum.

[zo1odMSQr5Fy]

Il me semble que ce problème peut se rapporter facilement au problème de coloration des graphes.. problème que l'on sait résoudre :

http://fr.wikipedia.org/wiki/Coloration_de_graphe

Tes tables seront les sommets de ton graphe,
les tables voisines seront les aretes de ton graphe;
les étudiants seront les couleurs.

Il faudra surement adapter un peu l'algorithme car tu as des contraintes supplémentaires : le nombre de sommet par couleur t'es imposé... et tu auras potentiellement droit à une couleur supplémentaire qui est le nombre... par contre, comme tu ne connais pas le nombre de place de l'amphi, tu peux partir sur une approximation qui correspond au nombre total d'étudiant à placer.

Je le verrai plus comme chaque éléve un sommet avec comme poids pour le sommet le nombre d'éléve dans la classe. Tu peut placer un eleve a coter tant qu'il y a pas de liaison entre les eleves.Et quand tu peut pas tu met une place vide ( tu incrémentes un compteur dans ce cas ). A la fin quand tout est placé tu fait nombre d'éléve + place vide ! Tu obtiens le placement et le nombre de place minimum

[hwoarang]

Que nenni, ça détermine pas un optimum (mon algo oui par contre ). Donc je persiste et je signe, si on a pas a l'avance le nombre de places dans l'amphi, ton algo ne marche pas et il permet encore moins d'avoir un optimum.

Euh, après 30 secondes de reflexion, je vois pas la faille . Est ce que tu as un exemple ou mon algo ne trouve pas d'optimum (par optimum j'entends la taille minimal de l'amphi où tous les eleves sont placés sans en avoir 2 de la meme classe à coté) ?

[Mopmop]

Euh, après 30 secondes de reflexion, je vois pas la faille . Est ce que tu as un exemple ou mon algo ne trouve pas d'optimum (par optimum j'entends la taille minimal de l'amphi où tous les eleves sont placés sans en avoir 2 de la meme classe à coté) ?

Si on a pas le nombre de place dans l'amphi on ne sais pas quand recommencer à la première place libre.
Si on prend 3 classes de 10 élèves et un amphi de 30 places (mais on ne le sait pas) on va placer la première classe :
1..3..5..7..9..11..13..15..17..19......................
Pour la deuxième classe on continue donc ça donne :
1..3..5..7..9..11..13..15..17..1920..22..24..26..28..30 <= et là, problème ! Il faudrait retourner à la place 2 mais on ne le sait pas donc on va attribuer les places 32, 34 etc...


Du coup on pourrait se dire qu'il suffit de reprendre à la première place libre à chaque fois. Du coup ça donnerai :
1234567891011121314151617181920
Et là quand on veut placer la troisième classe on ne peut pas (que 30 places dans l'amphi).


Le truc bien dans ça c'est qu'en donnant un exemple, j'ai pensé à la solution pour rendre l'algo correct : il suffit d'y ajouter un test => quand le nombre d'élèves placés = nombre d'élèves restants à placer on repart à la première place libre... Avec ce test on a effectivement un optimum qui sera d'ailleurs trouvé plus rapidement qu'avec l'algo que j'ai proposé. En revanche le miens sépare mieux les élèves (plus d'écart entre 2 élèves d'une même classe)... question de choix, comme d'hab .

Par ailleurs si on veut la taille minimale de l'amphi nécessaire, on peut simplement calculer :
Max( (taille de la plus grande classe)*2 ; nombre d'élèves en tout )

[hwoarang]

Bien vu

[Jojo K-ri]

Le truc bien dans ça c'est qu'en donnant un exemple, j'ai pensé à la solution pour rendre l'algo correct : il suffit d'y ajouter un test => quand le nombre d'élèves placés = nombre d'élèves restants à placer on repart à la première place libre... Avec ce test on a effectivement un optimum qui sera d'ailleurs trouvé plus rapidement qu'avec l'algo que j'ai proposé.

bonjour
pourquoi tu penses que c'est cela plutôt que le MIN des deux classes?
Avec ta méthode si on a classeA = 40 élèves et classeB = 10 élèves
quand tu as placé 25 élèves de la classe A tu vas placer les 10 de la classe B si j'ai bien compris ta méthode
donc il va y avoir 15 élèves de ces 25 de la classe A seuls, plus les 15 autres qui ne sont pas encore placés

[Mopmop]

bonjour
pourquoi tu penses que c'est cela plutôt que le MIN des deux classes?
Avec ta méthode si on a classeA = 40 élèves et classeB = 10 élèves
quand tu as placé 25 élèves de la classe A tu vas placer les 10 de la classe B si j'ai bien compris ta méthode
donc il va y avoir 15 élèves de ces 25 de la classe A seuls, plus les 15 autres qui ne sont pas encore placés

Je suis pas certain d'avoir compris la question mais ça m'a montré une petite erreur sur le test que je proposais d'ajouter, qui devrait être "quand le nombre d'élèves placés = nombre d'élèves restants à placer ET si on est pas en train de placer les élèves de la première classe, alors on repart à la première place libre".

[benratti]

Je le verrai plus comme chaque éléve un sommet avec comme poids pour le sommet le nombre d'éléve dans la classe. Tu peut placer un eleve a coter tant qu'il y a pas de liaison entre les eleves.Et quand tu peut pas tu met une place vide ( tu incrémentes un compteur dans ce cas ). A la fin quand tout est placé tu fait nombre d'éléve + place vide ! Tu obtiens le placement et le nombre de place minimum

Sauf que dans ton cas, c'est un nouvel algo... c'est pas le problème de coloration de graphe.

Pour rappel du problème de coloration de graphe, c'est comment colorié un graphe avec un nombre de couleurs données en respectant la contrainte que deux sommets liés par une arête ne peuvent pas être de même couleurs.

[zo1odMSQr5Fy]

Sauf que dans ton cas, c'est un nouvel algo... c'est pas le problème de coloration de graphe.

Pour rappel du problème de coloration de graphe, c'est comment colorié un graphe avec un nombre de couleurs données en respectant la contrainte que deux sommets liés par une arête ne peuvent pas être de même couleurs.

En effet autant pour moi ! J'etait parti sur l'utilisation de la coloration de graphe mais je me suis égaré dans ma reflexion . Je me disais que chaque eleve pouvant être à coté on mettait une couleur. Genre A et C peuvent être à côté de B ben on coloriais A et C en bleu. Mais ce qui faisais qu'on pouvait exclure des personnes qui ne pouvait être à côté de A mais peuvent être à côté de C. C'est pour ça qu'une condition dans l'algo doit etre mis en plus , pour avoir un simili de coloration de graphe. Si A et C s'exclue (qu'il y a une liaison entre les deux) on les colories de la même maniére ( en gros ils sont de la même classe )