[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= Xx2P d(x)+ Xx2I d(x)

Or2jAjet

Xx2P d(x) sontdes entierspairs, onendéduitalors que Xx2I d(x) est également pair, comme différence de deux entiers pairs. Chaque terme de cette dernière somme est impair, elle ne peut donc être paire que si et seule- ment si le nombre de termes est pair, on a donc montré que jIjest un entier pair. b. Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié avec exactement trois autres ? Considérons le graphe simple dont les sommets sont les 15 ordinateurs, les arêtes étant les liaisons entre ces ordinateurs. Si chaque appareil est relié à exactement 3 ordinateurs du réseau, les sommets du graphe sont tous de degré impair. D"après le résultat établi dans l"exercice précédent, un tel graphe doit posséder un nombre pair de sommets, le réseau est donc impossible. c. Montrer que le nombre total de gens qui ont habité la Terre et qui ont donné un nombre impair de poignées de mains est pair. Considérons le graphedontles sommets sont les gens quionthabité laTerreet dont les arêtes représentent les poignées de mains échangées entre ces person- nes. La réponse à la question découle immédiatement du résultat du premier exercice.

B.2 Graphes orientés

1.Définition

Un grapheorientéGest forméde deuxensembles : unensembleX=fx1 ;x2 ;:::;xn g dont les éléments sont appelés sommets, et un ensembleA=fa1 ;a2 ;:::;am g, partie du produitcartésien XX, dont les éléments sont appelésarcs. On notera

G=(X; A).

Sia=(x; y)est unarcdu grapheG,xest l"extrémitéinitialedeaetyl"extrémité finale de a. 5

Remarque

À tout graphe orienté

G=(X; A);on associe le graphe simple(X; B)où :

fx; yg2B,((x; y)2Aou(y; x)2A))

2.Définition

Soit xun sommet d"un graphe orienté. On noted +(x)le nombre d"arcs ayantx comme extrémité initiale, etd (x)le nombre d"arcs ayantxcomme extrémité finale. Ainsi, on a : d(x)=d +(x)+d (x)quotesdbs_dbs15.pdfusesText_21

[PDF] fonction homogène exercices corrigés

[PDF] fonction homogene economie

[PDF] fonction homogène de degré 0

[PDF] degré d'homogénéité des fonctions de production

[PDF] exercices corrigés d élasticité pdf

[PDF] servuction exemple

[PDF] eldorado laurent gaudé livre pdf

[PDF] lecture analytique eldorado laurent gaudé chapitre 5

[PDF] eldorado le cimetière de lampedusa commentaire

[PDF] lecture analytique eldorado laurent gaudé chapitre 10

[PDF] eldorado analyse

[PDF] lecture analytique eldorado chapitre 1

[PDF] eldorado laurent gaudé texte intégral

[PDF] lecture analytique eldorado laurent gaudé chapitre 13

[PDF] lecture analytique eldorado laurent gaudé chapitre 2