trouver un coloriage optimal de graphe c'est NPC yup
Mais certains graphes comme les DAG et les graphes complets on sait les colorier optimalement
L'idée de base était très simple : à partir d'un graphe quelconque générer un DAG correspondant et un complet correspondant puis ajouter/retirer des arêtes en maintenant un coloriage optimal à partir du coloriage optimal précédent et en comparant les deux états des graphes
Evidemment ça ne marche pas
Mais certains graphes comme les DAG et les graphes complets on sait les colorier optimalement
L'idée de base était très simple : à partir d'un graphe quelconque générer un DAG correspondant et un complet correspondant puis ajouter/retirer des arêtes en maintenant un coloriage optimal à partir du coloriage optimal précédent et en comparant les deux états des graphes
Evidemment ça ne marche pas
Je vois l'idée, et en vrai je vois pas pk ça pourrait pas marcher, vu que j'imagine que chaque étape doit avoir un temps de calcul proportionnel à n² (nombres de connections possibles entre n sommets), et qu'à la fin t'as un nombre relativement limité d'étapes
C'est de trouver les arrêtes à ajouter/retirer qui pose problème ?
C'est de trouver les arrêtes à ajouter/retirer qui pose problème ?
hihihi tu es aussi une pitite fofolle
Pardon?
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
Franchement ça je dirais pas non si tu partages
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
Le fameux 0 tout désiré
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
C'est aussi ce que je me disais si jamais
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
Pardon?
Non rien hihihi 
Non rien hihihi
Hihihi bahahah
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
Ca compte plus que tout
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
AHIIIIIIIIII
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
Je vois l'idée, et en vrai je vois pas pk ça pourrait pas marcher, vu que j'imagine que chaque étape doit avoir un temps de calcul proportionnel à n² (nombres de connections possibles entre n sommets), et qu'à la fin t'as un nombre relativement limité d'étapes
C'est de trouver les arrêtes à ajouter/retirer qui pose problème ?
C'est de trouver les arrêtes à ajouter/retirer qui pose problème ?
réduire le graphe en DAG est calculatoirement super simple (enfin, en ensemble de DAG plutôt pour conserver les infos )
Le problème c'est effectivement qu'à l'ajout d'arête on tombe sur un problème apparemment sous exponentiel et pas spécialement meilleur que les sous expo déjà connues donc RIP BOZO
Mais c'était amusant
Et sur ce, je go me préparer car contrairement à Oib qui ne jure que par les MPs je traine plutôt avec des gens IRL, peace out girl scouts
Le problème c'est effectivement qu'à l'ajout d'arête on tombe sur un problème apparemment sous exponentiel et pas spécialement meilleur que les sous expo déjà connues donc RIP BOZO
Mais c'était amusant
Et sur ce, je go me préparer car contrairement à Oib qui ne jure que par les MPs je traine plutôt avec des gens IRL, peace out girl scouts
I live inside my own world of make-believe
Hihihi bahahah
hihihi
Je re en urgence mes ptites fraizent
Gardez mémoire de moi, non point tel que j’ai failli, mais tel que j’étais.
ahiii le topic à 288 pages !
Ayaaaa il y a Corpsbeau et xox
blague à part though j'avais réduit le problème P=NP à l'ajout d'une arête dans un graphe qu'on sait optimalement colorié
c'était fun
c'était fun
Bordel ce gros cerveau 
le GOAT
C'est aussi ce que je me disais si jamais
Ca ne m'étonne pas de l'illustre et incorruptible Johnou_Ingram
Rav t'es belge aussi?!
Rav t'es belge aussi?!
Tiens en parlant de belges, tu connais l'expression "à côté de (élément A), (élément B) c'est du pipi de chat" ?
Je sais pas si c'est ma meuf qui est conne ou tous les belges
Je sais pas si c'est ma meuf qui est conne ou tous les belges