Examen graphes 13 2h sans documents Théorie des graphes

Théorie des graphes : Examen graphes 13 2h sans documents

Télécharger PDF

Examendegraphes- I3- 2 heures- sansdocuments

Question1 : Dantzig(8 Pts)

SoitunreseauR= (E;�;l) constitue d'ungraphe(E;�)sansboucleet d'uneapplicationl

qui,a chaquearc,faitcorrespondreunreelrepresentant salongueur.Lessommetsdu

graphesontE=f1;2;:::;ng.

Onveut,pourtoutcoupledesommets(x;y), calculerla longueurd'unpluscourtchemin

dexay. Oncherchedeplusunemethodeincrementale, c'est-a-direunemethodeevitant

detoutrecalculersi l'onpossededeja unesolutionpourunreseauR0 , etquel'onrajoute

unsommeta cereseau.

L'ideeestdepartird'unreseautriviala unseulsommet,etderajouteruna unles

sommets.OnconsiderepourcelalesensemblesEk =f1;2;:::;kg, avec1kn.

LasolutiondenotreproblemepourlereseauRk , sous-reseaudeRconstruitsurles

elements deEk , estunematriceLk detaillekkdont l'elementlk (i;j) a pourvaleurla

longueurd'unpluscourtchemindeiajdansRk . S'iln'existepasdechemindeiajdansR k

, onposelk (i;j) =1. Deplus,onal1 (1;1)= 0.Lasolutionduproblemepour

toutle reseauRestevidemment lamatriceL=Ln .

a)Donnez,pourle petitreseauci-dessous,lasuitedesmatricesLk .7 32 12 31 14 b)ProposezunemethodepourcalculerLk , connaissantLk�1 . Onsupposeraqu'iln'existe

pasdecircuitabsorbant, c'est-a-diredecircuitdelongueurstrictement negative. Jus-

tiezvotrereponse.

c)Surla basedecettemethode,proposezunalgorithmepourcalculerLn , dansle casou

il n'ya pasdecircuitabsorbant.

d)Quelleestlacomplexite decalculdevotrealgorithme?

e)Comment modiervotrealgorithmepourdetecterlapresenceeventuelled'uncircuit

absorbant ?

Note: untelalgorithmea ete propose pourlapremierefoisparG.B.Dantzigen1966.1 Question2 : Arbitrage(3 Pts)

\Unarbitrageestunecombinaisond'operationsnancierespermettant derealiserun

benecesansrisque(entheoriedumoins),entirant partid'imperfectionssusceptibles

d'appara^treentredierents marches."(P. Vernimmen,Finance d'entreprise, ed.Dalloz).

Etant donne unensembledendevises(parexemple: l'Euro,le Dollar,le Yen),unetable

detauxdechangeestuntableauTdedimensionnndanslequell'elementT[i;j] indique

le nombred'unitesdela devisejqu'onobtient enchangeant uneunite dela devisei. Par

exemple,siT[� ;
] = 1:3,onobtient 1:3 dollarpouruneuro.

L'existenced'unarbitragedansunetabledetauxdechangeconstitueundesordredansle

systememonetaire,caril permeta unoperateurdes'enrichirindeniment pardesimples

jeuxd'ecriture: celui-cipeuteneet,parunesuitebienchoisiedeconversions,recuperer

plusquesamiseinitialeetrecommencerautant defoisqu'ille souhaite.Supposonspar

exemplelatablesuivante:
�
10:8110� 1:251140 0:0090:0081

Enoperant la suitedechanges� ! !
!� surunesommed'unEuro,unspeculateur

recupere1400:0090:8 = 1:008� .

a)Formulezprecisement, dansle cadredesgraphes,le problemedela recherchedel'exis-

tenced'unarbitragedansunetabledetauxdechange.

b)Proposezunetransformationduproblemepermettant deseramenera unproblemeconnu. c)Quelalgorithmepeut-onemployerpourresoudreceprobleme? Quelleestsacom-

plexite ? Attention: il n'estpasdemande icidefournirunalgorithme,maisseulement

deciterle nomd'unalgorithmeconnu.

Question3 : Ornoir(4 Pts)

Enqualite d'ingenieurexpert,vousrecevezunappeld'oredelacompagniepetroliere

ALFquicherchea resoudreleproblemesuivant.Sonreseaudepipelinesluipermet

d'acheminerdesunitesdeproductionauxraneries19millionsdebarilsdepetrolebrut

parmois.Leschemadureseausetrouve engure1.LesnombresM[D] indiquent pour

chaquepipeline,ledebittransitant actuellement (D) etledebitmaximalsupporte par

cepipeline(M),enmillionsdebarilsparmois.Lacompagniesouhaitesavoirs'ilest

possibled'augmenterle debittotal,sachant quelesunitesdeproductionetderanage

sont capablesd'augmenterleurrendement.2 a)Quelalgorithme,etudie encours,permetderesoudreceprobleme? (iln'estpasde-

mande d'ecrirel'algorithme)

b)Montrezcomment trouverunesolutionauproblemedelacompagnie,enexecutant

uneetape del'algorithme.Onpreciseralesdonneesintermediairesutiliseeslorsde

cetteexecution(utilisezlafeuillejointeenpage4).

8 [3]

UNITES DE PRODUCTIONUNITES DE RAFFINAGE7 [2]

6 [6]

11 [11]

2 [0]

5 [5]

6 [4]

3 [3]

1 [1]

3 [3]

7 [6]

4 [3]

6 [4]

6 [6]

5 [5]Figure1 c)Montrezquelasolutionquevousproposezestoptimale.Sicen'estpasle cas,il peut

^etrenecessaired'executerunenouvelleetape del'algorithme.

Question4 : Graphehamiltoniensanscircuit(3 Pts)

OnconsidereungraphesanscircuitG= (E;�),etsapartitionenniveauxE0 , . . .,Ep .

a)Rappelerladenitiondelapartitionenniveauxd'ungraphe.

Onrappelleque,pourtouti2f0:::pg, pourtoutx2Ei , le rangr(x) dusommetxest

egalai, autrement ditlalongueurmaximaled'uncheminseterminant enxesti.

UnchemindansGestdithamiltoniens'ilpasseexactement unefoisparchaquesommetdeG. b)Montrerque,si touslesensemblesEi (i2 f0:::pg) contiennent chacunexactement

unsommet,alorsGadmetuncheminhamiltonien,etquecelui-ciestunique.

c)Montrerquereciproquement, siGadmetuncheminhamiltonien,alorstouslesen-

semblesEi (i2f0:::pg) contiennent chacunexactement unsommet.3 Question5 : Graphequasi-fortement connexe(2 Pts)

UngrapheG= (E;�)estditquasifortementconnexesi,a toutcoupledesommets(x;y),

onpeutassocierunsommetztelqu'ilexisteunchemindezaxetunchemindezay.

a)Rappelerladenitiond'uneracine.

b)Montrezque,siGestquasifortement connexe,alorsGpossedeuneracine.4 5