[PDF] TD no 1 PDF td.pdf

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 Montrer que tout graphe connexe contient au

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] 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 Montrer que tout graphe connexe contient au

[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] Exercices de théorie des graphes Année académique 2020 − 2021

Exercice 7 Pour chacun des graphes simples non orientés suivants, donner un exemple d'existence ou prouver l'inexistence a) Un graphe biparti

[PDF] quelques exercices 1 Quelques propriétés des graphes

Dans les exercices suivants, `a moins d'indications contraires, on travaille sur grés de tous les sommets d'un graphe non-orienté est un nombre pair Com-

[PDF] Graphes non orientés

Distance entre deux sommets et diamètre d'un graphe Graphe pondéré et plus courte chaîne Matrice associée à un graphe Exercices d'apprentissage AA AB

[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] Introduction à la théorie des graphes Solutions des exercices

1 Graphes non orientés Exercice 1 On obtient le graphe biparti suivant (à gauche) : P1 C1 P2 C2 P3 C3 P1 C1 P2 C2 P3 C3 En colorant les arêtes de ce

[PDF] Exercices

Exercices Dans les exemples sont reliés si leur intersection est non vide ; Ci-après, la matrice M est associée à un graphe orienté G qu'on représentera

[PDF] graphes

exercice 2 : 1 quelle matrice peut-être la matrice d'adjacence d'un graphe non orienté? A = 0 1 0

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

TD n o1

Généralités sur les graphes

Exercice 1SoitG= (V;E)un graphe.

(a)SiGest orienté :jEj=åx2Vd(x) =åx2Vd+(x). (b)SiGest non orienté :åx2Vd(x) =2jEj. En particulier, les sommets deGde degré impair sont en nombre pair. Exercice 2Dans un graphe non orienté, il y a toujours deux sommets de même degré. Exercice 3Lecomplémentaired"un graphe non orientéGest le grapheGdéfini par :V(G) = V(G)et8x;y2V(G),(x;y)2E(G)ssi(x;y)=2E(G). Prouver ou infirmer les assertions sui- vantes : (a)Deux graphes sont isomorphes ssi leurs complémentaires sont isomorphes. (b)SiGest non connexe alorsGest connexe. (c)SiGest connexe alorsGest non connexe.

Exercice 4(a)Quels sont ceux des graphes suivants qui sont isomorphes?(b)Combien il y a-t-il de graphes non orientés sur un ensemble fixé de 4 sommets? Combien il

y en a-t-il à isomorphisme près? Lesquels?

Exercice 5Prouver le Lemme 4.

Exercice 6Gest connexe ssi pour toute bipartition(X;Y)deV(G), il existe une arête ayant une extrémité dansXet l"autre dansY. Exercice 7Vrai ou faux? Si chaque sommet d"un graphe non orientéGest de degré 2 alorsG est un cycle. Exercice 8Un sommetxd"un graphe non orienté connexeGest ditpoint d"articulationdeG siGxest non connexe. Montrer que tout graphe connexe contient au moins deux sommets qui ne sont pas points d"articulation. Exercice 9On définit inductivement une classe de graphes non orientésCpar : 1

1.tout som metisolé est dans C;

2. si G2C, tout grapheHobtenu en ajoutant àGun sommetxet une ou plusieurs arêtes adjacentes àxest dansC. Montrer queCest exactement la classe des graphes connexes. En déduire une nouvelle preuve de la Proposition 5 (Gconnexe) jE(G)j jV(G)j1). Exercice 10Un graphe non orientéGest ditbipartis"il existe une partition deV(G)en deux ensemblesXetYtelle que tout arête deGjoint un sommet deXà un sommet deY. Montrer que Gest biparti ssiGne contient aucun cycle de longueur impaire. Exercice 11Tout graphe non orienté connexe admet un sous-graphe couvrant connexe et acy- clique (appeléarbre couvrantdu graphe). Par conséquent, tout graphe non orienté admet un sous-graphe couvrant acyclique (appeléforêt couvrantedu graphe). Exercice 12Combien existe-t-il de graphes orientés (resp. non orientés) ànsommets? Exercice 13Montrer que le nombre d"arbres sur un ensemble fixé densommets estnn2. Exercice 14(Connectivité de sous-graphes et d"extensions de graphes). On désigne parw(G) laconnectivitéd"un graphe non orientéG, c"est à dire le nombre de ses composantes connexes. En particulier,Gest connexe ssiw(G)=1. SoientG=(V;E)unGNOetIun ensemble de paires de sommets deG. Prouver les assertions suivantes :

1.w(G)w(G+I)w(G)jIj.

2.w(G)w(GI)w(G)+jIj.

Si w(Ge)>w(G)pour toute2I, alorsw(GI) =w(G)+jIj.

4.w(G) jVjjEj.

5.Gest acyclique ssiw(G) =jVjjEj.

Exercice 15Prouver le Lemme 8.

Exercice 16Prouver la Proposition 10.

Exercice 17Quand on utilise la représentation par matrice d"adjacence, la plupart des algo- rithmes sur les graphes ànsommets s"exécutent enO(n2), mais il y a des exceptions. Montrer qu"il est possible de déterminer enO(n)si un graphe orienté contient untrou noir- un sommet

de degré entrantn1 et de degré sortant 0 -, même si on utilise une représentation par matrice

d"adjacence. Exercice 18SoitGun graphe non orienté. Montrer queGest un cycle ssiGest non acyclique minimal. 2

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

Corrigé du TD n

Généralités sur les graphes

Correction exercice 1.

(a)Clairement,E=S x2VEntrants(x)=S

C"est le résultat cherché.

(b)SiHest une orientation du graphe non orientéG, on a clairement :jE(G)j=jE(H)j, soit, d"après ce qui précède : jE(G)j=12 x2V(H)dH(x)+å x2V(H)d+H(x)) =12 x2V(H)d

H(x) =12

x2V(G)d G(x): Correction exercice 2.SoitGun graphe non orienté ànsommets. SoitDl"ensemble des degrés des sommets deG. Puisque chaque sommet est relié à au plusn1 autres sommets, D f0;:::;n1g. Si par ailleurs les degrés sont deux à deux distincts,Dest de cardinalnet donc, nécessairement,D=f0;:::;n1g. MaisGne peut contenir simultanément un sommet de

degré 0 et un sommet de degrén1, puisque un sommet de degrén1 est relié à tous les autres

sommets du graphe. DoncjDjCorrection exercice 3. (a)Clair : tout isomorphismehdeGsurHest aussi un isomorphisme deGsurHpuisque : (b)Supposons doncGnon connexe. Soientx,ydeux sommets deV(G) =V(G). Six,ysont dans deux composantes connexes distinctes deG, alors(x;y)=2E(G)donc(x;y)2E(G)et ces sommets sont connectés dansG. Six,ysont dans une même composante connexe deG, soitzun sommet appartenant à une autre composante connexe deG(un tel sommet existe puisqueGest non connexe). Alors, par le même raisonnement que précédemment,(x;z)et (y;z)sont deux arêtes deG, doncxetysont connectés dansGpar le cheminxzy. (c)Cette assertion est fausse : le grapheG= (f1;2;3;4g;ff1;2g;f2;3g;f3;4gg)et son com- plémentaire sont tous les deux connexes. 3

Correction exercice 4.

(a)Désignons parG1,G2,G3,G4les quatre graphes représentés de gauche à droite. Il est facile

de voir queG1,G2etG4ont tous pour complémentaire une union de deux triangles. Ces trois graphes sont donc isomorphes, en vertu du(a)de l"exercice 3. Par contreG3contient un triangle, ce qui n"est pas le cas deG1. Donc cesG3n"est pas isomorphe àG1(ni àG2ou G 4). (b)Dans un graphe non orienté ànsommets, il y aC2n=n!2!(n2)!paires de sommets. Chacune de ces paires peut constituer ou ne pas constituer une arête du graphe. Ce qui donne 2 C2n graphes possibles sur un ensemble fixé densommets. Pourn=4 on obtient 26=64 graphes

possibles. Ces graphes se répartissent dans les 11 classes d"isomorphismes suivantes :Correction exercice 5.Récurrence sur la longueurkdu chemin : L"hypothèse est claire pour

k=1 : tout chemin de longueur 1 est élémentaire. Supposons l"hypothèse de récurrence vé-

rifiée par tout chemin de longueur inférieure à unkfixé. Soitp=x0a1x1:::ak+1xk+1un che- min de longueurk+1. Sipn"est pas élémentaire, soitil"indice du premier sommet interne depqui admet plusieurs occurences dansp. Soitjle plus petit indice tel quexj=xi. Alors p

0=x0a1x1:::aixiaj+1xj+1:::ak+1xk+1est un chemin entrex0etxk+1de longueur inférieure à

k. Par hypothèse de récurrence, il existe un chemin élémentaire entrex0etxk+1. Correction exercice 6.): Soient(U;V)la bipartition deV(G),u2U,v2V. Soitp: x

0x1:::xk1xkun chemin deu=x0àv=xk(dont l"existence est garantie par la connexité de

G). On noteile plus grand indice des sommets depappartenant àU. AlorsiG est une union de cycles élémentaires.Il revient au même de prouver que tout graphe connexe

dont tous les sommets sont de degré 2 est un cycle élémentaire. Soit doncGun tel graphe. Par

le Lemme 2,Gcontient un cycle et donc, un cycle élémentairep(Lemme 4). Ce cycle couvre nécessairement tous les sommets deG: sinon, il existerait une arêteaentreV(p)etV(G)V(p)

(par connexité deGet grâce à l"exercice 6), et l"extrémitéxdeaqui est surpserait adjacente

à 3 sommets (ses 2 voisins danspet l"autre extrémité dea), ce qui contredirait l"hypothèse

d(x) =2. Enfin,Gne contient aucune arête autre que celles intervenant dansp, toujours grâce 4

à l"hypothèse sur les degrés. Par conséquent,G=p. (Notons qu"on a même :tout sommet de G

est de degré 2ssiG est une union de cycles élémentaires.) Correction exercice 8.Commençons par introduire quelques définitions : sip:x yetq: y zsont deux chemins partageant une même extrémitéy, on notepqle cheminxp yq z. Un cheminpest unsous-chemind"un cheminqs"il existe deux cheminsp1,p2tels que q=p1pp2. Un chemin est maximal s"il n"est sous-chemin propre d"aucun chemin. Sipest un cheminélémentaireet six,ysont deux sommets apparaissant dans cet ordre dansp, on note p[x;y]l"unique sous-chemin depd"extrémitésxety. Considérons l"extrémitéud"un chemin élémentaire maximalp0deG. Tout sommetvadja- cent àuest surp0(sinon on pourrait prolongerp0). Soientx;y2V(G)etp:x yun chemin élémentaire dexàydansG. Sipne contient pasu, alorspest aussi un chemin élémentaire de xàydansGu. Sipcontientu, notonsaetble prédécesseur et le successeur deudansp. D"après ce qui précède,aetbsont surp0. De plus,u=2p0[a;b], puisqueuest une extrémité dep0. Donc le chemin obtenu à partir depen remplaçant le sous-cheminp[a;b] =aubpar le cheminp0[a;b]est un chemin dexàyqui ne contient pasu. Autrement dit, c"est un chemin de xàydansGu. On a ainsi montré que deux sommets distincts deuconnectés dansGsont aussi connectés dansGu. CommeGest connexe, on en déduit queGuest connexe :un"est pas

un point d"articulation deG. Par symmétrie, il en va de même pour l"autre extrémité dep0, ce

qui finit de prouver le résultat annoncé. Correction exercice 9.Il est clair queCest inclu dans la classe des graphes connexes : tout

sommet isolé est connexe et, siGest connexe, les graphes obtenus à partir deGpar application de

la règle de construction décrite en 2 sont aussi connexes. Montrons qu"inversement, tout graphe

connexeGest dansC: c"est clair siGest un sommet isolé. Supposons le résultat vérifié pour tout

graphe à au plusnsommets, pour un entiernfixé. SoitGun graphe connexe àn+1 sommets. Guest un graphe connexe ànsommets et donc, par hypothèse de récurrence,Gu2C. CommeGest obtenu à partir deGupar adjonction du sommetuet des arêtes deIncid(u),G est lui-même dansC. Application :siGest connexe, alorsjE(G)j jV(G)j1. Le résultat est clair pour les som- mets isolés. S"il est vrai pour un graphe connexe fixéG, il l"est pour tout grapheHobtenu à partir deGpar application de la règle 2 puisque, selon cette règle,jV(H)j=jV(G)j+1 et jE(H)j jE(G)j+1. Correction exercice 10.L"implication)est claire : tout chemin de longueur impaire dans le graphe(X;Y)-biparti a nécessairement une extrémité dansXet l"autre dansY. Ça ne peut donc pas être un cycle. Réciproquement, supposons queGne contienne aucun cycle de longueur impaire et montrons queGest biparti. Notons tout d"abord qu"un graphe est biparti ssi chacune de ses composantes connexes non triviales est biparti. Soit doncHune composante connexe non triviale deGetuun sommet deH. Pour toutx2V(H), on noted(x)la longueur d"un plus court chemin entrexetu. (CommeHest connexe,dest bien définie sur toutx2V(H).) Notons alors 5 X=fx2V(H):d(x)est pairgetY=fx2V(H):d(x)est impairg. Soienta=fx;yg 2E(H)et p(resp.q) un plus court chemin dex(resp.y) àu. Alorsxp uq1 ya!xest un cycle de longueur jpj+jqj+1=d(x)+d(y)+1. Ce cycle étant de longueur paire (par hypothèse),d(x)etd(y)

sont de parités opposées. Autrement dit, les extrémités deane sont pas simultanément dansX

ou dansY:Hest(X;Y)-biparti.

Correction exercice 11.

deGest non vide : il contientG. SoitTun sous-graphe couvrant connexe deG, minimal pour le nombre d"arêtes. Pour toutea2E(T),Taest un sous-graphe couvrant deGcomportant moins

d"arête queT. Il est donc non connexe, par hypothèse de minimalité surT. Ainsi, la suppression

d"un arête quelconque du graphe connexeTle déconnecte :Test un arbre (Théorème 7-(??)) et

donc un arbre couvrant deG.

2ème méthode.SoientGun graphe connexe. L"ensemble des sous-graphes couvrant et acy-

cliques deGest non vide : il contient(V(G);?). SoitTun sous-graphe couvrant acyclique maximal deG. Montrons par l"absurde queTest connexe : si tel n"est pas le cas,Tcomporte une composante connexeHtelle queV(H)6=V(G)et par connexité deG, il existe une arête a=fx;ygdeGqui jointV(H)etV(G)V(H)(Exercice 6). OrT+aest acyclique, sinon il existerait un cycle élémentaire deT+acontenanta(puisqueTest acyclique) :xa!yp x, et donc un cheminpentrexetydansT. Par conséquent,T+aest un sous-graphe acyclique deGqui contientT:contradiction avec l"hypothèse de maximalité deT. Finalement,Test un sous-graphe couvrant acyclique et connexe deG: c"est un arbre couvrant deG.

3ème méthode.Méthode algorithmique. Tant qu"il existe des arêtesasur un cycle deG,

choisir une tellea, faireG=Ga. Le graphe obtenu est tjs couvrant, connexec et contient au moins une arête "cyclique" de moins. Le graphe obtenu à la sortie de la boucle TQ est l"arbre cherché. Correction exercice 12.Il y an(n1)couples de sommets distincts et donc 2n(n1)graphes orientés possibles. Il y a

ån1i=1i=n(n1)2

paires de sommets et donc 2n(n1)2 graphes non orientés possibles. Correction exercice 13.Le problème posé revient à calculer le nombre d"arbres possibles sur l"ensemble ànsommetsV=f1;:::;ng. Nous allons montrer que les arbres surVsont en bijection avec les(n2)-uplets d"éléments deV. A tout arbreTsurVon associe les deux suites de sommets(fi)0 6

78FIGURE1 -(fi) = (2;1;5;3;6;7);(si) = (1;3;3;4;4;4)

On s"intéresse en fait uniquement au(n2)-upletU=(s1;:::;sn2)qui identifie de manière unique l"arbreT. En effet, à tout(n2)-uplet d"éléments deVon peut associer l"arbreTsurV (i1;s1)est dansT. On retirei1deVets1 deU, et on réitère l"opération avec les nouveauxV

etU. Lorsqu"il ne reste plus d"élément dansU, on termine en ajoutant àTl"arête constituée des

deux derniers éléments deV. Ces deux constructions prouvent l"équipotence de l"ensemble des arbres et de l"ensemble des (n2)-uplets surf1;:::;ng. Comme ce dernier ensemble est de cardinalnn2, on a le résultat cherché.

Correction exercice 14.

1 L "inégalitéw(G)w(G+I)est claire : l"ajoût d"arêtes àGne peut pas faire croître le nombre de composantes connexes. Dans le même temps, une arête ajoutée à un graphe relie au plus deux composantes connexes de ce graphe et donc réduit d"au plus un sa connectivité. Par conséquent, siI=fe1;:::;emg, la connectivité deG+I= (:::((G+ e

1)+e2)++em)est minorée parw(G)m.

2 Les ar gumentssont similaires à ceux de la question précédente : le retrait d"arêtes ne peut pas faire décroître la connectivité, d"où l"inégalitéw(G)w(GI). De plus, le retrait d"une arête provoque la scission d"au plus une composante connexe. La majoration w(GI)w(G)+jIjs"en déduit facilement. 3 Notons I=fe1;:::;emg. Le fait quew(Ge)>w(G)pour toute2Isignifie qu"aucune de ces arête n"est sur un cycle deG. Puisque le retrait d"arêtes diminue le nombre de cycles, on sait a fortiori quew(Ge1)w(G)équivaut àw(Ge) =w(G)+1, par la question 2. Il s"ensuit quew(GI) =w((:::((Ge1)e2)e3)em) = w(G)+m. 4 Le graphe GEest sans arête et donc, clairement,w(GE) =jVj. Par ailleurs, par 2, w(GE)w(G)+jEj. D"où finalement :jVj w(G)+jEj.

5): siGest acyclique, alors aucune arête deGn"est sur un cycle et donc, la suppression

de toutee2Eincrémente le nombre de composantes connexes deG. Autrement dit : w(Ge)>w(G)pour toute2E. Il s"ensuit, par 3, quew(GE) =w(G)+jEjet la conclusion vient dew(GE) =jVj. 7 (: supposonsw(G) =jVjjEj. Pour toute2E,w(Ge) jVj(jEj1)par 4. D"où w(Ge)jVjjEj+1=w(G)+1>w(G)pour toute2E. Ceci signifie qu"aucune2E n"est sur un cycle deG:Gest acyclique.

Correction exercice 15.

Si Gest une arborescence de raciner, alors le graphe non orienté sous-jacent àGest connexe, puisque le chemin orienté derà deux sommets quelconquesxetydonne lieu à un chemin non orienté entre ces deux sommets. Il est aussi acyclique. Sinon, soitCun cycle. Une arborescence étant clairement sans circuit, il existe un sommetxdeCcomportant deux prédécesseursuetvdansC. Soientp(resp.q) l"unique chemin orienté deràu(resp. v). Alorsp:uxetq:vxsont deux chemins orientés distincts deràx: une contradiction. Soient Gun arbre etr2V(G). On sait qu"il existe un chemin uniquepxderà n"importe quel sommetxdeG(voir Theorem 7, Item 6). On oriente alors tous les arcs depxder versx. Cette orientation peut être renouvellée sans conflit sur tout autre cheminpyissu de r. En effet, si l"arcuvapparaît danspx,vun"apparaît pas danspy. Si cela se produisait on aurait :r u!v xetr v!u y, et ceci entraînerait l"existence de deux chemins distincts derversu. Correction exercice 16.Récurrence surk. Le résultat est immédiat pourk=1 puisqu"un che- min de longueurkest un arc du graphe. Le calcul deMkpourk>1 donne : M kij=nå `=1Mk1i`M`j: Or tout chemin de longueurkentrexietxjse décompose en un chemin de longueurk1 entre x iet un certainx`, suivi d"un arc reliantx`etxj. Le résultat découle alors de l"hypothèse de récurrence selon laquelleMk1i`est le nombre de chemins de longueurk1 joignantxiàxk. Correction exercice 18.)est clair. Pour la réciproque, considérons un cycle élémentaireC deG. S"il existe une arêtea2EnC, alorsGaest non acyclique : une contradiction. Donc G=C. 8

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

TD n o2

Arbres couvrants minimaux

RAPPELS: Soit un graphe non orientéG= (V;E). SiPest une partie non triviale deV(i.e., P6=?etP6=V), le couple(P;VP)est appelécoupuredu graphe et noté(P;:P). On dit d"un cheminp:x ydeGqu"iltraversela coupure(P;:P)six2Pety=2P. En particulier, une arêteatraverse(P;:P)si l"une de ses extrémités est dansPet l"autre non. Exercice 1(a)Montrer que tout cheminptraversant une coupure(P;:P)contient une arête qui traverse cette même coupure. (b)Montrer que si une arête est sur un cycleCet traverse une coupure(P;:P), alors il existe une autre arête deCtraversant cette même coupure.

Exercice 2Dans un graphe pondéré, une arêteaest dite minimale pour la traversée d"une cou-

pure(P;:P)siaest de poids minimal parmi les arêtes qui traversent(P;:P). Soitaune arête

d"un graphe non orienté connexe pondéré. Montrer l"équivalence des assertions suivantes :

(a)il existe un ACMTdeGqui contienta; (b)il existe une coupure(P;:P)deGtelle queaest minimale pour la traversée de cette coupure. Exercice 3SoitGun graphe non orienté pondéré, connexe et non acyclique. SoientTun ACM deGetaune arête deGn"apparaissant pas dansT. On sait qu"alorsT+acontient un unique cycleCpassant para. (a)Montrer que toute arête deCest de poids inférieur ou égal à celui dea. (b)Montrer que si de plusaappartient à un arbre couvrant minimalT0, alorsCcontient une arêteb6=ade même poids quea. Pour tout sous-grapheHdeG, on note`(H)la suite des poids des arêtes deHtriés en ordre croissant. (c)Montrer que pour deux ACMTetT0quelconques deG,`(T) =`(T0). Exercice 4Soitaune arête de poids minimal dans un graphe pondéré. Montrer queaappartient

à un arbre couvrant minimal du graphe.

Exercice 5Soit(G;c)un graphe non orienté connexe valué par une fonction injective. Prouver ou infirmer : (a)Tout ACM deGcontient l"arête de poids minimum; (b)Aucun ACM ne contient l"arête de poids maximum; (c)Il n"y a qu"un ACM. 1 Exercice 6Dans un graphe non orienté connexe valué(G;c), on construit un sous-grapheTde la manière suivante : On considère une partitionV1tV2deV(G). On noteG1,G2les sous-graphes deG induits, respectivement, parV1etV2. SoitT1(resp.T2) un ACM deG1(resp.G2). On choisit une arêteade coût minimum parmi les arêtes joignantV1àV2et on appelle

Tle sous-grapheT= (T1[T2)+a.

Le grapheTest-il un arbre couvrant minimal deG?

Exercice 7Faire tourner l"algorithme deKruskalsur les graphes pondérés suivants :bd f i 2 79
c e

1014411

1 28g8
7 4 dα befc 5 2 1 1 121
h 5 αExercice 8Montrer que la variante suivante de l"algorithme deKruskalretourne un arbre

couvrant minimal deG:Algorithme 1:Variante de l"algorithme deKruskalDonnées:Un graphe pondéré conne xe(G;c)

Résultat:Un A CMFde(G;c)

1F=?;

2numéroter les arêtes deGdans un ordre quelconquea1:::am;

3pouri=1à mfaire4F=F+ai;

5siF contient un cyclealors6choisir une arêtebde poids maximal sur ce cycle ;

7F=Fb;

fin fin

8retournerFExercice 9PourAun ensemble d"arêtes deG, on notem(A)le poids maximal d"une arête deA.

Modifier l"algorithme de Prim pour déterminer un arbre couvrantAayant le plus petitm(A). Exercice 10L"algorithme deKruskalpeut retourner des ACM différents suivants le tri des

arêtes par poids croissant à partir duquel il effectue son calcul. Montrer que pour tout ACMTde

G, il existe un tri des arêtes par poids croissant à partir duquelKruskalretourneT. Exercice 11Montrer que siHest un sous-graphe d"un ACM deGet si de plusaest une arête deGminimale pour la traversée d"une coupure qui contientH, alorsH+aest lui aussi un sous- graphe d"un ACM deG. En déduire une nouvelle preuve de la correction de l"algorithme de

Kruskal.

2 Exercice 12SoientG= (V;E;w)un graphe non orienté connexe et pondéré. On considère l"al- gorithme suivant.Données:Un graphe non orienté conne xepondéré G= (V;E;w) 1F=G;

2trier les arêtes par poids décroissants ;

3pourchaque arête a prise dans cet ordrefaire4siFa est connexealorsF=Fa;

fin

5retournerF(a)Montrer que cet algorithme termine sur toute entrée.

(b)Montrer qu"il retourne un arbre couvrant. (c)Cet arbre couvrant est-il toujours de poids minimal? 3

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

Corrigé du TD n

Arbres couvrants minimaux

Correction exercice 1.

(a)On considère le premier sommetudepappartenant à:P. Alors l"arête qui précèdeudans pfait l"affaire. (b) Correction exercice 2.(a))(b): le grapheTaadmet deux composantes connexesP1et P

2. Montrons que le couple(P1;P2)est la coupure cherchée. Notons tout d"abord queatraverse

(P1;P2)(clair). Par ailleurs, aucune arête deTane traverse(P1;P2)(sinon ces deux parties seraient connectées dansTa). Donc s"il existe une arêteb=fx;ygdistincte deaet traversant (P1;P2),b=2T. Par conséquent,T+bcomporte un unique cycle de la formexb!yp x, oùp est un chemin dansT. Commeptraverse(P1;P2), il contient une arête qui traverse cette coupure

(d"après la question précédente), et cette arête ne peut être quea. Ainsi,aest sur l"unique cycle

deT+bet par conséquent, le grapheT0= (T+b)aest un arbre couvrant deG. Il doit donc

être de poidsà celui deT, ce qui entraîne quebest de poidsà celui dea: l"arêteaest bien

minimale pour la traversée de(P1;P2). (b))(a): SoitT0un ACM deG. SiT0contienta, c"est terminé. Sinon,T0+acontient un unique cycle de la formexa!yp x, oùpest un chemin deT0. Commeptraverse la coupure

(P;:P), il contient une arêtebtraversant cette coupure. Par minimalité deapour la traversée de

(P;:P),best de poidsà celui dea. Par conséquent,T= (T0+a)best un arbre couvrant de poidsà celui deT0: c"est un ACM deGqui contienta.

Correction exercice 3.

(a)Soitb6=aappartenant àC. Alors(T+a)best un arbre couvrant de(G;c). Par conséquent, c((T+a)b)c(T). Autrement dit,c(T)+c(a)c(b)c(T)et doncc(b)c(a). (b)Siaappartient à un ACM, alorsaest minimale pour la traversée d"une coupure(P;:P). Mais alors, le sous-chemin deCobtenu en retirant l"arêteadeCest un chemin dansTqui traverse la coupure(P;:P). Ce chemin contient donc nécessairement une arêtebdeTqui traverse (P;:P). Commebest sur le cycle,c(b)c(a), d"après la question précédente. Commeb traverse(P;:P),c(a)c(b), puisqueaest minimale pour la traversée. Finalement,c(b) = c(a). (c)On notea1;a2;:::;akla suite des arêtes deT0. Soit(Ti)0ikla suite de sous-graphes deG définie récursivement par :T0=Tet pour toutiAlors pour touti>0 : (1)Tiest un arbre couvrant qui contient(a1;:::;ai); (2)`(Ti) =`(Ti1).

Par conséquent,Tk=T0et`(T0) =`(T0) =`(T).

Correction exercice 4.

1ère méthode.Il suffit de faire tourner l"algorithme deKruskalà partir d"un tri des arêtes

par poids croissant dans lequelaapparaît en première position (un tel tri existe puisqueaest de poids minimal). Alorsasera sélectionnée lors du premier passage dans la boucle "pour" et

placée dans le grapheFen construction. Le résultat se déduit alors de la preuve de la correction

de cet algorithme, qui établit que le grapheFretourné est un ACM deG.

2ème méthode.SoitTun ACM deG. SiTcontienta, c"est fini. Sinon,T+acontient un

unique cycle passant para. Donc le grapheT0obtenu à partir deT+aen retirant une arêteb6=a

de ce cycle est un arbre couvrant (connexe parce qu"on a enlevé une arête d"un cycle d"un graphe

connexe, acyclique parce que ce cycle était unique, couvrant parce queV(T0) =V(T)). De plus, c(T0) =c(T)+c(a)c(b)c(T)puisquec(a)c(b). CommeTest de poids minimal,T0est un ACM (qui contienta).

Correction exercice 5.

(a)est vraie. SoitTun ACM deGqui ne contient pas l"arête de poids minimuma. AlorsT+a contient un unique cycle qui passe paraet, comme dans l"Exercice 4, pour toute arêteb6=a de ce cycle,(T+a)best un arbre couvrant deG. De plus,c((T+a)b) =c(T)+c(a) c(b). Commeaest de poids minimum et commecest injective, on ac(a)1;b2;:::;bk) un tri des arêtes deT(resp. deT0) par pondérations croissantes. Soit`le plus petit des indicesitels queai=2E(T0). AlorsT0+a`comporte un cycle, et ce cycle contient au moins une arête qui n"est pas dansT(sinon ce serait un cycle dansT). Soitbune telle arête. Commeb2E(T0)E(T),b2 fbi;i> `g. De plus(T0+a`)best un arbre couvrant deG. Enfin,c((T0+a`)b) =c(T0)+c(a`)c(b)engendré par toutes les arêtes deGenvisagées à un instant donné de l"exécution de l"algorithme,

que ces arêtes aient été retenues ou non dansF. En d"autres termes,Hest le graphe vide avant le

quotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] TD no 1

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

Généralités sur les graphes

Exercice 1SoitG= (V;E)un graphe.

Exercice 5Prouver le Lemme 4.

1.tout som metisolé est dans C;

1.w(G)w(G+I)w(G)jIj.

2.w(G)w(GI)w(G)+jIj.

Si w(Ge)>w(G)pour toute2I, alorsw(GI) =w(G)+jIj.

4.w(G) jVjjEj.

5.Gest acyclique ssiw(G) =jVjjEj.

Exercice 15Prouver le Lemme 8.

Exercice 16Prouver la Proposition 10.

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

Corrigé du TD n

Généralités sur les graphes

Correction exercice 1.

C"est le résultat cherché.

H(x) =12

Correction exercice 4.

0=x0a1x1:::aixiaj+1xj+1:::ak+1xk+1est un chemin entrex0etxk+1de longueur inférieure à

0x1:::xk1xkun chemin deu=x0àv=xk(dont l"existence est garantie par la connexité de

Correction exercice 11.

2ème méthode.SoientGun graphe connexe. L"ensemble des sous-graphes couvrant et acy-

3ème méthode.Méthode algorithmique. Tant qu"il existe des arêtesasur un cycle deG,

ån1i=1i=n(n1)2

78FIGURE1 -(fi) = (2;1;5;3;6;7);(si) = (1;3;3;4;4;4)

Correction exercice 14.

1)+e2)++em)est minorée parw(G)m.

5): siGest acyclique, alors aucune arête deGn"est sur un cycle et donc, la suppression

Correction exercice 15.

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

Arbres couvrants minimaux

à un arbre couvrant minimal du graphe.

Tle sous-grapheT= (T1[T2)+a.

Le grapheTest-il un arbre couvrant minimal deG?

1014411

Résultat:Un A CMFde(G;c)

2numéroter les arêtes deGdans un ordre quelconquea1:::am;

3pouri=1à mfaire4F=F+ai;

5siF contient un cyclealors6choisir une arêtebde poids maximal sur ce cycle ;

7F=Fb;

8retournerFExercice 9PourAun ensemble d"arêtes deG, on notem(A)le poids maximal d"une arête deA.

Kruskal.

2trier les arêtes par poids décroissants ;

3pourchaque arête a prise dans cet ordrefaire4siFa est connexealorsF=Fa;

5retournerF(a)Montrer que cet algorithme termine sur toute entrée.

Master 1 d"Informatique

2010 / 2011Recherche Opérationnelle

Corrigé du TD n

Arbres couvrants minimaux

Correction exercice 1.

2. Montrons que le couple(P1;P2)est la coupure cherchée. Notons tout d"abord queatraverse

Correction exercice 3.

Par conséquent,Tk=T0et`(T0) =`(T0) =`(T).

Correction exercice 4.

1ère méthode.Il suffit de faire tourner l"algorithme deKruskalà partir d"un tri des arêtes

2ème méthode.SoitTun ACM deG. SiTcontienta, c"est fini. Sinon,T+acontient un

Correction exercice 5.