pl@ou812.univ-tln.fr : 12/14/22 --- travail personnel: requis utilisation du compte: libre commandes réseaux: interdites permission HOMEDIR : drwx------ Repondre aux questions directement dans l'enonce en utilisant des lignes de moins de 72 caracteres. Pour les sources, utiliser les noms de fichiers precises dans l'enonce. Les sources ne doivent pas contenir de commentaires, ni de codes inutiles. Tous les programmes, fichiers etc... devront etre places dans le repertoire d'examen : /home/pl/exam-tp-I51-2022-pl Vous validerez votre travail par la commande : /home/partage/pl/validexam -mI51 --- L'objectif de ce sujet est de faire un peu de zoologie sur les graphes de petit ordre et leur classification à isomorphisme près. Un makefile est proposé pour maintenir le répertoire d'examen à jour, il n'a pas à être modifié, tout comme les sources : classe.c, zoo.c etc. **** Les commandes test.exe et zoo.exe partagent le même jeu d'options. L'option -h fournit un aide succint, et l'option filtrage -f qui permet de sélectionner les graphes, est détaillée par l'option -F. @> ./test.exe -F abiche Filtre abiche GRAPHE: arbre bicolore, sans isolani, connexe, hamiltonien, eulerien **** Dans l'état, le graphe data/maison.dat ne passe pas le test -f i @> ./test.exe -f i -s data/maison.dat ko... mais il passe le test contraire -f ^i ( ou -f I ) @> ./test.exe -f ^i -s data/maison.dat OK ! **** Dans l'état, il ne peut pas passer le test -f b ( bicolore ) @> ./test.exe -f b -s data/maison.dat coloration.c:23 -> bicolore : corrigez le bug ! le message indique qu'il faudrait corriger la fonction bicolore qui se trouve dans le fichier coloration.c pour rendre le sélecteur b opérationnel. ----------------------------------------------------------------------- 0. AVANT MISE EN ROUTE ----------------------------------------------------------------------- La commande ./zoo.exe -n{val} génère tous les graphes d'ordre {val} à isomorphisme près pour un entier n < 9. Dans l'état, le programme affiche le nombre de classes d'isomorphie. Nous avons vu en cours qu'il y a 11 classes de graphe d'ordre 4 : @> ./zoo.exe -n4 Nombre de classes : 11 Nombre de solutions : 11 [ a ] Utiliser le script.sh pour compléter la table de valeurs : ordre : 1 2 3 4 5 6 7 classe : 1 2 4 11 ... ... ... [ b ] Utiliser la commande /usr/bin/time --format="%U" mesurer le temps de calcul : ordre : 1 2 3 4 5 6 7 temps : ... ... ... ... ... ... ... ======================================================================= 1. MISE EN ROUTE ======================================================================= [ a ] Préciser la nature de la représentation des graphes implantée dans le fichier de définition graphe.h. ... [ b ] Observer la fonction void isolani( graphe *g ). Que fait-elle ? ... [ c ] Compléter la fonction degre( int s, graphe * g) [ d ] La fonction int bicolore( graphe *g ) contient un bug. Lequel ? [ e ] Merci de le corriger. [ f ] Combien de classes de graphe d'ordre 5 sont sans cycle impair ? # NB : cycle impair = cycle de longueur impair ======================================================================= 1. CONNEXE ======================================================================= [ a ] Compléter la procédure parcours pour finaliser la mise en oeuvre de la fonction int connexe( graphe * g ) qui renvoie 1 si le graphe est connexe et 0 sinon. Il y a 6 classes de graphe connexe d'ordre 4 et 5 non connexes Utiliser les commande suivante pour tester votre implantation : ./zoo.exe -n4 -f c ./zoo.exe -n4 -f ^c [ b ] Ecrire un script connexe.sh pour compléter le tableau : ordre : 2 3 4 5 6 7 connexe : non connexe : [ c ] Que doit-on remarquer ? ======================================================================= 2. ARBRE ======================================================================= [ a ] Compléter la fonction arete( graphe * g) [ b ] La fonction int arbre( graphe * g) qui renvoie 1 si le graphe g est arbre et 0 sinon contient une erreur. Laquelle ? [ c ] Merci de la corriger ! [ d ] Que calcule la commande ./zoo.exe -n 7 -f a ? [ e ] Combien y a t-il de classe d'arbre d'ordre 7 ? ======================================================================= 3. COMPLEMENTAIRE ======================================================================= On rappelle que ij est une arête du complémentaire du graphe G si et seulement si ij n'est pas une arête de G. Lancer la commande : @> ./test.exe -s data/maison.dat -l home -d [ a ] Que fait la commande. Préciser le rôle des options utilisées : [ b ] Faire le schéma du complémentaire du graphe maison [ c ] implanter une fonction graphe complementaire( graphe * g ) qui calcule et renvoie le complémentaire du graphe g. # On note Cccc(n) le nombre de classe de graphe connexe dont le complémentaire est connexe, c'est le résultat de la commande Cccc(n) : @> ./zoo.exe -n4 -f c/c [ c] Ecrire un script complement.sh pour compléter le tableau : ordre : 2 3 4 5 6 7 Cccc(n) : ... [ d ] Donner un exemple générique de graphe connexe à complémentaire connexe pour l'ordre n > 3. ======================================================================= 4. ADJOINT ======================================================================= On rappelle que le graphe adjoint d'un graphe G est un graphe L(G) dont sommets sont les arêtes de reliées par la relation d'indicidence. graphe A graphe T 0 --- 1 --- 2 A ----- B | \ / | \ / 3 C [ a ] Compléter : L( A ) est isomorphe au graphe ... L( T ) est isomorphe au graphe ... [ b ] Compléter la fonction graphe adjoint( graphe * g ) pour retourner le graphe adjoint de g. ======================================================================= 5. EULERIEN ======================================================================= [ a ] Coder une fonction int eulerien( graphe * g ) qui retourne 1 si le graphe est eulerien et 0 sinon. [ b ] Ecrire un script eulerien.sh pour compléter le tableau: ordre : 2 3 4 5 6 7 E(n): # E(n) : nombre de classes de graphe Eulerien à l'ordre n Les graphes de type -f e:e/e : eulerien dont le complément et l'adjoint sont eulerien sont rares. Il n'en existe pas si l'ordre du graphe est 4 ou 6. Il en existe un seul d'ordre 5 : @> ./zoo.exe -n5 -t e:e/e [ c ] Identifiez le ! ======================================================================= 6. HAMILTONIEN ======================================================================= [ a ] Comment qualifier la technique algorithmique utilisée pour coder la fonction int hamiltonien( graphe * g ) ? ... [ b ] Elle contient un bug... Lequel? ... [ c ] Merci de le corriger ! [ d ] Ecrire un script hamilton.sh pour compléter le tableau ordre : 2 3 4 5 6 7 H(n) : ... # H(n) : nombre de classes de graphe hamiltonien à l'ordre n [ e ] Le résultat de ./zoo.exe -n6 -f e:^h illustre un résultat du cours, Lequel ? ... [ f ] Que suggère le résultat de : for i in {1..6}; do ./zoo.exe -n $i -f h:^h; done ... ======================================================================= 5. INVARIANT ======================================================================= On définit l'invariant invDegre d'un graphe G comme étant le tableau ordonné des valeurs des degrés des sommets d graphe G. Par exemple, le graphe maison contient : 1 sommet de degré 2, 2 sommets de degré 3 et 2 sommets de degré 4, son invariant est : [2, 3, 3, 4, 4 ] On note invDegre(G) l'invariant du graphe G. [ a ] Si G et G' sont isomorphe alors ... On dit qu'un tableau T est une collision quand il existe deux graphes non isomorphes G et G' tel que : T == invDegre(G) == invDegre(G') [ b ] Compléter la procédure void invariant( graphe *g ) pour instancier le champ g->inv à la laveur invDegre( G ) [ c ] Comment utiliser les commandes zoo.exe, sort, uniq et wc pour compter les collisions dans les graphes d'ordre 5 [ d ] Ecrire un collisions.sh pour compléter la table : ordre : 2 3 4 5 6 7 C(n) : 0 0 0 3 # C(n) : nombre de classes valeurs de collision l'ordre n ======================================================================= 6. ANALYSE classe.c ======================================================================= On considère un entier n, on note m := (n-1)*n/2. Une observation attentive du code classe.c montre la fonction classification effectue un parcours sur le graphe des graphes. [ a ] Préciser la nature de ce parcours : ... .... .... [ b ] Exprimer en fonction de m l'ordre N du graphe des graphes N := [ c ] chaque sommet du graphe parcouru est de degré : D := [ d ] Exprimer en fonction de m le nombre d'arête du graphe des graphes M := [ d ] Donner en fonction de m le temps de calcul d'un voisin t := [ e ] Estimer le temps de calcul d'une classification en fonction de n T( n ) = [ f ] Utiliser la commande /usr/bin/time --format="cpu=%U" pour mesurer le temps de calcul pour n = 8 : T( 8 ) = [ g ] Extrapoler le temps de calcul pour n = 9 T( 9 ) =