[PDF] [PDF] Théorie des graphes DUT Informatique, semestre 2

[PDF] Introduction à la théorie des graphes - Apprendre-en-lignenet

– Des exercices pratiques où il peut être avantageux d'utiliser des graphes pour modéliser et résoudre un problème CAHIERS DE LA CRM No 6 · 1 Page 6 

[PDF] Résumé du cours de théorie des graphes 1 Notions de base 2

Deux graphes isomorphes ont les mêmes propriétés : même nombre de sommets et d'arêtes, mêmes degrés, Le graphe complet est le graphe simple ` a n 

[PDF] Théorie des Graphes

2 fév 2015 · Malgré ce contenu plus avancé, le livre est organisé de telle sorte qu'un cours d' introduction `a la théorie des graphes puisse se baser sur les 

[PDF] Théorie des graphes DUT Informatique, semestre 2

3 fév 2014 · du cours magistral, et prendre le temps de refaire les exercices types qui L' ensemble des fiches pdf du cours de théorie des graphes (TD1 `a 

[PDF] Cours 1 : Thorie des graphes

Cours 1 : Théorie des graphes Maîtrise en Informatique Un graphe simple est un ensemble fini de sommets et d'arcs (i e : Arêtes) défini comme des couples 

[PDF] Stage olympique de Saint-Malo Cours - Théorie des graphes

U n ar b re est un graphe connexe et sans cycle Notons alors que dans un arbre , il n'existe qu'un seul chemin entre deux sommets donnés ( il y en 

[PDF] Théorie des graphes et optimisation dans les graphes Table - CNRS

Exercice : Au cours d'une soirée, les convives se serrent les mains les uns les autres (jamais plusieurs fois avec la même personne) Chacun se souvient du 

[PDF] Chapitre 13 Théorie des graphes

Un graphe non orienté est dit connexe s'il y a un chemin entre n'importe quelle paire de sommets Un graphe orienté est dit connexe si, en transformant ses arcs

[PDF] Théorie des graphes Introduction Programme de Terminale ES

Dans tout livre de Terminale ES spécialité, vous trouverez de nom- breux exercices et des méthodes pratiques (Déclic, Hyperbole, ) N'hésitez pas `a les 

[PDF] INTRODUCTION A LA THEORIE DES GRAPHES - Aix - Marseille

Sinon, la coloration est terminée Application : Utiliser cet algorithme pour colorer les graphes des exercices précédents IV DECRIRE ET COMPTER LES 

[PDF] cours théorie générale du droit constitutionnel maroc

[PDF] cours thermodynamique statistique mp

[PDF] cours tourisme gratuit

[PDF] cours transaction immobilière

[PDF] cours transaction immobilière bts pi

[PDF] cours transfert thermique pdf

[PDF] cours transport routier pdf

[PDF] cours trigonométrie pdf

[PDF] cours trigonométrie première s

[PDF] cours tva maroc pdf

[PDF] cours typologie des textes narratifs s1 pdf

[PDF] cours ue4 paces pdf

[PDF] cours univ paris 1

[PDF] cours vanne

[PDF] cours vba excel 2013 pdf

Th´eorie des graphes

DUT Informatique, semestre 2

Version 2.0

3 f´evrier 2014

Ph. Roux

2009-2014

2

Table des mati`eresTable des mati`eres3

Origines historiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1 Diff´erentes notions de graphes . . . . . . . . . . . . . . . . . . . . . . 7

1.1 Relations binaires . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Relation dans un ensemble . . . . . . . . . . . . . . . . . . . . 16

1.3 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.4 Autres types de graphes . . . . . . . . . . . . . . . . . . . . . 23

1.5 Quelques probl`emes courants de th´eorie des graphes . . . . .30

2 Chemins dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.1 D´efinitions et premiers exemples . . . . . . . . . . . . . . . . . 35

2.2 graphes Euleriens et Hamiltoniens . . . . . . . . . . . . . . . . 37

2.3 Parcours de graphes orient´es . . . . . . . . . . . . . . . . . . . 46

3 Probl`emes d"optimisation pour des graphes valu´es . . . . . . . . . .. 54

3.1 Arbre couvrant optimal . . . . . . . . . . . . . . . . . . . . . 54

3.2 Probl`eme du plus court chemin . . . . . . . . . . . . . . . . . 56

3.3 Ordonnancement et gestion de projet . . . . . . . . . . . . . . 64

3.4 Flots dans les r´eseaux . . . . . . . . . . . . . . . . . . . . . . 70

4 Notions de th´eorie des langages . . . . . . . . . . . . . . . . . . . . . 81

4.1 Alphabets, langages et grammaires formelles . . . . . . . . . . 81

4.2 Langages r´eguliers et automates Finis . . . . . . . . . . . . . . 86

4.3 Langages alg´ebriques . . . . . . . . . . . . . . . . . . . . . . . 98

5 Metanet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

5.1 L"´editeur de graphes metanet . . . . . . . . . . . . . . . . . . 100

5.2 Chargement d"un graphe dansScicoslab. . . . . . . . . . . . 104

5.3 Variable de typegraphdansScicoslab. . . . . . . . . . . . . 106

5.4 Quelques fonctions pour les graphes . . . . . . . . . . . . . . . 112

5.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Bibliographie120

Liste des Exercices121

3

Avertissement

Pour bien utiliser ce polycopi´e, il faut le lire au fur et `a mesure de l"avancement du cours magistral, et prendre le temps de refaire les exercices types qui y sont propos´es. •Les d´efinitions et th´eor`emes sont num´erot´es suivant le mˆeme ordre que dans le cours magistral. Th´eor`eme 0.0.0les th´eor`emes apparaissent toujours dans un cadre gris´e comme

celui-ci et sont en g´en´eral suivis de leur d´emonstration, signal´ee par une barre dans

la marge et un?`a la fin comme ci-dessous :

Preuve :D´ebut de la d´emonstration ...

...fin de la d´emonstration •La table des mati`eres et l"index (`a la fin du document) permettentde retrou- ver une notion pr´ecise dans ce polycopi´e. •Les m´ethodes et techniques qui seront approfondies en TD sontsignal´ees par un cadre (sans couleurs) •Des exercices types corrig´es,r´edig´es comme vous devriez le faire enDS, sont signal´es par le symbole : •Les erreurs et les confusions les plus fr´equentes sont signal´ees dans des cadres rouges avec le symbole : •Vous ˆetes libre de r´eutiliser le contenu de ce document sous les termes de la licence CC-BY-NC-SA [11] 4 DUT InformatiqueTh´eorie des graphesMath´ematiques

Origines historiques

Les math´ematiques fournissent de puissants outils pour mod´eliser des probl`emes de toutes sortes : •les structures bool´eennes pour les probl`emes de logique (?,?,¬, =?, ...) •les ensembles pour repr´esenter des collections d"objetsN,R,R2,Mp,n(R) ... •les fonctions, d´eriv´ees, int´egrales pour r´ealiser des calculs ... Mais ses outils sont insuffisants, mˆeme `a notre niveau, pour pouvoir mod´eliser des probl`emes d"apparence pourtant assez simple. Un bon exemple de ce type de probl`eme peut ˆetre trouv´e dans le domaine des bases de donn´ees : comment mod´eliser les liens entre des objets pris dans diff´erents ensembles?? Pour cela nous avons besoin d"un nouveau type d"objet math´ematiques :les graphes. Par rapport aux autres th´eories math´ematiques ´etudi´ees `a l"IUT, la th´eorie des graphes est assez r´ecente. L"article consid´er´e comme fondateur de la th´eorie des graphes fut pr´esent´e par le math´ematicien suisse Leonhard Euler `a l"Acad´emie de Saint P´etersbourg en 1735, puis publi´e en 1741, et traitait du probl`eme des sept ponts de K¨onigsberg. Le probl`eme consistait `a trouver une promenade `a partir d"un point donn´e qui fasse revenir `a ce point en passant une fois et une seule par chacun des sept ponts de la ville de K¨onigsberg. Au milieu duXIXi`eme, c"est le?th´eor`eme des quatre couleurs?qui va po- pulariser dans le monde des math´ematiques cette th´eorie peu connue jusque l`a. Ce th´eor`eme affirme qu"on a besoin que de quatre couleurs diff´erentes pour colo- rier n"importe quelle carte g´eographique de telle sorte que deux r´egions limitrophes (ayant toute une fronti`ere commune) re¸coivent toujours deux couleurs distinctes. Le r´esultat fut conjectur´e en 1852 par Francis Guthrie, int´eress´e par la coloration de la carte des r´egions d"Angleterre, mais ne fˆut d´emontr´e qu"en 1976 par deux Am´ericains Kenneth Appel et Wolfgang Haken. Leur d´emonstration de ce th´eor`eme fut la premi`ere `a utiliser un ordinateur pour ´etudier les 1478 casparticulier aux quels se ram`ene le probl`eme des quatre couleurs critiques ce quin´ecessita plus de

1200 heures de calcul!

C"est donc auXXi`emeque cette th´eorie va connaˆıtre son v´eritable essor avec l"utilisation croissante dans la vie quotidienne des r´eseaux dont il faut optimiser l"utilisation constamment : •r´eseaux de transport routier, transport d"eau, d"´electricit´e •r´eseaux de transport de donn´ees (r´eseau de t´el´ephonie fixe, GSM, wifi ...) •r´eseaux d"informations (bases de donn´ees, web, r´eseaux sociaux ...) Cette th´eorie est devenue fondamentale en informatique car elle fournit de nombreux algorithmes pour r´esoudre des probl`emes complexes repr´esent´es par des graphes de tr`es grande taille (plusieurs centaines, milliers,... de sommets et d"arcs!). 5 DUT InformatiqueTh´eorie des graphesMath´ematiques

Figure1 - les 7 ponts de K¨onigsberg

Figure2 - une carte g´eographique colori´ee avec 4 couleurs seulement 6 DUT InformatiqueTh´eorie des graphesMath´ematiques

1 Diff´erentes notions de graphes

1.1 Relations binaires

La notion de graphe repose avant tout sur la notion derelation binaire, pour l"introduire nous allons commencer par prendre un exemple de la vie courante. ?1.1 Emploi du tempsUn emploi du temps met en relation des jours (ou des cr´eneaux horaires) et des mati`eres (et ´eventuellement des enseignants, des salles

ArchiSyst`emeAlgoMathsEGO

AlgoSyst`emeAnglaisECEGO

ArchiArchiAlgoAlgoMaths

AlgoECMaths

On est donc en pr´esence de deux ensembles de donn´ees dans cet exemple : les jours de la semaine et Les mati`eres enseign´ees. Mais il y a une donn´ee suppl´ementaire qu"on ne peut pas repr´esenter par un ensemble : la relation qui existe entre les jours et les mati`eres. On peux l"exprimer simplement par la phrase : une mati`ere est en relation avec les jours de la semaine o`u elle est enseign´ee? On peut essayer de repr´esenter ces liens sur un diagramme enles repr´esentant par des fl`eches comme sur la figure FIG.3. On se rend alors facilement compte qu"on ne peut pas mod´eliser ces liens en utilisant des fonctions ou des applications d"un des ensembles vers l"autre. On a besoin d"une notion plus g´en´erale ... Sport Archi Algo

Syst`eme

Anglais

EC EGO

MathsLundi

Mardi

Mercredi

Jeudi

V endredi

Samedi

Dimanche

Mati`eresRJours

Figure3 - Relations entre les mati`eres et les o`u elles sont enseign´ees 7 DUT InformatiqueTh´eorie des graphesMath´ematiques D´efinition 1.1 (Relation binaire)SoientEetFdeux ensembles alors ?Rest une relation deEversF?siRest la donn´ee d"un triplet d"ensembles (E,F,U)tel queU?E×F. •On dit que?xest en relation avecy?si et seulement si(x,y)?Uce qui sera not´exRy •Au contraire si?xn"est pas en relation avecy?on ´ecrirax?Ry •On repr´esentera une relationR= (E,F,U)par un diagramme sagittal (ou diagramme fl´ech´e) pour cela : - on dessine les diagrammes de Venn des ensemblesEetF - chaque couple(x,y)?Uest repr´esent´e par une fl`eche allant dex`ay Pour des raisons pratiques on utilisera le vocabulaire suivant pour d´esigner les diff´erents ensembles associ´ees `a la d´efinition de relation binaire: D´efinition 1.2 (Lexique de la th´eorie des graphes) Pour une relationR, d´efinie par le triplet(E,F,U), telle quexRyon dira : •Eest l"ensemble de d´epart,Fcelui d"arriv´e etUcelui des arcs. •xest le pr´ed´ecesseur dey, on dit aussi l"origine de(x,y) •l"ensemble des pr´ed´ecesseurs deyestΓ-(y) •d-(y) = CardΓ-(y)est le degr´e entrant eny

•le domaine deR:DR={x?E| ?y?F,(x,y)?U}

•yest le successeur dex, on dit aussi l"extr´emit´e de(x,y)

•l"ensemble des successeurs dexestΓ+(x)

•d+(x) = CardΓ+(x)est le degr´e sortant dex

•l"image deR:ImR={y?F| ?x?E,(x,y)?U}

Il est tr`es facile de retenir le sens de certaines de ces notions en pensant `a la repr´esentation graphique de la relation par un diagramme sagittal(ensembles de d´epart et d"arriv´e, successeurs, pr´ed´ecesseur) Mais d"autres sont moins faciles `a retenir (domaine, image, degr´e). Il faut donc bien retenir ces d´efinitions d`es main- tenant. ?1.2 Exprimer ces diff´erents ensembles pour la relation de laFIG.3

•D´epart :E={Sport;Archi;Algo;...;Maths}

•Arriv´ee :F={Lundi;Mardi;Mercredi;...;Dimanche} •Arcs :U={(Archi,Lundi);(Archi,Mardi);...;(Maths,V endredi)}

•Domaine :DR=E\ {sport}

•Image :ImR=F\ {Samedi;Dimanche}

•Γ+(Maths) ={Jeudi;V endredi}=?d+(Maths) = 2

•Γ-(Jeudi) ={Maths;EC;Algo}=?d-(Jeudi) = 3

8 DUT InformatiqueTh´eorie des graphesMath´ematiques On peut aussi rapprocher ce vocabulaire du vocabulaire utilis´es pour les fonctions et applications qui sont en fait des cas particuliers de relations! ?1.3 Cas des fonctions et applicationsreprendre les d´efinitions du cours de th´eorie des ensembles concernant les fonctions et applications du point de vue des relations binaires :

Fonctionsune fonctionf:E-→Fest une relation

xRy??f(x) =y R´eciproquement, une relationRest une fonction si chaque ´el´ement deE`a au plus un successeur ApplicationsUne relationR:E-→Fest une application si et seulement si :

•Rest une fonction

•Son domaine de d´efinition est ´egal `aE ce qui s"exprime en langage des relations binaires par ?x?E,Card(Γ+(x)) = 1?? ?x?E, d+(x) = 1 Application injective surjective, bijectiveSoitf:E-→Fune application, on dit quefest •injective si chaque ´el´ement deF`a au plus un pr´ed´ecesseur •surjective si chaque ´el´ement deF`a au moins un pr´ed´ecesseur ?y?F,Card(Γ-(y))≥1?? ?y?F, d-(y)≥1

•bijective si elle est injective et surjective

?y?F,Card(Γ-(y)) = 1?? ?y?F, d-(y) = 1 ?Ces d´efinitions ont une grande importance en base de donn´ees, elles sont direc- tement li´ees aux cardinalit´es qui apparaissent dans un MCD. Ellespermettent

d"expliquer pourquoi :•Une relation fonctionnelle qui apparaˆıt dans un MCD n"aura pas de table

propre •Une relation bijective ne devrait jamais apparaˆıtre dans un MCD 9 DUT InformatiqueTh´eorie des graphesMath´ematiques ?1.4 Reconnaˆıtre `a partir des diagramme sagittaux les d´efinitions pr´ec´edentes : reconnaˆıtre les fonctions et les applications des autres relations: 1 2 3 4a b c d e EhF 1 2 3 4 5a b c d e Eg F 1 2 3 4 5a b c d EfF

•getfsont des fonctions

•fest une application mais pasg(card+(5) = 0ou encoreDg=E\{5} ?= E) •ethn"est pas une fonction (card+(5) = 2) donc pas une application reconnaˆıtre injectivit´e, surjectivit´e et bijectivit´e: 1 2 3 4a b c d e Ef 1F 1 2 3 4 5a b c d Ef 2F 1 2 3 4 5a b c d e Ef 3F ce sont bien des applications et : •f1est injective mais pas surjective (`a cause ded-(e) = 0) •f2est surjective mais pas injective (`a cause ded-(d) = 2)

•seulef3est bijective

On retrouve sur ces exemples les r´esultats du th´eor`eme suivant :

Th´eor`eme 1.3

SoientE,Fdes ensembles finis etf:E-→Fune application alors

•sifest surjective alorsCard(E)≥Card(F)

•sifest bijective alorsCard(E) = Card(F)

10 DUT InformatiqueTh´eorie des graphesMath´ematiques Le diagramme sagittal permet de d´etecter de nombreuses propri´et´es d"une re- lation binaire, `a condition qu"il n"y ait pas trop d"arc ni d"´el´ements. Pour pou- voir analyser les propri´et´es de graphes de grandes tailles nous avons besoin d"une repr´esentation qui permette de faire des calculs : une matrice.

D´efinition 1.4 (matrice d"adjacence)

SoientE={x1;x2;...;xp},F={y1;y2;...;yn}etR= (E,F,U)une relation alors on appelle matrice d"adjacence deRla matrice bool´eenneMR?Mp,n(B)telle que M

R= (mi,j)avecmi,j=?1si(xi,yj)?U

0sinon

?Pour pouvoir ´ecrire la matrice d"adjacence d"une relation il faut avoir choisi un ordre pour les ´el´ements des ensemblesEetF(il sont num´erot´esx1,x2,... pourEety1,y2,...pourF). Ce choix est arbitraire, mais il n"est pas indiqu´e dans la matrice d"adjacence!On prendra donc (sauf mention contraire) l"ordrequotesdbs_dbs50.pdfusesText_50