L3 Informatique I6S3 Graphes

Projet 2020 : Dégénérescence des grands graphes réels

Le sujet.

Inscription pour le projet : avant le 7 avril par mél, sujet "inscription projet graphes" et indiquer le binome et les contraintes horaires s'il y en a. Après quelques jours, vérifiez que vous apparaissez sur le tableau ci-dessous.

Le rapport et la démonstration du projet :

• 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 : par exemple sous forme de tableau avec les valeurs trouvées
  • limitations de la version actuelle et possibilités d'extension/amélioration

Questions/Réponses :

Q : je ne sais pas comment tester si mon implémentation de l'algorithme de dégénérescence est juste. Je trouve la même chose que pour le graphe donné dans le sujet cependant lorsque je test sur d'autres graphes je n'ai aucun moyen de vérifier.

R : Vous pouvez tester à la main sur des petits graphes (par exemple sur un graphe régulier de degré r, la degenerescence est r, sur un arbre c'est 1). Sinon sur les plus grands graphes présents dans les bases, la degenerescence est parfois connue et indiquée (elle apparaît sous le nom de "K-core number"

Q : J'ai choisi d'afficher les centres sous forme de cercles. Ne sachant pas quelle bibliothèque choisir pour la création de PDF j'ai décidé de générer un fichier Postscript. Êtes-vous d'accord avec cela ?

R : OK pour le postscript, vous avez ensuite des commandes sous Linux comme ps2pdf qui font le changement de format.

Q : dans l’algorithme pour calculer la dégénérescence des graphes, le premier algo donné dans l'énoncé, dis simple, ne me donne pas les même numéro de centre pour un même point comparé a l'algo de Matula Beck (celui que l'on doit reproduire pour la question 3.a) et avec une distribution qui n'a rien a voir entre les 2. Nous obtenons cependant le même k max qui correspond à la dégénérescence du graphe. Est-ce normal ?

R : Oui normalement les deux algorithmes doivent donner le même numéro de centre pour chaque sommet. L'algorithme de Matula et Beck étant juste une version optimisée pour le temps d'exécution. Il doit y avoir une parte d'un des algos que vous avez mal interprétée.

Q : Quand vous demandez de faire une fonction qui crée le graphe G, dans un fichier KONNECT ou SNAP, comment peut-on mettre le graphe dans ces type de fichier ?

R : Je pense que vous prenez la question à l'envers : je demande d'écrire une fonction qui va aller lire un fichier (après l'avoir téléchargé) dans lequel est stocké un graphe au format SNAP ou KONECT et va remplir une structure pour coder le graphe (matrice d'adjacence ou liste de voisin ou autre).

Q : le graphe pour lequel on doit calculer la dégénérescence et le numéro des centres doit-il être aléatoire ou prend-on le graphe que vous avez donné en exemple ( ou doit-on construire un graphe par nous-même ) ?

R : vous pouvez essayer sur plusieurs graphes, dont celui de l'énoncé. Ensuite on vous demande de tester sur des graphes des bases SNAP ou Konect mais vous pouvez aussi tester sur des graphes aléatoires si vous le souhaitez.

Q : sur l'option b du projet de graphe, il est demandé d'utiliser un algorithme de coloration glouton sur les sommets, ordonnés selon leur centre. Cela signifie-t-il qu'il faut utiliser DSATUR comme algorithme en initialisant le tableau DSAT avec le centre de chaque point ?

R : c'est plus simple puisque je propose un ordre fixe pour colorier les sommets, uniquement basé sur leur centre : d'abord les sommets de centre k, ensuite ceux de centre k-1, etc jusqu'au plus petit centre ; k étant la dégénérescence du graphe.