EXAMEN de TRAVAUX PRATIQUES THEORIE ALGORITHMIQUE DES GRAPHES 13 decembre 2021 Conformément à l'usage, on note n(G) le nombre de sommets du graphe G, m(G) le nombre de ses arêtes et p(G) le nombre de composantes connexes. On rappelle qu'un cycle dans un graphe non orienté est un chemin fermé simple, c'est-à-dire ne passant pas deux fois par une même arête. En particulier, un cycle est de longueur > 2. ======================================================================== 0. Répondre aux questions suivantes ======================================================================== [ P0 ] Un graphe sans cycle est dit cyclique. Connaissez vous une autre terminologie ? LAQUELLE [ P1 ] Un graphe connexe est un arbre si et seulement n(G) = m(G) + 1 VRAI FAUX [ P2 ] Un graphe possede un cycle si et seulement si une de ces composante connexe n'est pas un arbre. VRAI FAUX [ P3 ] Un graphe est acyclique si et seulement si une n(G) = m(P) + p(G) VRAI FAUX ======================================================================== 1. statistiques sur les composantes connexes : fichier -> connexe.{ch} ======================================================================== [a] Dans le fichier connexe.c, coder une fonction void stats( graphe g ) qui liste les statistiques sur les composantes connexes du graphe g : pour chaque composante, il s'agit d'afficher : un numero, un élément de la composante, la taille de la composante et le nombres d'arêtes de ses arêtes. L'affichage prendra la forme d'un tableau à 4 colonnes. [b] Comment décider de l'existence d'un cycle dans un graphe sur la base des statistiques de ses composantes connexes ? [c] Coder une fonction int cycle( graphe g ) qui le numéro d'un sommet représentant une composante connexe contenant un cycle. Dans le cas d'un graphe acyclique, la valeur de retour doit être -1. ======================================================================== FUSION( G : graphe ) debut n := ordre( G ) initialiser une structure de n ensembles disjoints pour chaque arete uv de G si representant( u ) != representant( v ) alors reunion( u, v ); // comptage sinon // fsi fin fin ======================================================================== ======================================================================== 2. Détection de cycle : fichiers requis -> disjoint.{ch} detection.c ======================================================================== [a] Expliquer commment l'algorithme FUSION( G ) peut être utilisé pour détecter la présence d'un cycle dans le graphe G. [b] Coder une fonction int detect( int *i, int*j, graphe g ) qui renvoie 1 si le graphe posssède un cycle, 0 sinon. Les arguments i et j, seront utilisés pour passer les extrémités d'une arête de cycle. [c] Préciser le temps de calcul dans le meilleur des cas. [d] Préciser le temps de calcul dans le pire des cas. ======================================================================== 3. backtracking sur l'échiquier : fichiers requis -> varan.c ======================================================================== Un virus venu d'Indonésie a produit quelques mutations sur les pièces du jeu d'échecs. Le varan est des pièces mutantes qui se déplace comme un cavalier et une tour. Pour un échiquier nxn, on note V(n) le nombre de configurations de n varans sans conrôle mutuel. [a] Combien de cases sont controlées par un varan sur un coin de l'échiquier [b] Et au centre d'un échiquier nxn ? [c] Coder une source varanc.c pour une commande varan.exe qui prend un entier sur la ligne de commande pour déterminer et afficher la valeur de V(n). [d] Préciser les valeurs de V(n) pour 1 <= n <= 8. [e] Une formule pour V(n) ? ======================================================================== 4. challenge numérique : fichiers requis -> komodo.c ======================================================================== Il s'agit de coder une version optimisée pour le problème des varans. [a] Coder une source komodo.c pour une commande komodo.exe qui prend un entier sur la ligne de commande pour déterminer et afficher la valeur de V(n). [b] Utiliser la commande /usr/bin/time pour comparer les performances des commande varan.exe et komodo.exe