Théorie des graphes : Graphes representations algorithmique m1
Télécharger PDFAlgorithmique—M1
TD1 : Grapheset repr ́esentations
1Troisfa ̧consderepr ́esenterungraphe4 13 52 6
Exercice1 : Donnerunerepr ́esentationdugrapheci-dessusaumoyen d’unelisted’adjacence,
puisaumoyen d’unematriced’adjacence.
Consid ́eronsungrapheG= (V, E) sansboucletriviale.Onappellematriced’incidencedu
grapheG, la matrice`a|V|ligneset|E|colonnes,B= (bi,j ) d ́efiniepar:b i,j=
−1si l’arˆetejpartdusommeti
1si l’arˆetejarrive danssommeti0sinon. Exercice
2 : Donnerunerepr ́esentationdumˆemegraphe(ci-dessus)enmatriced’incidence.
Quelsprobl`emesrencontre-t-on?
Exercice
3 : Proposerunalgorithmedeconstructiondela matriced’incidence`a partirdela
listed’adjacenced’ungraphe,puis`a partirdesa matriced’adjacence.
Exercice4 : SiBT d ́esignela transpos ́ee deB, querepr ́esente la matriceBBT ?
2Algorithmiquesurchacunedesrepr ́esentations
Exercice
5 : Danschacunedestroisrepr ́esentations,queltempsfaut-ilpourd ́eterminersi
deuxsommetuetvdonn ́es sont voisins?
Exercice
6 : Danschacunedestroisrepr ́esentations,queltempsfaut-ilpourpourcalculerle
degr ́e sortant d’unsommet? Mˆemequestionpourle degr ́e entrant.
Exercice7 : R ́e- ́ecrivez l’algorithmeg ́en ́eriquedeparcoursd’ungraphevuencoursdefa ̧con
adapt ́ee `a chaquerepr ́esentation.Quelestle tempsd’execution,`a chaquefois?
Exercice8 : Consid ́eronsungrapheorient ́eG= (V, E). Unsommetvestunpuitsuniversel1 s’ilestde degr ́e entrant|V|−1 et de degr ́e sortant 0. ́
Etant donn ́ee unerepr ́esentationd’ungraphe
G= (V, E) parunematriced’adjacence,proposerunalgorithmepermettant ded ́eterminers’il
existeunpuitsuniversel.
3Grapheset mod ́elisation
Exercice9 : Combieny a-t-ilde circuitssimplesdansle graphede sommetsV={vi , si , ti }, i∈
[0..n−1] et d’arcsE={(vi , si ),(vi , ti ),(si , vj ),(ti , vj ) avecj= 1 +i modn}, i∈[0..n−1] ?
Exercice
10: Unpasseurse trouve aubordd’unerivi`ereavec unloup,unech`evreet une
salade.Commevousle savez probablement, lesloupmangent lesch`evresmaispaslessalades,
lesch`evresmangent lessaladesmaispaslesloups,et lessaladesnemangent personne.Danssa
barque,le passeurnepeuttransporterqu’unseuldestroisprotagonistes`a la fois.Lorsqu’ilest
danssa barqueousurla rive oppos ́ee,il nepeutempˆecherdecarnagealimentaire.Onsouhaite
savoirs’ilpeutamener,sainset saufs,del’autrecˆot ́e dela rive le loup,la ch`evreet la salade.Si
celaestpossible,combiendetravers ́eessont n ́ecessaires?
Pourr ́epondre`a ce probl`eme,vousendonnerezunemod ́elisationparungraphe,et le refor-
mulerezdansce cadre.
Exercice
11 : Des ́etudiantsA,B,C,D,EetFdoivent passerdesexamensdansdiff ́erentes
disciplines,chaqueexamenoccupant unedemi-journ ́ee :
– Algorithmique: ́etudiantsAetB.
– Compilation: ́etudiantsCetD.
– Basesdedonn ́ees: ́etudiantsC,E,FetG.
– Java : ́etudiantsA,E,FetH.
– Architecture: ́etudiantsB,F,GetH.
Oncherche `a organiserla sessiond’examenla pluscourtepossible.
Pourr ́epondre`a ce probl`eme,vousendonnerezunemod ́elisationparungraphe,et le refor-
mulerezdansce cadre.
4Grapheseuleriens
Exercice
12: Uncircuiteul ́eriendansungrapheorient ́e estuncircuitquipasseexactement
unefoisparchaquearc.SoitGungrapheorient ́e sanssommetisol ́e. D ́emontrerques’ilexisteun
circuiteul ́eriendansGalorsGestfortement connexe(ilexisteuncheminu wpourchaque
coupledesommetsu,w) et pourchaquesommetudeg− (u) = deg+ (u) (lesdegr ́es sortant et
entrant sont ́egaux).
Exercice13 : Inversement, supposant queGestungraphefortement connexeet pourchaque
sommetu, deg− (u) = deg+ (u). Comment trouver danscegrapheuncyclesimple? (Uncycle
simplepasseauplusunefoisparunarc.)
Si ona d ́ej`a trouv ́e uncyclesimpledansGalorsqu’est-cequenouspouvonsdirededegr ́es
entrant et sortant dechaquesommetsdugrapheHobtenu `a partirdeGensupprimant dans
Gtouslesarcdece cycle? D ́emontrerqueGposs`edeuncircuiteul ́erien,donnerunalgorithme
permettant de trouver ce circuit.1 puitsveutdirede degr ́e sortant z ́ero,et universelqu’ilvoittoutle monde
1Troisfa ̧consderepr ́esenterungraphe
Enlistes: 1 : (1,2,3,4);2 : (2)3 : (5,6)
4 : (4,3);5 : (5,3)6 : (6,5,3)
Biensˆur,il s’agitenfaitdelisteschaˆın ́ees!
Enmatriced’adjacence(z ́erosomispourplusde clart ́e)123456 1111121 311411 5116111 Correction2 : Onrencontredeuxdifficult ́es :
– Lesarˆetesn’ont pasdenom; il fauten donner
– Lesboucles! Ond ́ecidedemettrepourcet exercice seulementun2 enbu,e dansla matrice
d’incidence,sieestuneboucleautourdusommetu. Notonsqu’on ́etendainsila d ́efinition
standard.
abcdefghijklmn
12-1-1-1212 31-1-1111412-1 512-11612-1-1 Correction3 :
Pourconstruirela matriced’incidence: toutd’abordond ́eterminesa tailleet pourcelaon
comptele nombred’arˆetesdugraphes.Ensuite,pourchaquearˆeteonremplitla matrice(quiest
aud ́epartinitialis ́e `a 0).Casdeslistesd’adjacence:
Entr ́ee:tableaude listed’adjacenceE de taille$n$
Variables:entieri initialis ́e `a 0
sommetx,y
D ́ebut:
Pourx de 1 `a n faire
Pourtoutvoisinde y de x fairei++ fin du pour
fin du pour
B = matricede taillen*ii=0 Pourx de 1 `a n faire
Pourtoutvoisinde y de x fairei++ B(x,i)=-1
B(y,x)=1
fin du pour
fin du pourFin. Casdesmatricesd’adjacence:
Entr ́ee:matriced’adjacenceM de taille$n$
Variables:entieri initialis ́e `a 0
sommetx,y
D ́ebut:
Pourx de 1 `a n faire
Pourtouty de 1 `a n faire
si M(x,y)=1fairei++ fin du si
fin du pour
fin du pour
B = matricede taillen*ii=0 Pourx de 1 `a n faire
Pourtouty de 1 `a n faire
si M(x,y)=1fairei++ B(x,i)=-1
B(y,x)=1
fin du si
fin du pour
fin du pourFin. Correction
4 :
LamatriceM=BBT = (mi,j ) estcarr ́e detaillen. Deplus:
– Pourtouti6=j,mi,j =nb aretesX k=1b i,kb j,k
vautle nombred’arˆetesexistant entrelessommetsietj
(ind ́ependamment de l’orientation)
– Pourtouti,mi,i =nb aretesX k=1b i,kb i,k
vautle degr ́e dei.
2Algorithmiquesurchacunedesrepr ́esentations
Correction
5 :
– Listes:O(d+ (x)) (onparcoursla listedeu`a la recherche dev)
– Matriced’adjacence:O(1)(simpleacc`es `aEu,v )
– Matriced’incidence:O(m) (pourtoutearˆeteiontestebui etbvi quidoivent ˆetrenon-nulstouslesdeux) Correction6 : Degr ́e sortant :
– Listes:O(d+ (x)) (tailled’uneliste,standard)
– Matriced’adjacence:O(n) (compterles1 danslau`emelignede la matrice)
– Matriced’incidence:O(m) (oncomptepourtoutearˆeteilesbui valant 1)
Degr ́e entrant :
– Listes:O(m) (il fautparcourirtoutesleslisteset compterleslisteso`uuapparaˆıt)
– Matriced’adjacence:O(n) (compterles1 danslau`emecolde la matrice)
– Matriced’incidence:O(m) (oncomptepourtoutearˆeteilesbui valant−1)
Correction7 : Seulela ligne“pourtoutvoisinvdeu” est`a r ́e ́ecrire
– Listes:
C = u.tete
Tantque C != null
v = C.val
... // calculsur v
Fin tantque
Se faitenO(d+ (u)) pourchaquesommetu. Chaquesommetestvu unefois.OnestdoncenO(n+m)ENTOUT. – Matriced’adjacence:
Pourv de 1 a n
Si E(u,v)= 1
... // calculsur v
Fin si
Fin pour
SefaitenO(n) pourchaquesommetudoncO(n2 ) en tout.
– Matriced’incidence: Poure de 1 a m Si b(u,e)= 1 // u originede e, cherchonsla destinationPour
v de 1 a n Si b(v,e)= -1 ... //calculsurv Finsi FinpourFinsi Finpour
Lacomplexit ́e estimmonde:O(nm) pourchaquesommetudoncO(n2 m2 ) entout.
Correction
8 :iestunpuitsuniverselsi et seulement si dansla matricela ligneinecontient que
des0 et la colonneine contient quedes1 sauf`a l’intersectionde la lignei. Onpeutdonctesterde fa ̧con
exhaustive, ce quiprenduntempsquadratiqueen|V|.
3Grapheset mod ́elisation
Correction
9 : 2n , le graphese dessinecommeuncycledelosanges.Lescyclescontiennent toutlesv i
, et `a chaquefois,pourpasserde l’un`a l’autreil y a 2 possibilit ́es,soitparle haut,soitparle bas.Bref
nchoixbinaires`a faire.
Correction10:
Onconstruitungraphecorrespondant `a l’ ́evolutiondusyst`eme.Il suffitalorsderegarders’ily a un
chemindela configurationinitiale`a la configurationfinale.
Ona le graphe(nonorient ́e) pagesuivante.
Correction11: Onconstruitungraphe(nonorient ́e ici)danslequelchacunedesdisciplinesparunsommet,et relier
pardesarˆeteslessommetscorrespondant auxexamenincompatibles(ayant des ́etudiants encommun)
Il s’agitalorsdecolorierchacundessommetsdugraphesenutilisant le moinsdecouleurspossible,
dessommetsvoisinsnepouvant ˆetredela mˆemecouleur.Icitroiscouleurssuffisent, et onnepeutfaire
mieux.Leprobl`emeestdansle casg ́en ́eralNP-complet,doncdur!Algo JavaArchi BDCompil AB F,HE,F F,GC PCLS,-LS,PC PLS,C
S,PLCL,PSC
PSC,LLPC,SC,PLS PC,LS-,PLCS C- LS CCS L- B
Fig.1 – Corrig ́e del’exercice7
4Grapheseuleriens
Correction12 : Il suffitde montrerquele circuitpassepartouslessommets.Si ce n’ ́etaitpasle cas,
il existeraitunsommetincident `a aucunarc(puisquele circuitlescontient tous)doncisol ́e.
Le circuit“rentre”autant de foisdansunsommetqu’ilen sort(loidesnœuds)donclesdegr ́es entrants
et sortants sont lesmˆemes.
Correction
13: Remarquonsquetoutgraphesimplement connexeavecdeg− (u) = deg+ (u) est
fortement connexe.
Toutemarchedansuntelgrapherevient aupoint ded ́epart.Eneffet,unemarchequi“grille”les
arˆetesd ́ejavuesmaintient la propri ́et ́e de l’ ́egalit ́e desdegr ́es,saufpourle sommetde d ́epart.Lesommet
de d ́epartesttoujoursaccessible,caronne si ondeconnecte(simplement) le graphela marche estdansla
composante quile contient (ellea franchi unnombrepairdefoisla fronti`ere).
D`es qu’ona bouvcl ́e unemarche,il suffitd’nrecommenceruneen partant d’unsommetdusycleayant
desarcsnon-grill ́es : onreviendra`a ce sommetet ona ainsiagrandile cycle.