Algorithmique Exercice Coupe minimale dans un graphe

Publié par

TD 4 Algorithmique Exercice 1: Coupe minimale dans un graphe Soit G un graphe connecte, non-oriente avec eventuellement plusieurs aretes entre les n sommets. Une coupe dans G est un ensemble d'aretes qui si on les enleve, G devient non-connexe. Une coupe minimale est une coupe de cardinalite minimale. Le probleme de trouver une coupe maximale est NP-complet. L'idee de l'algorithme est de choisir uniformement une arete et de fusionner les deux sommets en un seul sommet en mettant sur ce sommet les aretes qui arrivaient aux deux sommets initiaux et en enlevant les boucles. On appelle cette operation une contraction. On voit que meme si le graphe initial n'avait qu'une seule arrete entre chaque sommet, le graphe ayant subi une contraction peut en contenir au plus deux. Ce processus diminue d'une unite le nombre d'arete. L'algorithme effectue des contractions jusqu'a ce que le nombre de sommets soit egal a 2 et retourne comme valeur le nombre d'aretes entre ces deux points. 1. Montrer qu'une contraction d'arete ne diminue pas la valeur d'une coupe minimale. 2. Soit k la valeur d'une coupe minimale. Montrer que G a au moins kn/2 aretes. 3. Soit Ei l'evenement de ne pas choisir une arete de C a la i-ieme etape, pour 1 ≤ i ≤ n? 2.

  • semi-anneau

  • coupe minimale

  • matrice n?

  • arete allant de ¬

  • booleennes indexees par les entiers ≤

  • chemins de longueur minimal


Publié le : mardi 19 juin 2012
Lecture(s) : 341
Tags :
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
TD 4
Algorithmique
Exercice 1:Coupe minimale dans un graphe SoitGsegnuhparnecteconon-o´e,n´taeirneveneev´cmeleeltuieusplntteˆrasrulertnesensommets. UnecoupedansGestunensteˆruqselbmeadel`ene,evioisesnlGdevient non-connexe. Unecoupe minimaletedevuornureuocealimLee.obpreml`pemaximaleestdepuocenutseinemt´linadiarec NP-complet. Lide´edelalgorithmeestdechoisiruniform´ementuneareˆteetdefusionnerlesdeuxsommets enunseulsommetenmettantsurcesommetlesarˆetesquiarrivaientauxdeuxsommetsinitiauxet enenlevantlesboucles.Onappellecetteop´erationunecontractionilesemmˆephraegO.qteuvnio initialnavaitquuneseulearrˆeteentrechaquesommet,legrapheayantsubiunecontractionpeut encontenirauplusdeux.Ceprocessusdiminueduneunit´elenombredareˆte.Lalgorithmeeectue descontractionsjusqu`acequelenombredesommetssoite´gala`2etretournecommevaleurle nombredareˆtesentrecesdeuxpoints.
1.Montrerquunecontractiondarˆetenediminuepaslavaleurdunecoupeminimale. 2. Soitkla valeur d’une coupe minimale. Montrer queGa au moinskn/ra2teˆes. 3. SoitEirunearˆetaesdcehoisinedtnepee´´vnemelCa`ali-i`emeuo1re´atepp,in2. (a) Montrerque Pr[E1]12/n. i1 (b) Montrerque Pr[E2|E1]12/(nenemalern´´esglue)pt1[rPeuqtEi|∩ Ej]12/(ni+1). j=1 2 (c)Montrerquelaprobabilite´trouverunecoupeminimaleparceproce´d´eestaumoins. n(n1) 4.Montrercommentobtenirunalgorithmedontlaprobabilite´de´checsoit<1/eet donner sa complexit´e.
Exercice 2:nusnadevitisnartretuˆoClhegrap 3 1.RappelerlalgorithmedeFloyd-WarshallpourcalculerlaclˆoturetransitiveenΘ(n) en temps. 2.Montrerquesilexisteunalgorithmequicalculelacloˆturetransitivedunematricen×nenA(n) additions,multiplicationsde´l´ementsdunsemi-anneauetsiA(3n)cA(nnu´reel)opruc >0 et toutnentier positifs, alors il existe un algorithme de multiplication avecM(n) =O(A(n)) additions et multiplications. 3. Montrerque si le produit de deux matricesn×nutpentreˆeela´lceucM(n) additions et mul-tiplications et si 4M(n/2)M(n) etM(2n)cM(n) pour uncet toutncalstoˆl,rolaure transitive se calcule enA(n) =O(M(n)) additions et multiplications. 4.Montrerquelesemi-anneaubool´eenB= ({0,1},,,0,1) n’est pas un anneau. log 72 5. SoitAetBdeux matricesn×nptuestcelaucbeoloelr´eeennes.LeproduinO(n(logn=) ) 2.82 O(neualsnqiuterlcoˆsbintions,aiairepo)are´tisiantr.ve
Exercice 3:Chemins de longueur minimale Onutiliselesemi-anneaudesr´eelspourtraiterlescheminsdelongueurminimaldansungraphe. SoitAetBdeux matricesn×n[s0dsnaeitnœcc`a..M]∪ {∞}. On veut calculer la matriceCde cœfficients cik= min(aij+bjk). 1jn 3 1. Montrerque l’algorithme classique fonctionne enO(nlogM). 2.Onpeutame´liorerunpeucetalgorithmeenutilisantlefaitquepoura6=b, a bmin(a,b) lim (x+x)/x= 1 x0 a b et donc min(a, b) = log(x+x)/logxpourxpetit. P n b k (a) Soitb1, . . . , bn,nentiers positifs, et soitf(x) =xeta= min(b1, . . . , bn). Montrer k=1 m alors quea=d−(1/m) logf(2 )epour toutm >logn. (b)Soitunr´eel0< x <1 etzerideiobnabnmitneolezn´tearrr´eedseatrˆeeptoesdeelnx. Alors d−(1/m) logxe= 1 +bz/mc. (c) Donnerun algorithme qui calcule le (min,+)-produit de deux matricesAetBrate´sdecneevse log 7log 72 dans [0..M]∪ {∞}enO(niqetm´thleurssueare´po)irasnoitrse´leosuO(n(Mlogn) ) op´erationsbinaires. 3. Comparerles deux algorithmes et donner la valeur deMpour laquelle le premier algorithme est plus efficace. 4.Est-cequecetalgorithmeestplusrapidequandilsagitdematricesboole´ennes?
Exercice 4:2eS-`lmeobPrTA Soitx1, . . . , xnun ensemble denpsraelestneisriravelbaoobseel´esnndeineex´n.Unlitt´eral sur cet ensemble de variables est une variablexiintigaonsuo,e´na¬xi. Une 2-clause sur cet 0 ensembledevariableestunedisjonctiondedeuxlitt´eraux``. Une assignationτest une fonction de l’ensemblex1, . . . , xndans{0,1}itt´unleurdavalL.rela`ioatgnsiasneaut`menetavirlenτ, soit V(`, τatgsee´)a`elτ(xi) si`=xiea1t`τ(xi) si`=¬xi. La valeur d’une clauseca`tnemevrelati une assignationτ, soitV(c, τleuresvaesdesdestsel)e,umdmamixAS-2Tlboreme`uxraep.Lliux´ett s´enoncecommesuit: ´ Etantdonne´unentiernet une liste de 2-clauses sur l’ensemble de variablesx1, . . . , xne´ndtrerei,m s’il existe une assignationτennodiuqsetuota`uslascleliladeestslevalaue1rp(orbl`emeded´ecisio.)n Calculer une telle assignation si elle existe (calcul d’une solution).
1.Onassociea`unelistede2-clausessurlensembledevariablesx1, . . . , xnrieot´ennguphraeGdont 0 lessommetssontleslitte´rauxsurlensembledevariablesx1, . . . , xn. Pour chaque clause``, 0 0 onajoute`aGuarneteˆelaaltned¬`a``rˆeteallantdetenuae¬``a`eosnpuoo`(¬¬xi=xi). (a) Montrerque l’on peut calculerGen tempsO(n+m`u)onest le nombre de variables etm lenombredeclauses.Onexpliciteraunchoixdestructuresdedonn´eesetonproposeraune description de l’algorithme en terme de pseudo-code.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.