El' ements de Th' eorie des Graphes

Description

INSTITUT NATIONAL POLYTECHNIQUE DE LORRAINE
Ecole Nationale Superieure d’Electricite et de Mecanique
Elements de Theorie des Graphes
Didier Maquin
Version provisoire du 3 mai 2003Table des matieres
Avant propos 4
1 Un bref historique de la theorie des graphes 4
2 Introduction 6
2.1 Qu’est-ce qu’un graphe? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Graphes et applications multivoques . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Principales de nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Modes de representation d’un graphe 9
3.1 Listes de succession . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Etude de la connexite 11
4.1 Cha^ nes et cycles, elementaires et simples . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Chemins et circuits, elementaires et . . . . . . . . . . . . . . . . . . . . . 12
4.3 Graphes et sous-graphes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4 et fortement connexes . . . . . . . . . . . . . . . . . . . . . 13
4.5 Cycles et nombre cyclomatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5 Parcours euleriens et hamiltoniens 15
5.1 Cha^ nes et cycles euleriens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2 Cha^ ...

Sujets

• dictionnaire
• cours

Informations

• Publié par: Vikub
• Nombre de lectures: 110
• Langue: Français

Extrait

INSTITUT NATIONAL POLYTECHNIQUE DE LORRAINE EcoleNationaleSupe´rieured’Electricit´eetdeMe´canique

El´ementsdeTh´eoriedesGraphes

DidieraMuqni

Version provisoire du 3 mai 2003

Table des ti` s ma ere Avant propos 1Unbrefhistoriquedelath´eoriedesgraphes 2 Introduction 2.1 Qu’est-ce qu’un graphe ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Graphes et applications multivoques . . . . . . . . . . . . . . . . . . . . . . . . . 2.3Principalesd´efinitions................................. 3Modesderepr´esentationd’ungraphe 3.1 Listes de succession . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Etude de la connexite ´ 4.1Chˆnesetcycles,´el´ementairesetsimples...................... aı 4.2Cheminsetcircuits,´ele´mentairesetsimples..................... 4.3 Graphes et sous-graphes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Graphes et sous-graphes fortement connexes . . . . . . . . . . . . . . . . . . . . . 4.5 Cycles et nombre cyclomatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Parcourseul´eriensethamiltoniens 5.1Chaˆınesetcycleseul´eriens............................... 5.2 Chaınes et cycles hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˆ 6Me´thodederecherchedechemins 6.1Rappelsurlesop´erationsbool´eesurlesmatrices................ nnes 6.2 Recherche de chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3Leprobl`emedupluscourtchemin.......................... 7 Arbres et arborescences 7.1De´finitionsetproprie´te´s................................ 7.2 Arbres couvrants de poids minimum . . . . . . . . . . . . . . . . . . . . . . . . . 8Re´seaux,reseauxdetransportetproble`mesdeflots ´ 8.1De´finitions........................................ 8.2 Recherche d’un flot complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3Am´eliorationduflot.................................. 8.4 Recherche d’un flot maximal : algorithme de Ford et Fulkerson . . . . . . . . . . 8.5Exempletraite´manuellement............................. 8.6Recherched’unflotmaximal`acoˆutminimal..................... 9 Couplages 9.1Leproble`meducouplagemaximal.......................... 9.2 Couplage maximal et flot maximal . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Couplage de poids maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4Probl`emesd’affectation................................

3

4 4 6 6 7 8 9 9 10 11 11 11 12 12 13 14 15 15 17 18 18 19 20 23 23 24 26 26 27 28 29 29 32 32 33 35 36 37

10Probl`emesd’ordonnancement 10.1Legraphepotentielstaˆches................ - 10.2Legraphepotentiels-´etapesougraphePERT...... 10.3 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 10.4Comple´ments........................

Annexe A -iondel’algorithmdeMeooerD-jiskrtalpmIeme´tatn

Annexe B -yodedlFhtemogir´lpmIall’deontitaenem

Annexe C -l´emImp’ledoglaatnenoitimPrthrideme

R´efe´rences

4

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

40 41 42 43 44

46

50

52

53

Avant propos ”Fautt’faireundessin?”.Larepr´esentationd’unproble`meparundessin,unplan,une esquissecontribuesouventa`sacompre´hension.Lelangagedesgraphesestconstruit,`al’ori- gine,surceprincipe.Nombresdeme´thodes,depropri´ete´s,deproce´duresonte´t´epens´eesou trouv´eesa`partird’unsch´emapourˆetreensuiteformalise´esetd´evelopp´ees.Chacund’entrenous a,aumoinsunefois,vuouutilise´unplandem´etro,unecartedelignesferroviaires,unplan ´letrique,unarbreg´ene´alogiqueouunorganigrammed’entreprise;ainsi,toutlemondesait e c plusoumoinsintuitivementcequ’estungraphe.Toutefois,entrecettenotionvagueo`udes points,repre´sentantdesindividus,desobjets,deslieuxoudessituations,sontrelie´spardes fle`ches,ilyaunelonguee´laborationdesconcepts.Lapremie`redifficulte´a`laquelleonpeutˆetre confront´econcernelaterminologie(t`bondanteenth´eoriedesgraphes).Nousavonsdonc res a choisid’isolerlesprincipalesde´finitionsduresteducoursenutilisantunemiseenpagediffe´rente. Lath´eoriedesgraphesconstitueaujourd’huiuncorpusdeconnaissancestre`simportant. Commesonnoml’indique,cecoursneconstitueradoncqu’uneintroduction`acettethe´orie.Nous lepre´ciseronsulte´rieurement,led´eveloppementdecettethe´oriedoitbeaucoupa`celuidescalcu- lateurs.Ilnousadoncsembl´eincontournabled’exposerquelquesalgorithmesdebase(recherche de chemin, d’arbre, de flots, etc.). Cependant, ceci ne constitue pas le corps de cet enseignement memesilesproble`mespratiquesdemiseenœuvresontimportants.Nousn’´evoqueronspas,par ˆ exemple,l’optimalit´edetelleoutellerepre´sentationd’ungrapheauregarddutraitementque l’onsouhaiteeffectuer,nilacomplexite´(ausensnombred’ope´rations´el´ementaires)desalgo- rithmes.Demanie`rea`permettreaulecteurint´eresse´dejugerdesdifficult´esdemiseenœuvre desalgorithmes“litt´eraux”,plusclairspourlacompre´hension,d´ecritsdanslecorpsdutexte, quelquesimple´mentationsa`l’aidedulangageMatlab r  sont d fonctions ne Ces ´ onnes en annexe. pr´etendentnullementa`eˆtreefficacesouefficientessurdesdonne´esquelconques;ellesnesont donne´esqu’a`titred’illustration.Demeˆme,nousnoussommesefforce´sceciter,aumomentde l’introductiondesm´ethodesdebase,lesfonctionsdelaboˆıte`aoutilsdemanipulationdegraphes Metanetdu logiciel Scilab c  qui leur correspondent.

1Unbrefhistoriquedelathe´oriedesgraphes Toutlemondes’accorde`aconsid´ererquelatheoriedesgraphesestne´een1736avecla ´ communicationd’Euler(1707-1783)danslaquelleilproposaitunesolutionauc´el`ebreproble`me despontsdeKo¨nigsberg(Euler,1736).Leprobl`emepose´e´taitlesuivant.DeuxıˆlesAetD surlarivi`erePregel`aK¨onigsberg(alorscapitaledelaPrussedel’Est,aujourd’huirebaptisee ´ Kaliningrad)e´taientreli´eesentreellesainsiqu’auxrivagesBetCa`l’aidedeseptponts(de´signe´s par des lettres minuscules) comme le montre la figure 1.

Fig.L–1flıdeltˆ’piohKeeni`erarivgeleePre

5