UTBM theorie de la programmation tda et structures de donnees 2004 gi

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 la solution la plus efficace en 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) En vous 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. Var … Début … Fin b) Ecrivez un 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) Dessinez l’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 ...