[PDF] [PDF] 1 Parcours en profondeur 2 Tri topologique

View - Download [PDF] 1 Parcours en profondeur 2 Tri topologique

Previous PDF

Next PDF

Année 2019-20

Diplôme Inter-Universitaire

Enseigner l"informatique au lycée

Bloc 5 : TP 3

Parcours de graphes1 Parcours en profondeur

On se donne l"implémentation récursive suivante du parcours en profondeur à partir d"un sommets.

def parcours_profo ndeur (G, s) : """ Renvoie la liste du parcours en profondeur du graphe G représenté par sa liste d"adjacence (dictionnaire), à partir du sommet s : exploration restreinte à la partie accessible à partir de s """ sommets_visites def parcours_somme t (u): if u not in somm ets_visites: sommets_visites append(u) for x in

G [u]:

parcours_sommet(x) parcours_sommet(s) return sommets_vis ites

Question 1Appliquer l"algorithme à un graphe non connexe (tel qu"il existe deux sommets non reliés par

un chemin), à partir de différents sommets, pour vérifier les listes de parcours renvoyées.

Question 2Justifier qu"à tout moment de l"exécution de l"algorithme de parcours en profondeur, la pile

d"appels des arguments de la fonctionparcours_sommetforme un chemin desau sommetx, le dernier sommet sur lequel on a appelé la fonction récursivement.

Question 3Quelle est la complexité dans le pire des cas de l"algorithme de parcours en profondeur précé-

dent?

Question 4Comment modifier l"algorithme afin qu"il ait une complexité linéaire en le nombre d"arcs et le

nombre de sommets du graphe?

Question 5Comment modifier à nouveau le programme afin qu"il parcourt la totalité du graphe, même si

celui-ci est non connexe? En particulier, on cherche à écrire une nouvelle fonctionparcours_profondeurqui

renvoie une liste de sommetsLqui vérifie les propriétés suivantes : c haquesommet de Sapparaît une fois et une seule dansL;

c haquesommet de la li ste(sa ufle premie r)app artientà la fron tièredu sous-ensem blede sommet splacé s

avant lui dans la liste, si toutefois cette frontière est non vide. (On rappelle que la frontière d"un ensemble

de sommetsTSest l"ensemble des sommetss2SnTqui sont adjacents à au moins un sommet de T) L"algorithme ainsi modifié porte souvent le nom deparcours itéré...

2 Tri topologique

Étant donné un graphe orienté acycliqueG(c"est-à-dire qui ne possède pas de cycle), on veut trouver un

ordre linéaire total des sommets deG(autrement dit, on veut numéroter les sommets de1àn, ce qui définit

une relation d"ordre total,u < vsi l"indice deuest plus petit que l"indice dev), tel que cet ordre vérifie la

propriété : pour tout arc(u;v)deG,u < v

Ce tri permet d"ordonnancer des tâches à effectuer en présence de contrainte de précédence, du type la tâche

A doit être faite avant la tâche B. C"est typiquement le cas lors de la compilation de projets avec plusieurs

fichiers qui dépendent les uns des autres,makepar exemple utilise un tri topologique pour décider de l"ordre de

compilation.

Question 6Montrer que si le graphe comporte un cycle, un tel ordre n"existe pas. Ceci explique pourquoi

une compilation peut échouer avec un message d"erreur contenant les termesdépendance cyclique. Ce message

indique la présence d"un cycle dans le graphe de dépendance.

Question 7Ordonner le graphe suivant.Cetrip ermetd"ord onnancerdestˆaches`a effectuerenpr´esence decontr aintedepr´ec´edence,

dutype latˆacheAdoit ˆetref aiteavantlatˆache B.C "esttypiq uementlecaslorsd elacompilation deproj etsavecplusieursfichi ersquid´epen dentlesunsdesautres,makeparexem pleutiliseuntri topologiquepourd´eciderde l"ordredec ompilation. L"algorithmeutilis´eestunsim pleparcoursenprofondeur.Onu tiliseun eliste pourcontenirles sommetstri´es,init ialementvide.Chaquesomm etuestins´er ´edanslalisted`esquetousl esappels

r´ecursifssurlesarcssortantsdeusonttermin ´es.Demani`ere´equivalenteuestin s´er´ed`esqueua

´et´evisit´eet quetoussesvoisinssortant ssontin s´er´es.S "ilreste `alafinuns ommetnon-parcouru,

onre lanceleparcoursenprof ondeurd epuiscesommet,jusqu "`ace quetouslessommetssoient parcourus.Lalistefinaledonnel "ord re. (a)Montrerquesilegraphec omporteunc ycle,u ntelord ren"existep as. (b)Ordonnerlegraphesuivant. a b c d e f g h ij k l m (c)Donnerenpseudoco delafon ctiontritopologique. (d)Quelleestlacomplexi t´edecet algorithm e? (e)Quepeut-on diredel"ordretopologiq ue,parrapport`a l"arbre duparcoursenprofondeu r? Exercice5(Nombredetristopol ogiques) SoitClegraphe orient´edesomm ets{a,b,c,d,e}et d"arcs{ ab, ac, be, cd, de}.En um´erertouslestristopologiquesd ecegraphe. Exercice6(Pluslongschemins dansungraph eacyclique)Onveutcalcul erlalongue urd"un plus longchemin orient´edansungrapheor ient´eacycliqueG.Soi tv 1 ,v 2 ,...,v n untrit opologiquedes sommetsdeG.Pou rtoutsommet v i soitl(v i )la longueur d"unpluslongchemin arrivantenv i et soitπ(v i )le voisind ev i surcechemi n. (a)Donneruneformuled er´ecurr encepourcalculerl(v i )etπ(v i (b)Donnerenpseudo-co del"algor ithmedecalculd"unpluslongchemi n? (c)Quelleestsacomplexi t´e? Exercice7(Planificationdetravaux)Pourr´enove runem aison,ilestpr´evuderefai rel"inst allation ´electrique(3jours),der´eam´enager(5 jours) etdecarreler(2jours) lasall edebains,derefaire leparqu etdelasalledes´ejou r(6jour s)etd erepeindrele schambr es(3jours),lapeint ureetl e carrelagenedevantˆetr efaitsq u"apr`esr´efacti ondel"installation´ electrique.

(a)Silepr opri´et aired´ecidedetoutfairelui-mˆeme,dans quelordredoit-ilproc´e der?Q uelle

estladur´ eedest ravaux? (b)Silar´ enovat ionestfaiteparuneentrepriseet quechacune destˆacheses taccompl ieparun employ´edi ff ´erent,quelleestladu r´eeminimaledestra vaux?

2Question 8Expliquer pourquoi un grapheGpossède un cycle si et seulement si à un moment de l"exécution

de l"algorithme de parcours itéré en profondeur, le chemin d"appel possède un cycle. Question 9En déduire un algorithme produisant un tri topologique s"il en existe un. Question 10Quelle est la complexité de cet algorithme?

Question 11Que peut-on dire de l"ordre topologique, par rapport à l"arborescence de parcours en profon-

deur? Question 12SoitCle graphe orienté de sommetsfa;b;c;d;eget d"arcsf(a;b);(a;c);(b;e));(c;d);(d;e)g. Enumérer tous les tris topologiques de ce graphe.

3 Parcours en largeur

On cherche à implémenter un parcours en largeur d"un graphe. Pour cela, on se rappelle qu"il s"agit d"un

parcours générique dans lequel on choisit le sommet de la bordure à l"aide d"une file.

Question 13Utiliser une classe implémentant une file pour écrire une fonction Python réalisant un parcours

en largeur d"un graphe à partir d"un de ses sommets, en se limitant aux sommets accessibles depuis ce sommet

initial.

Question 14Sachant qu"un parcours en profondeur peut être implémenté à partir du parcours générique

en choisissant le sommet de la frontière à l"aide d"une pile, en déduire une implémentation non récursive du

parcours en profondeur d"un graphe à partir d"un sommet. 2quotesdbs_dbs16.pdfusesText_22

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf

[PDF] cornière catnic

[PDF] corniere galva pour brique

[PDF] corniere pour linteau brique

[PDF] cornière support briques