Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

UTBM
le 17 janvier 2005
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 d’algorithmes 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 nœuds !(5)a) Envous basant sur le parcours en profondeur, Ècrivez une fonction "cycle" permettant de vÈrifier qu’un graphe non orientÈ est sans cycle. L’exploration s’arrÍtera ‡ la dÈtection du premier cycle Vous utiliserez le TDA graphe. On suppose que le type sommet nous permet d’indicer 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. VarDÈbut Fin b) Ecrivezun prÈdicat "arbre" dÈterminant si un graphe est un arbre. Fonction BoolÈen arbre(Graphe g) ; VarDÈbut Fin ; 2) Articulations fÍlÈes ?(9)a) Dessinezl’arborescence de parcours en profondeur du graphe ci dessous avec point de dÈpart A. (L’ordre alphabÈtique dÈtermine l’ordre des successeurs d’un sommet.) NumÈrotez les sommets en fonction de leur ordre d’accËs Sur cette arborescence dessiner les arÍtes non utilisÈes en pointillÈs. G BC D E F Unpoint d’articulationdans un graphe connexe est un sommet dont la suppression dÈcompose le graphe en plusieurs composantes. Un graphe sans point d’articulation est dit2connexeou biconnexe. En d’autres termes, un graphe 2connexe prÈsente pour chaque couple de sommets deux chaÓnes disjointes adjacentes, donc reliant les deux sommets. Le graphe cidessus n’est pas 2connexe. Le point B est un point d’articulation. La composante { A, B E, F, G, H } est 2 connexe. Le point B est doncpoint d’articulationcar 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 l’algorithme de parcours, dÈfinissez une fonction "point_articulation" qui explore le graphe et dÈterminer les points d’articulation d’un 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 d’articulation.
Lo42  final A2004  page1/2