[PDF] Introduction à la théorie des graphes

View - Download Introduction à la théorie des graphes

Previous PDF

Next PDF

Introduction à la théorie des graphes

Eric Sigward

e.sigward@ac-nancy-metz.fr

Introduction2

Définitionsetpremiersexemples2

Terminologie7

Élémentsdelathéoriedesgraphes9

LesgraphesenTerminaleES34

Exercices35

Solutionsdesexercices38

Complément:lesarbres43

1

A Introduction

L"histoire de la théorie des graphes débute peut-être avec les travaux d"Euler au XVIII e siècle et trouveson originedans l"étudede certains problèmes, tels que celui demandaient s"il était possible, en partant d"un quartier quelconque de la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir à leur point de départ), la marche du cavalier sur l"échiquier ou le problème de coloriage de cartes. La théorie des graphes s"est alors développée dans diverses disciplines telles que la chimie, la biologie, les sciences sociales. Depuis le début du XX e siècle, elle constitue une branche à part entière des mathématiques, grâce aux travaux de De manière générale, un graphe permet de représenter la structure, les connex- ions d"un ensemble complexe en exprimant les relations entre ses éléments : réseau de communication, réseaux routiers, interaction de diverses espèces animales, cir- cuits électriques,... Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande variété de problèmes en se ramenant à l"étude de sommets et d"arcs. Les derniers travaux en théorie des graphes sont souvent effectués par des infor- maticiens, du fait de l"importance qu"y revêt l"aspect algorithmique.

B Définitions et premiers exemples

B.1 Graphes non orientés

1.Définition

Un graphe simpleGest un couple formé de deux ensembles : un ensemble X=fx1 ;x2 ;:::;xn gdont les éléments sont appeléssommets, et un ensemble A=fa1 ;a2 ;:::;am g, partie de l"ensembleP2(X) des parties à deux éléments de X, dont les éléments sont appelé sarêtes. On noteraG=(X; A).

Lorsque

a=fx; yg2A, on dit queaest l"arête deGd"extrémitésxety,ouque ajointxety, ou queapasse parxety. Les sommetsxetysont ditsadjacents dansG. 2

2.Définition

Un multigrapheG=(X ; A; f)est déterminé par : - un ensemble

Xde sommets

- un ensemble

A;cette fois abstrait

- une application f:A!P2 (X) Dans cet exemple,x,y,z,tsont les sommets du multigraphe et :f(a1 )=f(a2 )=f(a3 )=fx; tg;f(a4 )=fx; yg;f(a5 )=fx; zg;f(a6 )=fz; tg; Unmultigraphe avec bouclesest un triplet(X ; A; f)oùfest une application de

AdansP2

(X)[P1 (X);en d"autres termes, un multigraphe avec boucles peut comprendre des arêtes multiples entre deux sommets donnés ainsi que des boucles multiples en un sommet.

3.Exemples:

a. Le graphe d"un tournoi,

T=(X; A)où :

Xest l"ensemble des participants au tournoi

Aest l"ensemble des paires de joueurs se rencontrant dans le tournoi. b. La carte routière de la France,

F=(X; A)où

Xest l"ensemble des villes de la France.

A=ffx; yg=il y a au moins une route directe reliant les villesxetyg: c. Le graphe discret d"ordren,Dn =(X;;): d. Le graphe complet d"ordren,Kn ;oùX=f1;2;:::;ngetA=P2 (X) K1 K2 K3 K4 K5 e. Le graphe biparti-completKp;qoùX=fx1 ;x2 ;:::;xp ;y1 ;y2 ;:::;yq get

A=ffxi

;yj g=16i6pet16j6qg 3 K4;2 f. Le cycleCn,oùX=f1;2;:::;ngetA=ff1;2g;f2;3g;:::;fn1;ng;fn;1gg C4

4.Définition

Soit G=(X; A)un graphe simple, etxun sommet de ce graphe. Ledegré dex, notéd(x), est le nombre d"arêtes incidentes àx;c"est-à-dire contenantx.

Lorsque

d(x)= 0, on dit que le sommetxestisolé, lorsquex=1, il est dit pendant.

Exemples:

si xest un sommet deCn,d(x)=2 sixest un sommet deKn,d(x)=n1

5.Définition

Un graphe simple est dit

régulierde degrér, lorsque tous ses sommets sont de degré r.

6.Lemme des poignées de mains

Soit

G=(X; A)un graphe simple, alors

Xx2X d(x)=2jAj En effet, chaque pairefx; ygdeAest comptée deux fois, une fois pourd(x)et une seconde fois pour d(y):

Remarque

Le lemmedes poignées demains restevalablepourles multigraphesavec boucles en convenant qu"une boucle contribue pour 2 dans le calcul du degré d"un som- met.

7.Exercices

a. Montrer qu"un graphe simple a un nombre pair de sommets de degré impair.

Notons

Pl"ensemble des sommets de degré pair etIl"ensemble des sommets de degré impair d"un graphe simple

G=(X; A):PetIformentune partition

4 deX;d"après le lemme des poignées de mains, on a : Xx2X d(x)=2jAj=quotesdbs_dbs4.pdfusesText_7

[PDF] suite graphique théorie des graphes

[PDF] histoire de la théorie des graphes

[PDF] théorie des graphes cours et exercices corrigés

[PDF] le gone du chaaba analyse

[PDF] le gone du chaaba azouz begag commentaire

[PDF] les différentes théories des organisations

[PDF] théorie des organisations résumé

[PDF] le gone du chaaba texte intégral

[PDF] telecharger le gone du chaaba livre

[PDF] abécédaire le gone du chaaba

[PDF] théorie de perturbation

[PDF] le gone du chaaba livre analyse

[PDF] le gone du chaaba film

[PDF] théorie des plaques exercices

[PDF] exercices corrigés de plaques et coques