bonjour,

je ne sais pas si c'est le bon endroits (forum de math ou informatique) pour ça.

le début du week-end j'ai vue une vidéo sur le problème p=np. donc j'ai décider de faire une petit programme en c pour la coloration de graphe.

donc je l'ai fini, je l'ai test, j'ai l'impression que ca marche (il trouve bien  la configuration minimal de couleur entre [1;+inf]).

j'ai l'impression que le nombre d'étape est de  aX^2+bX+c (est ce qu'il y a une personne pour vérifier que c'est exacte?) tel que a,b,c ap N et X le nombre de node.

désoler le code est moche mais je trouve que c'est plus facile de compte les étape d'exécution de code comme ca, désoler j'ai pas l'habitude de commentée le code aussi.

voici le code source (.c) avec l'exécutable et des exemple

https://github.com/nicolas745/graphe-chromatique/

le fichier pour résolution c'est : \code source\colorgraph.c

pour exécute le code le programme dans le cmd " prog.exe test.json" (dans le terminal, les couleur sont défini par des chiffre)

 fichier test.json : [[2],[1,4,6],[4],[2],[6],[3]] 

pour le fichier json il faut mettre sur une seul ligne car si il y a des multiligne il risque de d'avoir des bug si il y a trop de ligne (sauf si vous utiliser https://github.com/udp/json-builder pour le créer).

la procédure que j'ai suivie pour crée le programme

pour le premier node, on prend un node random puis on défini une couleur

la boucle commence

on va prendre une node avec une préférence il faut minimum 2 node de couleur adjacent. et c'est interdis de prendre des Node isoler. (on a le droit prendre node qui possède 1 couleur adjacent si il reste que ça).

puis défini sa une couleur

fin de la boucle si il n'y a plus de node sans couleur

merci, d'avoir tout lue même , il y a beaucoup de faut d'orthographe. Désoler je suis dyslexique 

-
Edité par NicolasBlanc25 11 janvier 2021 à 11:11:39

Bonjour

Comme tu décris ton algorithme, tu a quelque chose qui colorie un graphe, pas quelque chose qui trouve le nombre minimal de couleurs pour colorier un graphe. Colorier un graphe n'est pas un problème dans NP (il est effectivement dans P). Un problème NP complet est de décider pour un entier C>2 et un graphe quelconque G si G peut se colorier (ou non) avec C couleur. Un problème NP difficile sera de déterminer le plus petit C pour lequel G reste coloriable.

-
Edité par NicolasBlanc25 11 janvier 2021 à 11:19:31