L3 Informatique I6S3 Graphes

Projet 2017 : Coloration gloutone itérée

Le sujet.

Inscription pour le projet : avant le 10 avril par mél, sujet "inscription projet graphes" et indiquer le binome. Après quelques jours, vérifiez que vous apparaissez sur le tableau ci-dessous.

Le rapport et la démonstration du projet :

• démos le mercredi 3 mai et jeudi 4 mai
• La démonstration dure 10 minutes: 5 minutes de présentation + 5 minutes de questions.
• Vous devez être prêt quelques minutes avant l'heure de passage (vérifiez que votre application fonctionne sur les PC de la salle auparavant !).
• synthèse de 4 pages maximum à rendre au moment de la soutenance et comprenant :
  • bref rappel de la problématique et des enjeux
  • structures et algorithmes mis en oeuvre (ne détailler que les plus pertinents)
  • résultats produits : réponses aux questions + tableau avec les valeurs trouvées en fonction de n et d (avec h et l fixés)
  • limitations de la version actuelle et possibilités d'extension/amélioration

Questions/Réponses :

Q : Faut-il un rendu visuel, lors de l’exécution du programme ?

R : Oui, rendu visuel possible mais non obligatoire. Ne pas passer trop de temps sur cette partie. Par contre un affichage permettant de vérifier que la coloration produite est bien propre et (m-équitable) est important.

Q : Est-ce qu'il est possible de le faire en C# ?

R : oui

Q : A t'on le droit d'adapté l'algorithme de coloration exact pour qu'il n'ai pas en paramètre un nombre précis de couleur mais qu'il en rajoute au besoin?

R : oui, du moment que le résultat produit est correct.

Q : auriez vous un intervalle de valeur à nous conseiller pour d et n (dans le graphe de disque) pour avoir un résultat cohérent?

R : il faut choisir les intervalles de façon à ce que les résultats soient intéressants, par ex : n = 5, 10, 50, 100 et d=100, 200, 400, 800

Q : Pour la création des voisins, est-ce qu'il faut faire avec les disques ou est-ce que l'on peut garder la méthode du TP3 (avec la probabilité) ?

R : Oui, le sujet est sur les graphes de disques, donc c'est mieux de reprendre leur construction (TP2), mais si c'est trop compliqué, vous pouvez garder les graphes aléatoires du TP3.

Q : Pour DSATUR équitable, est-ce que l'on part avec comme nombre de couleur le nombre de sommet ? (ce que je fais actuellement) Mon DSATUR fonctionne mais pour le DSATUR équitable je trie ma liste de couleur en mettant la moins utilisée devant, du coup j'obtiens une coloration à 1 utilisation pour chaque couleur. Est-ce qu'il s'agit du résultat attendu ou bien une erreur de ma part ?

R : Pour DSATUR équitable, il ne faut pas fixer un nombre de couleurs à l'avance, sinon cela biaise le comportement, comme vous avez pu le voir. A chaque fois qu'une nouvelle couleur est nécessaire pour colorier un sommet, elle devient donc plus prioritaire que les autres à l'itération suivante car un seul sommet l'utilise.

Q : Concernant le rapport vous avez parler de limitations de la version actuelle et possibilités d'extension/amélioration. pouvez-vous m'expliquer cela ? merci

R : Expliquez si vous êtes limités par les temps de calculs suivant la taille du graphe, ce que vous proposeriez de faire pour trouver plus efficacement une coloration équitable, etc