Final LO42 Les documents de cours et TD sont autorisÈs (La copie ou les idÈes du voisin non). Le barËme est indicatif. Le soin donnÈ ‡ la rÈdaction sera ÈvaluÈ. Toute rÈponse devra Ítre claire et justifiÈe (toute ambiguÔtÈ sera mal interprÈtÈe). En fonction des propriÈtÈs des objets manipulÈs, vous choisirez lasolution la plus efficaceen terme de complexitÈ. Sauf indication contraire, dans le cas dalgorithmes les rÈponses doivent Ítre rÈdigÈes en pseudo code. Les questions bonus Èventuelles ne sont ‡ traitÈes que si le reste est traitÈ convenablement.. 1) Arbre ou sac de nuds !(5)a) Envous basant sur le parcours en profondeur, Ècrivez une fonction "cycle" permettant de vÈrifier quun graphe non orientÈ est sans cycle. Lexploration sarrÍtera ‡ la dÈtection du premier cycle Vous utiliserez le TDA graphe. On suppose que le type sommet nous permet dindicer un tableau. Type sommet = [1..nMax] ; Fonction BoolÈen cycle(sommet s ; Graphe g ; Var BoolÈen M[1..n] ;…) ; // vous pouvez complÈter la liste de paramËtres si nÈcessaire. Var…DÈbut …Fin b) Ecrivezun prÈdicat "arbre" dÈterminant si un graphe est un arbre. Fonction BoolÈen arbre(Graphe g) ; Var…DÈbut …Fin ; 2) Articulations fÍlÈes ?(9)a) Dessinezlarborescence de parcours en profondeur du graphe ci dessous avec point de dÈpart A. (Lordre alphabÈtique dÈtermine lordre des successeurs dun sommet.) NumÈrotez les sommets en fonction de leur ordre daccËs Sur cette arborescence dessiner les arÍtes non utilisÈes en pointillÈs. G BC D E F Unpoint darticulationdans un graphe connexe est un sommet dont la suppression dÈcompose le graphe en plusieurs composantes. Un graphe sans point darticulation est dit2connexeou biconnexe. En dautres termes, un graphe 2connexe prÈsente pour chaque couple de sommets deux chaÓnes disjointes adjacentes, donc reliant les deux sommets. Le graphe cidessus nest pas 2connexe. Le point B est un point darticulation. La composante { A, B E, F, G, H } est 2 connexe. Le point B est doncpoint darticulationcar il a comme Ègalement comme descendants C et D. b) EnÈtudiant les arÍtes non utilisÈes, dites ce qui caractÈrise lesdescendants { C, D}par rapport aux descendants { E, F, G }. En vous basant sur lalgorithme de parcours, dÈfinissez une fonction "point_articulation" qui explore le graphe et dÈterminer les points darticulation dun graphe. Elle reÁoit en paramËtre un graphe, un sommet du graphe, un compteur de parcours, un tableau de marquage des sommets et un tableau permettant de noter les sommets comme point darticulation.
Lo42 final A2004 page1/2
UTBM
le 17 janvier 2005
fonction entier point_articulation (sommet s ; Graphe g ;Varentier compteur ;Varentier M[1..n],VarBoolÈen art[1..n] ;…) ; Var…DÈbut …Fin c) Dessinezlarborescence de parcours en profondeur du graphe avec point de dÈpart B. A nest pas un point darticulation, B en est un. Que pouvezvous dire de la structure des deux arborescences au niveau des racines ? Connaissant le numÈro de la racine et en analysant la numÈrotation des sommets ‡ lexploration du premier successeur et des successeurs suivants, Ècrivez une fonction "point_articulation2", basÈe sur lalgorithme de la prÈcÈdente, pour donner la bonne information sur le sommet de dÈpart fonction entier point_articulation2 (sommet s ; Graphe g ; Var entier compteur ; Var entier M[1..n] ; VarBoolÈen art[1..n] ;…) ; Var…DÈbut …Fin d) Ecrivezun prÈdicat "biconnexe" qui reÁoit en paramËtre un graphe et retournant soit la valeur boolÈenne vrai si le graphe est 2connexe, soit la valeur faux. e) Ecrivezune fonction "point_articulation3" en modifiant lalgorithme de la fonction "point_articulation2" pour interrompre lexploration dËs la dÈtection dun point darticulation.(question bonus)3) Ilest parfait Monceau ?(6) Un arbremonceauuds ‡ deux fils et dont toutes lesest un arbre binaire dont tous les ÈlÈments sont soit des feuilles soit des n Ètiquettes des fils dun nud ont des valeurs infÈrieures ‡ la valeur de lÈtiquette du nud. Utilisez limplantation dispersÈe avec les types suivants : Type Ab= ^noeud ; noeud= structure dÈbut Telementinfo ; Abg, d ; Fin; a) Ecrivezune fonction permettant de contrÙler si un arbre binaire transmis en paramËtre est un arbre vÈrifiant la premiËre propriÈtÈ ÈnoncÈe cidessus. Chaque nud doit Ítre visitÈ une seule fois. b) Modifiezvotre fonction pour vÈrifier que larbre est monceau ou non. Le parcours doit rester unitaire c) Quellessont les diffÈrences entre un arbre monceau et un tas ou tournois parfait ? Rappelez limplÈmentation de la hauteur dun arbre binaire. Utilisez cette fonction pour vÈrifier quun arbre est parfait. d) Imaginezune solution pour tester si un arbre est parfait en un seul parcours de chaque nud.(question bonus)