Projet universitaire de résolution mathématique du problème de K-Coloration d'un graphe donné dans l'UE Sécurité et Aide à la Décision en L2 Informatique à l'Université de Caen Normandie.
Le but du projet est de déterminer le nombre mamimum de couleurs, de façon optimale, pouvant colorer un graphe (dans le fichier graph.dimacs) en respectant une contrainte, il ne faut pas que les couleurs de 2 noeuds reliés soient les mêmes.
L'autre but était de faire cela avec l'API d'un outil, lp_solve. Cet outil permet de faire de la programmation linéaire afin de résoudre des problèmes mathématiques comme des problèmes d'optimisation et de maximisation de certaines valeurs. Lien vers l'API.
Pour Windows : Rendez-vous sur ce site afin d'installer la version développeur de lp_solve. Sans cela, il vous sera impossible d'utiliser l'API de lp_solve.
Pour MacOS et Linux: Exécutez la commande suivante :
sudo apt install liblpsolve55-devVous pouvez exécuter le script avec cette commande :
g++ main.cpp -llpsolve55 -lcolamd -ldl -o exePour modifier le graphe, veuillez modifier le fichier graph.dimacs en respectant les règles d'écriture.