Cours de theorie des graphes Théorie des graphes

Théorie des graphes : Cours de theorie des graphes

Télécharger PDF

ÉcoleNationaldesSciencesAppliquées-

DépartementGénieÉlectriqueetInformatique

M09:CoursdeThéoriedegrapheAuteur Prof.SafaeElHajBenali

safae.elhajb enali@usmba.ac.ma

N.B.:Versionprovisoire.Mercidemesignalerleserreurs !1 •Théoriedegraphe

12hdecours.

8hdeTD.

2hd'evaluation.

Tabledesmatières

Tabledesmatières2

1Elémentsdethéoriedesgraphes4

1Dénitionetconceptsdebase...............................5

1.1Dénition"intuitive"d'ungraphe.........................5

1.2Dénitionmathématiqued'ungraphe......................6

1.3Ordred'ungraphe.................................6

1.4Orientationd'ungraphe..............................7

1.5Multiplicité.....................................7

1.6Degrés........................................8

1.7Relationsentresommets..............................9

1.8Quelquestyp esdegraphes.............................10

2Représentationsd'ungraphe................................11

2.1Matriced'incidencesommets-arcs.........................11

2.2Matriced'adjacenceoud'incidencesommets-sommets.............12

3Connexitédanslesgraphes.................................13

3.1Chaînesetcycles..................................13

3.2Cheminsetcircuits.................................14

3.3Fermeturetransitived'ungraphe.........................15

3.4Connexité......................................17

3.5Comp osanteconnexe................................17

3.6Forteconnexité...................................18

2Leproblèmedupluscourtchemin20

1Lespluscourtscheminsd'unsommetàtouslesautres.................21

1.1AlgorithmedeDijkstra-Mo ore...........................21

1.2AlgorithmedeBellman-Ford............................23

2Pluscourtscheminentretouslessommets........................24

2.1AlgorithmedeFloyd-Warshall...........................24

3Ordonnancement,recherchedupluslongchemin27

1Contextegénéral.......................................28

2Dénitionsetpropriétés...................................28

2.1Datededébutauplustôtd'unetâchej.....................29

2.2Datededébutauplustardd'unetâchei....................29

2.3LesdiérentesMargesd'unetâche........................30

3Métho desd'ordonnancement................................32

4Lamétho deM.P.M......................................32

4.1RepresentationM.P.M................................33

4.2Calculdel'ordonnancementparlamétho deM.P.M...............342 TABLEDESMATIéRES3

5Lamétho deP.E.R.T.....................................37

5.1ReprésentationdeP.E.R.T.............................37

5.2DicultésdeconstructiondugrapheP.E.R.T..................38

5.3Calculdel'ordonnancementparlamétho deP.E.R.T...............38

4Colorationdegraphe43

1Histoireduproblème....................................43

1.1Formulationenthéoriedesgraphes........................44

1.2Applicationsdelacoloration............................44

2Colorationdessommets...................................45

2.1Dénitiondelanotiondestable.........................45

2.2Leproblèmedecoloration.............................46

2.3Encadrementdunombrechromatique......................47

2.4AlgorithmedecolorationdeWelshetPowell..................48

3Colorationdesarêtes....................................48

3.1Présentationduproblème.............................48

3.2Lienaveclacolorationdessommets.......................48

3.3Exempledecolorationd'arêtes..........................49

[PremierChapitre\

Elémentsdethéoriedesgraphes

Leproblèmedesp ontsdeKönigsb erg:

LavilledeKönigsb ergcomprenait4quartiers,séparéspardesp onts.LeshabitantsdeKönigsb erg

sedemandaients'ilétaitp ossible,enpartantd'unquartierquelconquedelaville,detraversertous

lesp ontssanspasserdeuxfoisparlemêmeetdereveniràleurp ointdedépart.

Fig.1.1Problèmedesp ontsdeKönigsb erg(Eulerproblem1736)

"Euler"démontraen1736qu'ilétaitimp ossibledetraverserchacundesseptp ontsdelaville

deKönigsb ergunefoisexactementetdereveniraup ointdedépart.

Eulerreprésentacettesituationàl'aided'un"dessin"oùlessommetsreprésententlesterreset

lesarêtes,lesp ontscommelemontrelagure1.2.

Fig.1.2Grapheasso ciéauproblèmedesp ontsdeKönigsb erg

Eulerdémontraqueceproblèmen'apasdesolution.Leproblèmedesp ontsdeKönigsb ergest

identiqueàceluiconsistantàtraceruneguregéométriquesansleverlecrayonetsansrepasser

plusieursfoissurunmêmetrait.4 1.DÉFINITIONETCONCEPTSDEBASE5

Lathéoriedesgraphesconstitueundomainedesmathématiquesqui,historiquement,s'estaussi

développ éauseindedisciplinesdiversestellesquelachimie(mo délisationdestructures),labiologie

(génome),lessciencesso ciales(mo délisationdesrelations)ouenvued'applicationsindustrielles

(problèmeduvoyageurdecommerce).Elleconstituel'undesinstrumentslespluscourantsetles

plusecacesp ourrésoudredesproblèmesdiscretsp osésenRechercheOp érationnelle(RO).

Ungraphep ermetdereprésentersimplementlastructure,lesconnexions,lescheminements

p ossiblesd'unensemblecomplexecomprenantungrandnombredesituations,enexprimantles

relations,lesdép endancesentreseséléments(eg,réseaudecommunication,réseauxferroviaireou

routier,arbregénéalogique,diagrammedesuccessiondetâchesengestiondeprojet,etc).Enplus

desonexistencepurementmathématique,legrapheestaussiunestructurededonnéespuissante

p ourl'informatique.

1Dénitionetconceptsdebase

1.1Dénition"intuitive"d'ungraphe

Dénition1.1Ungrapheestunschémaconstituéparunensemble(icisupp oséni)dep oints

etparunensembledeèchesreliantchacunedeux.Lesp ointssontapp eléslessommetsdu

graphe,etlesècheslesarcsdugraphe."

Exemple1.1Danslegrapheci-après,ona:

unensembledesommets:{a,b,c,d,e,f,g,h},

unensembled'arcs:{1,2,3,4,5,6,7,8,9}.

Remarque1.1"Lap ositiondessommetsetlaformedesarcssuruneguren'imp ortepas ;seul

imp ortedesavoircommentlessommetssontreliés".Lesgraphes1.3et1.4sontditsisomorphes.

Notation1.1L'arc3vadusommeteausommetf.Onditqu'ilestdelaforme(e,f)eton

écritparconventionque3=(e,f).Onremarquequesilaforme(g,c)sutp ourdésignerl'arc6

6CHAPITRE1.ELÉMENTSDETHÉORIEDESGRAPHES

Fig.1.3Unexempledegraphe

Fig.1.4UnGrapheisomorpheaugraphedelagureprécédente

demanièreunivo que,laforme(f,e)nesutpasp ourdésignerl'arc1uniquementcar4=(f,e)

également.

1.2Dénitionmathématiqued'ungraphe

Dénition1.2UngrapheG=(X,U)estlecoupleconstitué:

1.parunensembleX={x1 ,x2 ,...,xn }.

2.parunefamilled'élémentsU={u1 ,u2 ,...,um }dupro duitcartésienX×X={(x,y)/x∈

Xety∈X}.

1.3Ordred'ungraphe

Selonlesdénitionsprécédentes,l'ensembledesommetsestsupp oséni.

1.DÉFINITIONETCONCEPTSDEBASE7

Dénition1.3Onapp elleordredugrapheG=(X,U)lenombredesommetsdugraphe.

Notation1.2L'ordredeGestdonclecardinaldeXetnoté|X|.

Exemple1.2Legraphedelagure1.3estd'ordre8.

1.4Orientationd'ungraphe

Dénition1.4(Arête)Unearêteestunensembledesommets(ensembledecardinalité1ou

2).UnearêteestdoncunélémentdeP2 (X)(l'ensembledespartiesàdeuxélémentsdel'ensembleX). Notation1.3Lanotation{x,y}p ourraitêtreemployéemaisilfaudraitécrire{x}(p ourx=y).

SoitungrapheG=(X,U),onnoteradonclesarêtessouslaforme[x,y](avecx∈Xety∈X).

Dénition1.5(Graphenonorienté)Un"graphenonorienté"seraapp eléunmulti-

grapheetnotéG=(X,E)avecE⊂P2 (X).

Exemple1.3Réseaudepiéton.

Remarque1.2Dansunmultigraphe,ilp eutyavoirplusieursarêtesentredeuxsommets.

Dénition1.6(Arc)Unearcestunepaireordonnéedesommets(x,y).

Dénition1.7(Grapheorienté)Undigrapheouun"grapheorienté"estungraphedont

touteslesarêtessontorientées.

Exemple1.4Réseaudevol.

1.5Multiplicité

Dénition1.8(Boucleetextrémités)

Unarcdelaforme(x,x)estuneb oucle.

Soitunarcdelaforme(x,y),xetysontapp eléslesextrémitésdel'arc:

8CHAPITRE1.ELÉMENTSDETHÉORIEDESGRAPHES

xestl'extrémitéinitialedel'arc ;

yestl'extrémiténaledel'arc.

Fig.1.5Unexempledeb oucleetd'extrémités

Dénition1.9(Multiplicitéd'unepaire(x,y))Lamultiplicitéd'unepaire(x,y)estle

nombred'arcs(dugrapheG)ayantcommeextrémitéinitialexetcommeextrémiténaley.

Notation1.4Lamultiplicitéd'unepaire(x,y)estnotée:m+ G

(x,y).Onp osem− G(x,y)=m +G (y,x)etm G(x,y)=m −G (x,y)+m+ G(x,y). six6=yalorsmG (x,y)estlenombred'arcsayantuneextrémitéenxetuneeny.

six=yalorsmG (x,y)vautdeuxfoislenombredeb ouclesenx.

1.6Degrés

a)Degréd'unsommet

Dénition1.10Pourungrapheouunmultigraphe,onapp elledegrédusommetx,etonnote

d(x),c'estlenombred'arcsayantuneextrémitéenx.Attention !uneb ouclesurunsommetest

comptéedeuxfois.

Exemple1.5Danslegraphedelagure1.3:d G(e)=5, dG (c)=?.

Lemme1.1(Lemmedesp oignéesdemains)Lasommedesdegrésdessommetsd'unmul-

tigrapheestégaleàdeuxfoislenombred'arêtes.

Exemple1.6Danslegraphe1.6,onalesdegrés:d(x 1)=2 d(x2 )=1d(x 3)=3 d(x4 )=2d(x 5)=1 d(x6 )=1

1.DÉFINITIONETCONCEPTSDEBASE9

Fig.1.6

etlenombred'areteestégaleà5.

b)Degréd'ungraphe

Dénition1.11Ledegréd'ungrapheestledegrémaximumdetoussessommets.

Ungraphedonttouslessommetsontlemêmedegréestditrégulier.Siledegrécommunestk,

alorsonditquelegrapheestk-régulier.

Exemple1.7Dansl'exemple1.6,ledegrédugrapheest3.

Exercice1.1Est-ilp ossiblederelier15ordinateursdesortequechaqueappareilsoitreliéavec

exactementtroisautres ?

1.7Relationsentresommets

Dénition1.12(Sommetsvoisins)

Lesommetyestunsuccesseurdusommetxs'ilexisteunarcdelaforme:(x,y).

Lesommetyestunprédécesseurdusommetxs'ilexisteunarcdelaforme:(y,x).

Lesommetyestunvoisinouadjacentdusommetxs'ilexisteunarcdelaforme(x,y)

oudelaforme(y,x)(autrementditsiyestunsuccesseurouunprédécesseurdex).

Unsommetp endantestunsommetquin'aqu'unseulvoisin.

Notation1.5L'ensembledessuccesseursdusommetxestnoté:Γ+ (x).

L'ensembledesprédécesseursdusommetxestnoté:Γ− (x).

L'ensembledesvoisinsoudessommetsadjacentsdusommetxestnoté:Γ(x)=Γ+ (x)+Γ− (x).

Exemple1.8Danslegraphedelagure1.3:Γ(e)=Γ +(e)+Γ −

(e)={f,h}∪{f,d}={f,d,h}.

10CHAPITRE1.ELÉMENTSDETHÉORIEDESGRAPHES

1.8Quelquestyp esdegraphes

a)p-graphe

Dénition1.13SoitungrapheG=(X,U),silenombred'arcsquivad'unsommetxàun

sommetydeXestinférieurouégalàp(p ourtouslessommetsxetydeU)alorsonditqueG

estunp-graphe.

Notation1.6G=(X,U)estunp-graphe⇐⇒ ∀(x,y)∈X2 /|{u∈U,u=(x,y)}|≤p.

Exemple1.9Legraphedelagure1.3estun2-graphe(m+ G

(f,e)=2).

b)Graphesimple

Dénition1.14Ungraphesimpleestunmultigraphe:

sansb oucles ;

telqu'iln'yaitjamaisplusd'unearêteentredeuxsommetsquelconques

Fig.1.7Unexempledegraphesimple

c)Graphecomplet

Dénition1.15Ungrapheestcompletsichaquesommetdugrapheestreliédirectementà

touslesautressommets.

d)Graphebiparti

2.REPRÉSENTATIONSD'UNGRAPHE11

Fig.1.8Unexempledegraphecomplet

Dénition1.16Ungrapheestbipartisisessommetsp euventêtredivisésendeuxensembles

XetY,desortequetouteslesarêtesdugrapherelientunsommetdansXàunsommetdansY

(danslagure1.9,onaX={1,3,5}etY={2,4,6},ouviceversa).

Fig.1.9Unexempledegraphebiparti

Exercice1.2Untournoiopp ose6équip es.Chaqueéquip edoitarontertouteslesautres.

1.Construisezungraphereprésentanttouteslespartiesp ossibles.

2.Queltyp edegrapheobtenez-vous ?

3.Sichaqueéquip enejouequ'unmatchparjour,combiendejoursfaudra-t-ilp ourterminer

letournoi ?

2Représentationsd'ungraphe

Nousaimonsbiencommuniquerpardesdessins,maislesmachinesn'ensontpasencorelà:il

fautdonctrouverd'autresfaçonsdereprésenterlesgraphes.

Lasolutionconsisteàutiliserdesmatrices,etilyadiérentesmétho des.

2.1Matriced'incidencesommets-arcs

Dénition1.17Lamatriced'incidenceoud'incidencesommets-arcsd'ungrapheG(X,U)

sansb oucleestunematricetellequechaquecolonnecorresp ondàunarcdeGetchaqueligneà

12CHAPITRE1.ELÉMENTSDETHÉORIEDESGRAPHES

unsommetdeG;siu=(i,j)∈U,lacolonneuatoussestermesnuls,sauf:{ aiu =+1,a ju=−1, Exemple1.10Ondonnecommeexemplelamatriced'incidencesommets-arcsdugraphepartiel

sansb oucleengendréparl'ensembledesarcsdugraphedelagure1.3privédel'arc5(lab oucle)        1 2 3 4 6 7 8 9

a0 0 0 0 0 0 0 0

b0 0 0 0 0 0 0+1

c0 0 0 0−1 0 0 0

d0 0 0 0 0+1+1 0

e−1+1+1−1 0−1 0 0

f+1 0−1+1 0 0 0 0

g0 0 0 0+1 0 0 0

h0−1 0 0 0 0−1−1        2.2Matriced'adjacenceoud'incidencesommets-sommets

Dénition1.18Lamatriced'adjacenceoud'incidencesommets-sommetsd'ungraphe

G(X,U)estunematricecarréeoùchaquelignecorresp ondàunsommetdeGetchaquecolonne

corresp ondégalementàunsommetdeG.Letermegénéraldelamatriceest:a

i jtelque a

i j=m +G (xi ,xj )signiequelesommetxi estadjacentausommetxj .a i j

=0sinon.

Encasdeb oucle(p ourlesommeti,parexemple),onplaceun1surladiagonale(enp osition(i,i)). Exemple1.11Ondonnecommeexemplelamatriced'incidencesommetssommetsasso ciéeau

3.CONNEXITÉDANSLESGRAPHES13

graphedelagure1.        a b c de f

g h

a0 0 0 0 0 0 0 0

b0 0 0 0 0 0 0 1

c0 0 1 0 0 0 0 0

d0 0 0 0 1 0 0 1

e0 0 0 0 0 1 0 1

f0 0 0 0 2 0 0 0

g0 0 1 0 0 0 0 0

h0 0 0 0 0 0 0 0        Remarque1.3Lamatriced'adjacenced'ungraphenonorientéestsymétrique:a

i j=a ji. 3Connexitédanslesgraphes

3.1Chaînesetcycles

Dénition1.19UnechaînedansG,estunesuitedelaforme(x0 ,u1 ,x1 ,u2 ,...,xk−1 ,uk ,xk )

ayantp ourélémentsalternativementdessommets(xi )etdesarêtes(ui ),commençantetse

terminantparunsommet,ettellequelesextrémitésdeui soientxi−1 etxi ,i=1,...,k.Six 0=aetx k

=b,ondiraquelachaînerelieaetb.Enplus,ondiraquelachaîneaune

longueurk(c'estlenombred'arêtesdelachaîne).Unechaînedoitcomp orteraumoinsunearête.

Legraphe1.10contientleschaînes(x1 ,u3 ,x3 ,u4 ,x4 )et(x4 ,u4 ,x3 ,u2 ,x2 ,u1 ,x1 ),entreautres.

Onnechangepasunechaîneeninversantl'ordredesélémentsdanslasuitecorresp ondante,

ainsileschaînes(x1 ,u3 ,x3 ,u4 ,x4 )et(x4 ,u4 ,x3 ,u3 ,x1 )sontidentiques.

Onapp elledistanceentredeuxsommetslalongueurdelaplusp etitechaînelesreliant.

Lediamètred'ungraphelapluslonguedesdistancesentredeuxsommets.

Unechaîneestélémentairesichaquesommetyapparaîtauplusunefois.

Unechaîneestsimplesichaquearêteapparaîtauplusunefois.Danslegraphe1.10,(x 1,u 1,x 2,u 2,x 3

)estunechaînesimpleetélémentaire.

Unechaînetellequex0 =xk estapp eléechaînefermée.Danslegraphe1.10,(x 2,u 2,x 3,u 4,x 4,u 4,x 3,u 2,x 2

)estunechaînefermée.

Unechaîneferméesimpleestapp eléecyclesiseullesommetdedépartapparaîtdeuxfois

danslachaîne.Danslegraphe1.10,(x2 ,u2 ,x3 ,u4 ,x4 ,u5 ,x2 )estuncycle.

Théorème1.1Ungrapheestbipartisietseulements'ilnecontientaucuncycledelongueur

impaire.

14CHAPITRE1.ELÉMENTSDETHÉORIEDESGRAPHES

Fig.1.10

3.2Cheminsetcircuits

Cesontlesmêmesdénitionsquelesprécédentesmaisenconsidérantdesconceptsorientés.

Uncheminconduisantdusommetaausommetbestunesuitedelaforme(x 0,u 1,x 1,u 2

, ...,xk−1 ,uk ,xk ).Surledigraphe1.11,onp eutvoirparexemplelechemin(x 3,u 2,x 2,u 1,x 1

).Parconvention,toutchemincomp orteaumoinsunarc.

Onapp elledistanceentredeuxsommetsd'undiraphelalongueurduplusp etitchemin

lesreliant.S'iln'existepasdecheminentrelessommetsxety,onp osed(x,y)=∞.Par

exemple,surledigraphe1.11,d(x1 ,x2 )=2,d(x4 ,x3 )=1,d(x3 ,x4 )=∞.

Uncircuitestuncheminavecx0 =xk .Ledigraphe1.11contientuncircuitenpartantdex 1. Lesnotionsdelongueur,decheminsetdecircuitssontanaloguesàcellesdeschaînesetdes

cyclesp ourlecasnonorienté.

Fig.1.11

Théorème1.2(Nombredecheminsdelongueurk)A k

(i,j),élémentàlap osition(i,j)delapuissancekième deA,estaussilenombredechemins

delongueurkquimènentdexi àxj .

3.CONNEXITÉDANSLESGRAPHES15

Letermedeparcoursregroup eleschemins,leschaînes,lescircuitsetlescycles.Unparcoursest: élémentaire:sitouslessommetsquilecomp osentsonttousdistincts ;

simple:sitouslesarcsquilecomp osentsonttousdistincts ;

hamiltonien:passeunefoisetuneseuleparchaquesommetdugraphe ;

eulérien:passeunefoisetuneseuleparchaquearcdugraphe1 ;

préhamiltonien:passeaumoinsunefoisparchaquesommetdugraphe ;

préeulérienouchinois:passeaumoinsunefoisparchaquearcdugraphe.

Remarque1.4Leproblèmeduvoyageurdecommerceestvoisinduproblèmehamiltonien.Il

consisteàtrouveruncircuithamiltoniendecoûtminimaldansungraphevalué.

3.3Fermeturetransitived'ungraphe

Lecalculdelafermeturetransitivep ermetderép ondreauxquestionsconcernantl'existencede

cheminsentrexetydansGetcecip ourtoutcoupledesommets(x,y).

Dénition1.20Onapp ellefermeturetransitived'ungrapheG=(X,U),legrapheGf =(X,U f

)telquep ourtoutcoupledesommets(xi ,xj )∈X2 ,l'arc/arête(xi ,xj )appartientàUf si

etseulements'ilexisteunchemin/chainedexi versxj .

Lecalculdelafermeturetransitived'ungraphep eutsefaireenfaisantlasommeb o oléenne

des"puissances"successivesdesamatriced'adjacence.Considéronsparexemplelegrapheorienté

suivant:

Soitlegraphed'ordre7suivant:

lamatriced'adjacenceasso ciéest:

Fig.1.12

16CHAPITRE1.ELÉMENTSDETHÉORIEDESGRAPHESA=       

0 1 0 0 0 0 0

0 0 0 0 0 1 1

0 0 0 1 0 0 0

0 0 0 0 1 0 0

0 0 0 0 0 0 1

1 0 0 0 1 0 0

0 0 1 0 0 0 0       Danscettematrice,A(i,j)=1ssiilexisteunchemindelongueur1p ourallerdeiàj.Pour

qu'ilexisteunchemindelongueur2p ourallerd'unsommetaàunsommetb,ilfautqu'ilexiste

unsommetitelqu'ilexisteunchemindelongueur1deaversietunautrechemindelongueur

1deiversb.Pourtestercela,ils'agitdeparcourirsimultanémentlaligneaetlacolonnebdela

matriceAetderegarders'ilyaun1àlamêmep ositiondanslaligneaetlacolonneb.Ainsi,en

multipliantcettematriceparelle-même,onobtientlamatriceA2 descheminsdelongueur2:A 2=       

0 0 0 0 0 1 1

1 0 1 0 1 0 0

0 0 0 0 1 0 0

0 0 0 0 0 0 1

0 0 1 0 0 0 0

0 1 0 0 0 0 1

0 0 0 1 0 0 0       Danscettematrice,A2 (i,j)=1ssiilexisteunchemindelongueur2p ourallerdeiàj.Par

exemple,A2 (a,g)=1carilexisteunchemin(<a;b;g>)delongueur2allantdeaàg.Defaçon

plusgénérale,Ak estlamatricedescheminsdelongueurk.

EnadditionnantAetA2 ,onobtientlamatriceA+A2 descheminsdelongueurinférieureou

égaleà2:A+A 2=       

0 1 0 0 0 1 1

1 0 1 0 1 1 1

0 0 0 1 1 0 0

0 0 0 0 1 0 1

0 0 1 0 0 0 1

1 1 0 0 1 0 1

0 0 1 1 0 0 0       Selonlemêmeprincip e,oncalculelamatriceA+A2 +A3 +A4 +A5 descheminsdelongueur

inférieureouégaleà5:

3.CONNEXITÉDANSLESGRAPHES17A+A 2+A 3+A 4+A 5=       

1 1 1 1 1 1 1

1 1 1 1 1 1 1

0 0 1 1 1 0 1

0 0 1 1 1 0 1

0 0 1 1 1 0 1

1 1 1 1 1 1 1

0 0 1 1 1 0 1       Sionrecommenceunefoisdeplus,etquel'oncalculelamatriceA+A2 +A3 +A4 +A5 +A6 descheminsdelongueurinférieureouégaleà6,onconstatequecettematriceestégaleàcelle

descheminsdelongueurinférieureouégaleà5.ParconséquentA+A2 +A3 +A4 +A5 estla

matriced'adjacencedelafermeturetransitiveGf dugrapheGdedépart,onconstatequ'unnouvel

arrangementdescolonnesetdeslignesp ermetdefaireapparaîtredesmatricescarrées,uniquement

forméesdes1,s'appuyantsurladiagonaleprincipale.A+A 2+A 3+A 4+A 5=       

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

0 0 0 1 1 1 1

0 0 0 1 1 1 1

0 0 0 1 1 1 1

0 0 0 1 1 1 1       LafermeturetransitivedugrapheG=(X,U)estlegrapheGf =(X,Uf )telque:U f

={(a,a),(a,b),(a,f),(a,g),(a,c),(a,d),(a,e),(b,b),(b,a),(b,f),(b,g),(b,c),(b,d),

(b,e),(g,g),(g,c),(g,d),(g,e),(c,c),(c,d),(c,e),(c,g),(d,d),(d,e),(d,g),(d,c),

(e,e),(e,g),(e,c),(e,d),(f,f),(f,a),(f,b),(f,g),(f,c),(f,d),(f,e)}.

3.4Connexité

Lanotiondeconnexitéexprimelap ossibilitéd'allerden'imp ortequelsommetdugrapheà

n'imp ortequelautresommetdugraphe.

Dénition1.21Unmultigrapheconnexeestungraphetelquep ourtoutepairedesommetsx

ety,ilexisteunechaînereliantxety.

Exemple1.12Lepland'unevilledoitêtreconnexe.

Cegraphe1.13estnonconnexe.

3.5Comp osanteconnexe

18CHAPITRE1.ELÉMENTSDETHÉORIEDESGRAPHES

Fig.1.13Exempledegraphenonconnexe

Dénition1.22Unecomp osanteconnexeestunsousgrapheconnexedetaillemaximale.

Remarque1.5ilesttoujoursp ossibledepartitionnerungrapheencomp osantesconnexes.Par

exemple,surlagure1.3,sionconsidèrelemultigraphealorsilestscindéen3comp osantes

connexes:{a},{g,c},{e,f,d,h,b}.

Notonsquesil'oncalculelafermeturetransitived'ungrapheconnexe,onobtientungraphe

complet.Demême,sil'oncalculelafermeturetransitived'ungraphecomp ortantkcomp osantes

connexes,onobtientungraphecontenantksous-graphescomplets(unp ourchaquecomp osante

connexe).

3.6Forteconnexité

Casdesgraphesorientés:Onretrouvecesdiérentesnotionsdeconnexitésdanslesgraphes

orientés,enremplaçantnaturellementlanotiondechaineparcelledechemin:onparledegraphe

fortementconnexeaulieudeconnexe,decomp osantefortementconnexeaulieudecomp osante

connexe.

Dénition1.23Undigrapheestditfortementconnexesientretoutepairedesommets,il

existeunchemindexi versxj etunchemindexj versxi .

SoitG=(X,U)ungraphe.Siquelsquesoientxi ,xj ∈X,ilexisteunchemindexi versxj etun

chemindexj versxi ,alorslegrapheestfortementconnexe.Sinonondénitdescomp osantes

fortementconnexes.

3.CONNEXITÉDANSLESGRAPHES19

Exemple1.13

Dénition1.24Onapp ellecomp osantefortementconnexetoutsous-grapheinduitmaximal

fortementconnexe(maximalsigniequ'iln'yapasdesous-grapheinduitconnexeplusgrand

contenantlessommetsdelacomp osante).

Exemple1.14Parexemple,legrapheorientésuivantcontient2comp osantesfortementsconnexes:

lapremièreestlesous-graphedéniparlessommets{a,b,c,d}etlasecondeestlesous-graphedéni

parlessommets{e,f,g}.

Commep ourlesgraphesnonorientés,unefaçondedéterminersiungrapheorientéestfortement

connexeconsisteàcalculersafermeturetransitive:silafermeturetransitivedugrapheestlegraphe

complet,alorsilestfortementconnexe.

Exemple1.15Revenonsàl'exempledugraphe1.12,achacunedessousmatricescarréesunités

delamatriceA+A2 +A3 +A4 +A5 corresp ondunecomp osantefortementconnexe:{A,B,F}et

{C,D,E,G}sontlesensemblesdesommetsdesdeuxcomp osantesfortementconnexesdugraphe

delagure1.12.

[DeuxièmeChapitre\

Leproblèmedupluscourtchemin

Lesproblèmesdecheminementdanslesgraphes(enparticulierlarecherched'unpluscourt

chemin)comptentparmilesproblèmeslesplusanciensdelathéoriedesgraphesetlesplusimp ortants

parleursapplications.

OnseplacedanslecasdesgraphesorientésvaluésG=(X,U).Maislesrésultatsetalgorithmes

présentéssegénéralisentfacilementauxcasdesgraphesnonorientésvaluésentransformantle

graphenon-orientéenungrapheorientéenremplaçantunearêteentredeuxsommetspardeuxarcs

desensinverseentrecessommets.

Dénition2.1SoitG=(X,U)ungraphevalué ;onasso cieàchaquearcu=(i,j)unelongueurd(u)oud i j

.Leproblèmedupluscourtcheminentreietjconsisteàtrouveruncheminμ(i,j)

deiàjtelque:d(μ)= ∑u∈μ d(u)soitminimale.

Interprétationded(μ) :coûtdetransp ort,dép ensedeconstruction,tempsnécessairedepar-

cours,...

Danslarecherched'unpluscourtchemindexày,troiscasp euventseprésenter:

•Iln'existeaucunchemindexày(parexemple,sixetyappartiennentàdeuxcomp osantes

fortementconnexesdiérentesdeG).

•Ilexistedescheminsdexàymaispasdepluscourtchemin.

•Ilexisteunpluscourtchemindexày.

Exemple2.1Onconsidèrelegraphesuivant:Ilexistedescheminsdexày(etmêmeuneinnité),

maisiln'existepasdepluscourtchemindexày(ilsutd'emprunterlecycledep oidsnégatif

autantdefoisquenécessaire).Ilexisteunpluscourtchemindexàzmaispasdechemindezàx.20 1.LESPLUSCOURTSCHEMINSD'UNSOMMETÀTOUSLESAUTRES21

Dénition2.2Uncircuitdelongueurnégativeestapp elécircuitabsorbant.

Etalors,uneconditionnécessaireetsusanted