[PDF] SUJET + CORRIGE PDF corrige.pdf

SUJET + CORRIGE Exercice 1: Graphes pondérés (b) (2 points) Donnez un exemple d'un graphe orienté pondéré G = (S, A), Propriété : Un graphe non orienté G(S, A) est connexe si pour n'importe quel sommet s ∈ S, l'exécution

Ces excursions sont résumées sur le graphe ci-dessous dont les sommets trace de recherche même incomplète ou d'initiative même non fructueuse sera prise en de deux sommets A et B origines et extrémités de deux arètes orientées et

[PDF] ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES

Exercice 16 (o) Essayez de construire un graphe non orienté ayant au moins deux sommets et tel que tous les sommets ont des degrés distincts Qu'

[PDF] Introduction à la théorie des graphes Solutions des exercices

1 Graphes non orientés établi dans l'exercice 7, un tel graphe doit posséder un nombre pair de sommets, le réseau Corrigé en partant du sommet 3 :

[PDF] TD no 1

Exercice 8 Un sommet x d'un graphe non orienté connexe G est dit point d' articulation de G si G−x est non connexe Corrigé du TD no 1 Généralités sur les

[PDF] graphes

1 4 corrigés exercices 2 4 corrigés exercices définition 2 : (matrice d' adjacence d'un graphe non orienté ) quel que soit le graphe non orienté G à n

[PDF] Optimisation Combinatoire et Graphes Exercices et Solutions

30 avr 2018 · GRAPHES NON ORIENTÉS Exercice 21 Dans un graphe G, soient s et t deux sommets distincts Montrer qu'il existe une (s, t)-chaîne dans G

[PDF] Exercice sur les Graphes - Moodle INSA Rouen

(Exercices et problèmes résolus de recherche opérationnelle, Dunod) dont les 1) En considérant le graphe comme non orienté, donner une chaîne de A à F

[PDF] Corrigé des exercices

Corrigé des exercices • Combinatoire des graphes £ ¢ ¡ Exercice 1 a) Soit G = (V,E) un graphe non orienté simple Notons V1 l'ensemble des sommets de

[PDF] Exercices

La théorie des graphes est rarement abordée en France dans le cursus Ci- après, la matrice M est associée à un graphe orienté G qu'on représentera chercher dans la liste des sommets le premier sommet non coloré et le colorer avec la

[PDF] SUJET + CORRIGE

PARCOURS :Master 1

UE J1BS8203 :Méthodes et outils pour la biologie des systèmes

Épreuve :Examen

Date :Lundi 8 avril 2013

Heure :10 heures

Durée :2 heures

Documents : autorisés

Épreuve de M. AlainGriffaultSUJET + CORRIGE

Avertissement

La plupart des questions son tindép endantes.

L"espace laissé p ourles rép onsesest suffi- sant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement déconseillé).

Solutions en langage algorithmique o uen Py-

thon.QuestionPointsScore

Graphes pondérés6

Plus longue sous-séquence commune9

Parcours en largeur5

Total:20

Exercice 1: Graphes pondérés (6 points)

(a) i. (2 p oints)Soit Tun arbre couvrant minimal d"un grapheG= (S;A;w), et soitS0un sous ensemble deS. SoitT0le sous-graphe deTinduit parS0(c"est une foret), et soitG0le sous-graphe deG induit parS0. Montrez que siT0est connexe (donc un arbre), alorsT0est un arbre couvrant minimal deG0. Solution:Supposons queT0ne soit pas un arbre couvrant minimal deG0. On sait queT0est un arbre, c"est donc qu"il n"est pas minimal. SoitT01un arbre couvrant minimal deG0. PosonsR=TT0, l"ensemble des arcs deTqui ne sont pas dansT0. PosonsT1=T01[R. Montrons queT1est un arbre couvrant deG. T

1couvreGcarT01couvreG0, et que les arcs deRcouvrentGG0.

1est un arbre (meme nombre d"arcs queT.

Le poids deT1est inférieur au poids deT, orTest un arbre couvrant minimal. Il y a donc contradiction. T

0est donc un arbre couvrant minimal deG0.ii.(2 p oints)Soit Tun arbre couvrant minimal d"un grapheG= (S;A;w). SoitG0= (S0;A0;w)le

graphe obtenu à partir deGen ajoutant un nouveau sommets0et ses arcs incidents. Montrez queT0obtenu en ajoutant àTle sommets0et un de ses arcs incidents de poids minimal n"est pas toujours un arbre couvrant minimal deG0.

Solution:

G= (fa;b;cg;f(a;b;1);(a;c;2)g)

T=G G

0= (fa;b;c;s0g;f(a;b;1);(a;c;2)(s0;b;1);(s0;c;1)g)

0= (fa;b;c;s0g;f(a;b;1);(s0;b;1);(s0;c;1)g)

UE J1BS8203 : Méthodes et outils pour la biologie des systèmes Session 1, Année 2012/2013 (b)

(2 p oints)Donnez un exemple d"un graphe orien tép ondéréG= (S;A), de fonction de pondération

w:A!Net d"origines, tel queGsatisfasse la propriété suivante :Pour tout arc(u;v)2A, il existe une arborescence des plus courts chemins de racinesqui contient(u;v)et une autre qui ne contient pas(u;v).

Solution:

G= (fs;u;vg;f(s;u;1);(s;v;1);(u;v;0);(v;u;0)g)

T1 = (fs;u;vg;f(s;u;1);(s;v;1)g)

T2 = (fs;u;vg;f(s;u;1);(u;v;0)g)

T3 = (fs;u;vg;f(s;v;1);(v;u;0)g)Exercice 2: Plus longue sous-séquence commune (9 points) Soitwun mot. Les motsuobtenus en retirant un nombre quelconque (entre0etlen(w)) de lettres forment les sous-séquences du motw. Exemple : siw=abacb, alors sseqs(w) =f;a;b;c;ab;aa;ac;ba;bc;bb;cb;aba;abc;abb;aac;aab;acb;bac;bab;bcb; abac;abab;abcb;aacb;bacb;abacbg Soitw1etw2deux mots. Il est possible de calculersseqs(w1)\sseqs(w2), donc de calculer la longueur de la plus longue sous-séquence commune à ces deux mots.

Le problème de laPlus longue sous-séquence commune(PLSC) consiste à trouverunesous-séquence com-

mune de longueur maximale. Notations :Soitwun mot. On notew[i]la(i+ 1)emelettre dew, etwile mot composé desipremières lettres du motw. Par conventionw0désigne le mot vide. Propriété :Soientu=um+1etv=vn+1deux mots, et soitw=wk+1une PLSC deuetv, alors 8< :siu[m] =v[n]alorsw[k] =u[m]etwkest une PLSC deumetvn siu[m]6=v[n]alorsw[k]6=u[m])(wk+1est une PLSC deumetvn+1) siu[m]6=v[n]alorsw[k]6=v[n])(wk+1est une PLSC deum+1etvn)

La propriété précédente permet l"écriture d"algorithmes basés sur la programmation ditedynamique, tech-

nique qui utilise des tableaux de stockage d"informations pour éviter de répéter des calculs. Pour calculer

PLSC(u;v), une matriceCva contenir pour chaque couple d"indice (i,j) la longueur dePLSC(ui;vj). Cette

matrice peut se calculer ainsi : c[i;j] =8 :0sii= 0ouj= 0 c[i1;j1] + 1sii >0;j >0etu[i1] =v[j1] max(c[i;j1];c[i1;j])sii >0;j >0etu[i1]6=v[j1] (a)

Soit le prog rammep ythonsuiv ant:

defplscCodage (u,v ): # Initialisation de la matrice avec des 0 code = [0]( len (u)+1) foriinrange ( len (code )): code [ i ] = [0]( len (v)+1) # Calcul du codage foriinrange (1 , len (u)+1): forjinrange (1 , len (v)+1): ifu[ i1]==v[ j1]: code [ i ] [ j ] = code [ i1][ j1]+1 else: code [ i ] [ j ] = max(code [ i ] [ j1],code [ i1][ j ]) returncode

Page 2 sur 4

UE J1BS8203 : Méthodes et outils pour la biologie des systèmes Session 1, Année 2012/2013 i. (2 p oints)Remplissez le tableau suiv ante nexécutan tl"app elplscCodage("abcbdab","bdcaba").

Solution:0123456

bdcaba

00000000

1a0000111

2b0111122

3c0112222

4b0112233

5d0122233

6a0122334

7b0122344

ii. (1 p oint)Donnez et justifiez la c omplexitédu programme plscCodage.

Solution:Deux boucles imbriquées, et à l"intérieur, une instruction de branchement. Les deux

branches sont en(1), le branchement est donc en(1). La boucle la plus interne est donc en(len(v)), et la plus externe en(len(u)len(v)). Pour des raisons similaires, la phase d"initialisation est également en(len(u)len(v)).

La complexité de l"algorithmeplscCodageest en(len(u)len(v)).(b)i. (4 p oints)Donnez un algorithme ou bien un programme p ythonplscDecodage(u,v,code)qui

retourne une des plus longues sous-séquences communes àuetven utilisant le tableaucode, qui est le résultat de l"appelplscCodage(u,v)

Solution:

defplscDecodage (u,v , code ): plsc = " " i = len (u) j = len (v) whilecode [ i ] [ j ]>0:# on sait que code [0][ j ]=0 et code [ i ][0]=0 ifu[ i1]==v[ j1]: plsc = u[ i1]+plsc i = i1 j = j1 elifcode [ i ] [ j1]<=code [ i1][ j ] : i = i1 else: j = j1 returnplscii.(1 p oint)Donnez le résultat de la suite d"instructions : code = plscCodage (u,v) plsc = plscDecodage (u,v , code) print( plsc ) Solution:bcbaiii.(1 p oint)Donnez e tjustifiez la comple xitéde v otrepro grammeplscDecodage.

Solution:

Meilleur des cas ( u=an;v=bm) :

(1) Pire des cas ( u=an;v=abman1) :O(len(u) +len(v))Page 3 sur 4 UE J1BS8203 : Méthodes et outils pour la biologie des systèmes Session 1, Année 2012/2013

Exercice 3: Parcours en largeur (5 points)

Définition :Un graphe biparti est un graphe non orientéG(S;A)dans lequelSpeut être partitionné en

deux ensemblesS1etS2tels que(u;v)2Aimplique soit(u;v)2S1S2, soit(u;v)2S2S1. En d"autres termes, toutes les arêtes passent d"un ensemble à l"autre.

Propriété :Un graphe non orientéG(S;A)est connexe si pour n"importe quel sommets2S, l"exécution

de l"algorithmeParcoursLargeur(G,s)vu en cours colorie tous les sommets en noir. En d"autres termes, tous les sommets sont accessibles depuis n"importe quelle racine. (a) (4 p oints)Donnez un algorithme (ou u nprogramme p ython)basé sur le parcours e nlargeur vu en cours qui retourneVraisi et seulement si le grapheGest biparti et connexe.

Solution:

defbipartiConnexe (G): forsinlisteSommets (G): demarquerSommet( s ) s . dist = None r = random. choice ( listeSommets (G)) marquerSommet( r ) r . dist = 0 f = Queue() f . put( r ) while notf . empty (): s = f . get () fortinlisteVoisins ( s ): if notestMarqueSommet( t ): marquerSommet( t ) t . dist = s . dist+1 f . put( t ) elif( t . dists . dist)%2==0: # G n " est pas biparti returnFalse forsinlisteSommets (G): if notestMarqueSommet( s ): # G n " est pas connexe returnFalse returnTrue(b)(1 p oint)Donnez e tjustifiez la compl exitéde v otrea lgorithme. Solution:Sans tenir compte du démarquage initial qui coute(S). Meilleur des cas (Un graphe comp oséde ntriangles disjoints) : (1) Pire des cas( G=Km;n, le graphe complet biparti) :O(S+A)Page 4 sur 4quotesdbs_dbs4.pdfusesText_8

[PDF] [PDF] SUJET + CORRIGE

PARCOURS :Master 1

Épreuve :Examen

Date :Lundi 8 avril 2013

Heure :10 heures

Durée :2 heures

Documents : autorisés

Épreuve de M. AlainGriffaultSUJET + CORRIGE

Avertissement

La plupart des questions son tindép endantes.

Solutions en langage algorithmique o uen Py-

Graphes pondérés6

Plus longue sous-séquence commune9

Parcours en largeur5

Total:20

Exercice 1: Graphes pondérés (6 points)

1couvreGcarT01couvreG0, et que les arcs deRcouvrentGG0.

1est un arbre (meme nombre d"arcs queT.

0est donc un arbre couvrant minimal deG0.ii.(2 p oints)Soit Tun arbre couvrant minimal d"un grapheG= (S;A;w). SoitG0= (S0;A0;w)le

Solution:

G= (fa;b;cg;f(a;b;1);(a;c;2)g)

0= (fa;b;c;s0g;f(a;b;1);(a;c;2)(s0;b;1);(s0;c;1)g)

0= (fa;b;c;s0g;f(a;b;1);(s0;b;1);(s0;c;1)g)

Solution:

G= (fs;u;vg;f(s;u;1);(s;v;1);(u;v;0);(v;u;0)g)

T1 = (fs;u;vg;f(s;u;1);(s;v;1)g)

T2 = (fs;u;vg;f(s;u;1);(u;v;0)g)

Soit le prog rammep ythonsuiv ant:

Page 2 sur 4

Solution:0123456

00000000

1a0000111

2b0111122

3c0112222

4b0112233

5d0122233

6a0122334

7b0122344

Solution:

Solution:

Meilleur des cas ( u=an;v=bm) :

Exercice 3: Parcours en largeur (5 points)

Solution: