Introduction à la théorie des grapheslycee.lagrave.free.fr/IMG/pdf/graphes.pdf · Les graphes Le vocabulaire de base : Un graphe est un sch ema constitu e de sommets dont certain

Introduction a la theorie des graphes

TES specialite

Lycee Beaussier - F.Lagrave

2011/2012

A B C

D

1

4

5

6

7

2 3

Les graphes

Le vocabulaire de base :

Un graphe est un schema constitue desommets dont certain sont relies par des

aretes.A B

C

D

E

F

Les sommets representent des objets et les aretes traduisent des informations entre lesobjets.

Une arete reliant un sommet a lui meme s’appelle une boucle ;

Deux sommets distincts relies par une arete sont dits adjacents ;

Un sommet est isole lorsqu’aucune arete ne le relie aux autres sommets.

http://lycee.lagrave.free.fr (♣) 2 / 22 2011/2012 – TES spe

http://lycee.lagrave.free.fr

Les graphes



aretes.A B

C

D

E

F







Les graphes



aretes.A B

C

D

E

F







Les graphes



aretes.A B

C

D

E

F







Les graphes



aretes.A B

C

D

E

F







Le vocabulaire de base

L’ordre d’un graphe est le nombre de sommets de ce graphe ;

Le degre d’un sommet est le nombre d’extremites d’aretes que l’on comptesur ce sommet (pour une boucle, on compte deux extremites).

Un graphe simple est un graphesans boucle et tel que, entre deuxsommets, il y ait au plus une arete ;

Un graphe complet est un graphesimple dont tous les sommets sontadjacents deux a deux.

AB

CD

E

BA

C

D A

B

C



Le vocabulaire de base

L’ordre d’un graphe est le nombre de sommets de ce graphe ;

Le degre d’un sommet est le nombre d’extremites d’aretes que l’on comptesur ce sommet (pour une boucle, on compte deux extremites).

Un graphe simple est un graphesans boucle et tel que, entre deuxsommets, il y ait au plus une arete ;

Un graphe complet est un graphesimple dont tous les sommets sontadjacents deux a deux.

AB

CD

E

BA

C

D A

B

C



Le vocabulaire de base - graphe complet

Un graphe complet est un graphe simple dont tous les sommets sontadjacents les uns avec les autres.

Dans le graphe complet d’ ordre n , le degre de chacun des sommets est n − 1.

Les graphes complets d’ordre 2, 3, 4 et 5 sont donnes ci-dessous :

Graphe K2 Graphe K3 Graphe K4 Graphe K5



Le vocabulaire de base - graphe complet

Un graphe complet est un graphe simple dont tous les sommets sontadjacents les uns avec les autres.

Dans le graphe complet d’ ordre n , le degre de chacun des sommets est n − 1.

Les graphes complets d’ordre 2, 3, 4 et 5 sont donnes ci-dessous :

Graphe K2 Graphe K3 Graphe K4 Graphe K5



Le vocabulaire de base - graphe oriente

Un graphe oriente est un graphe dont les aretes sont orientees.Une arete orientee va d’un sommet vers un autre sommet, elle est representeepar une fleche.

AB

CD

E

E

D

A

B

C

graphe simple d’ordre 5 ;

sommets : A, B, C, D, E ;

A et B sont adjacentsA et C ne sont pas adjacents ;

E est un sommet isole .

graphe oriente ayant 7 aretes ;

une arete qui part ou arrive en unsommet compte pour 1 ;

au sommet E, une arete arrive de D etla boucle en E a deux extremites en Edonc E est de degre 3



Le vocabulaire de base - graphe oriente

Un graphe oriente est un graphe dont les aretes sont orientees.Une arete orientee va d’un sommet vers un autre sommet, elle est representeepar une fleche.

AB

CD

E

E

D

A

B

C

graphe simple d’ordre 5 ;

sommets : A, B, C, D, E ;

A et B sont adjacentsA et C ne sont pas adjacents ;

E est un sommet isole .

graphe oriente ayant 7 aretes ;

une arete qui part ou arrive en unsommet compte pour 1 ;

au sommet E, une arete arrive de D etla boucle en E a deux extremites en Edonc E est de degre 3



Relation fondamentale entre degres et aretes

Calculer pour chacun des graphes la somme des degres de tous les sommets et lacomparer avec le nombre d’aretes du graphe.

AB

CD

E

BA

C

D A

B

C

sommet degreA 2B 3C 3D 1E 1

total 10

sommet degreA 3B 3C 3D 3

total 12

sommet degreA 3B 3C 2

total 8

nombre d’aretes : 5 nombre d’aretes : 6 nombre d’aretes : 4





AB

CD

E

BA

C

D A

B

C


total 10


total 12


total 8






AB

CD

E

BA

C

D A

B

C


total 10


total 12


total 8






AB

CD

E

BA

C

D A

B

C


total 10


total 12


total 8






AB

CD

E

BA

C

D A

B

C


total 10


total 12


total 8






AB

CD

E

BA

C

D A

B

C


total 10


total 12


total 8





Regle : la somme des degres de tous lessommets d’un graphe est egale a deuxfois le nombre de ses aretes.

Consequence : la somme desdegres de tous les sommets d’ungraphe est un nombre pair.

Cette regle et sa consequence permettent de savoir si un graphe est realisable ou pas, etde prevoir son nombre d’aretes.

Application : un club de foot est forme de cinq equipes :

11 Peut-on organiser des rencontres telles que chaque equipe joue deux matchs ?

22 Meme question si chaque equipe joue trois matchs ?






























Decrire un graphe

Le plan ci-contre represente le reseau despistes cyclables desservant certains sitesd’une agglomeration.

1. Construire le graphe associe a ce reseau.

Salle de sport

Bibliotheque

Centrecommercial

Ecole

Gare

Piscine



Decrire un graphe

Le plan ci-contre represente le reseau despistes cyclables desservant certains sitesd’une agglomeration.

2. Decrire ce graphe.

Salle de sport

Bibliotheque

Centrecommercial

Ecole

Gare

Piscine



Decrire un graphe

Le graphe ci-contre represente le reseaudes pistes cyclables desservant certainssites d’une agglomeration.

Decrire un graphe, c’est donner sonordre, le nombre des aretes et indiquersi le graphe est simple, oriente ou non

oriente.

S

B

M

E

P

G

Les sommets sont les 6 sites, donc le graphe est d’ordre 6 . Il y a 10 pistes cyclables,donc le graphe comporte 10 aretes . C’est un graphe simple non oriente



Decrire un graphe


Decrire un graphe, c’est donner sonordre, le nombre des aretes et indiquersi le graphe est simple, oriente ou non

oriente.

S

B

M

E

P

G

Les sommets sont les 6 sites, donc le graphe est d’ordre 6 . Il y a 10 pistes cyclables,donc le graphe comporte 10 aretes . C’est un graphe simple non oriente



Decrire un graphe


3. Indiquer dans un tableau le degre dechacun de ses sommets.Le graphe est-il complet ? Justifier.

4. Combien de pistes cyclables lamunicipalite doit-elle construire pour quedeux sites quelconques de l’agglomerationsoient relies directement ?

S

B

M

E

P

G



Resolution

3. Tableau des degres des sommets :

sommet S P B E G Mdegre 2 4 4 4 3 3

Le graphe n’est pas complet, car il existedeux sommets non adjacents S et E parexemple.4. Pour que deux sites quelconques soientrelies directement par une piste cyclable, legraphe doit etre complet.

Dans un graphe complet d’ordre 6,chaque sommet est de degre 5.

S

B

M

E

P

G

Tous les sommets doivent etre de degre 5. La somme des degres des sommets d’ungraphe est alors egale au double du nombre d’aretes.Ainsi, la somme des degres sera 6× 5 = 30, soit un graphe de 15 aretes.La municipalite doit donc construire cinq pistes cyclables supplementaires :trois pistes S-E, S-G et S-M d’extremite S ; une piste P-M d’extremite P ; une piste B-Gd’extremite B.



Exercice

Dans un groupe de six enfants, est-il possible que quatre exactement d’entre eux aientchacun trois amis et que les deux autres aient chacun un ami ?

De meme, est-il possible que trois exactement d’entre eux aient chacun trois amis et lestrois autres aient chacun deux amis ?



Solution

(1) (1)

(3)

(3) (3)

(3)

(3) (3)

(1)

(3) (3)

(1)

4× 3 + 2× 1 = 14

(3) (3)

(2)

(3) (2) ?

(2)

(2) (3)

(1)

(3) (3)

(2)

3× 3 + 3× 2 = 15? 3× 3 + 2× 2 + 1 = 14



Traduire une situation par un graphe

Sept lycees possedent chacun un club de theatre. Ils proposent d’organiser un tournoi dematchs d’improvisation, ou chaque club doit rencontrer cinq autres clubs participants.Traduire par un graphe. L’organisation de ce tournoi est-elle possible ? Sinon proposerune autre organisation du tournoi.

Pour traduire une situation par ungraphe : on indique quels sont lessommets du graphe et ce que representeune arete entre deux sommets.

Pour savoir si on peut construireun graphe, on utilise la regle : lasomme des degres des sommetsd’un graphe est egale au doubledu nombre d’aretes.

On traduit la situation par un graphe non oriente dont les sommets correspondent auxclubs des lycees. Une arete entre deux sommets represente un match entre deux clubs.

Le graphe est non oriente et d’ordre 7Si chaque club rencontre 5 autres clubs, le degre de chaque sommet est 5. Donc lasomme des degres est 7× 5 = 35.Or la somme des degres des sommets d’un graphe et un nombre pair. L’organisation dece tournoi est donc impossible.

Pour qu’elle soit possible entre ces 7 clubs, il faut que le degre de chaque sommet soit unnombre pair , donc chaque club doit rencontrer 2, 4 ou 6 autres clubs.

























































Les chaınes dans un graphe

Definition : Une chaine est une successiond’aretes reliant deux sommets.

La longueur d’une chaıne est lenombre d’aretes qui la composent.


a

b

d

e

c





Une chaıne simple n’utilise pas deux fois lameme arete.

a - b - c est une chaine simple de longueur 2


a

bc

d

e





Une chaıne fermee revient a son point dedepart.

a - b - d - c - b - a est une chaine fermee de longueur 5

Une arete est comptabilisee autant de fois qu’elle apparait dans la chaine.


a

bc

d

e





Un cycle est une chaıne simple fermee.

a - b - d - e - a est une cycle de longueur 4


a

b

d

e

c


Chaınes orientees

Un chemin est une chaıne orientee dans un graphe oriente.

Un circuit est un cycle oriente.

A

C

D

E

F

B

A

C

E

B

GF

A

C

FE

B

G

Chaıne :A - C - D - F - E - D

Chaıne orientee :A → C → E → B → C → E → G

Cycle oriente :A → C → E → B → C → F → E →

G → B → A



Chaınes orientees

Un chemin est une chaıne orientee dans un graphe oriente.

Un circuit est un cycle oriente.

A

C

D

E

F

B

A

C

E

B

GF

A

C

FE

B

G

Chaıne :A - C - D - F - E - D

Chaıne orientee :A → C → E → B → C → E → G

Cycle oriente :A → C → E → B → C → F → E →

G → B → A



Les graphes connexes

Un graphe est connexe s’il existe une chaıne entre deux sommets quelconques.

La distance entre deux sommets d’un graphe connexe est la longueur de la chaıne laplus courte qui les relie ;

Le diametre d’un graphe connexe est la plus grande distance parmi toutes les paires desommets.





Exemple : graphe connexe

a

c

d

b

e

Exemple : graphe non connexe

a

c

d

b

e





Exemple : graphe connexe

a

c

d

b

e

La distance entre les sommets b et dest 2

La distance entre les sommets a et eest 3

Le diametre de ce graphe est 3



Cheminement sur un graphe

Pour chaque figure, peut-on parcourir une fois et une seule toutes les aretes du graphesans lever le crayon ? Si oui, revient-on au point de depart ?Donner, pour chaque graphe, le nombre de sommets de degre impair.

Graphe a :5 sommets et 8 aretes

b

c

a

d

e


b

c

a

d

e


a

bc

de



Cheminement sur un graphe

Pour chaque figure, peut-on parcourir une fois et une seule toutes les aretes du graphesans lever le crayon ? Si oui, revient-on au point de depart ?Donner, pour chaque graphe, le nombre de sommets de degre impair.


b

c

a

d

e

Chaıne simple :d - c - b - e - a - b - d - a - c

b

c

a

d

e

Chaıne fermee :a - c - e - b - d - a

a

bc

de

4 sommets de degre impair 2 sommets de degre impair 0 sommet de degre impair



Theoreme d’Euler

Une chaıne eulerienne est une chaıne quicontient une fois et une seule toutes les

aretes du graphe.

→ Une cycle eulerien est une chaıneeulerienne fermee.

Parcourir une fois et une seule toutes les aretes d’un graphe connexe sans lever lecrayon, revient a chercher une chaıne eulerienne :

Si tous les sommetssont pairs

Possible Depart = Arrivee

S’il existe exactementdeux sommets impairs

Possible Depart = l’un des sommets impairsArrivee = l’autre sommet impair

Dans tous les autres cas Impossible



Theoreme d’Euler - Exemples

Trouvez, si possible une chaıne eulerienne pour les graphes suivants ; l’une d’entre elles,est-elle un cycle eulerien ?

d

c

a

b

f e

db

c

a

b

d

f

a

c

e

d

c

a

b

f e

6 sommets de degre impair

db

c

a

2 sommets de degre impairb - a - d - b - c - d

b

d

f

a

c

e

0 sommet de degre impaira - e - f - b - d - e - c - b - a

Theoreme d’Euler

Un graphe connexe admet une chaıne eulerienne si le nombre de ses sommets dedegre impair est 0 ou 2.

Dans le cas ou il y a exactement deux sommets de degre impair, l’origine etl’extremite de la chaıne seront ces deux sommets.

Dans le cas ou tous les sommets du graphe sont de degre pair, la chaıne eulerienneest alors un cycle eulerien et son depart peut etre n’importe quel point.




d

c

a

b

f e


db

c

a


b

d

f

a

c

e


Theoreme d’Euler







d

c

a

b

f e


db

c

a


b

d

f

a

c

e


Theoreme d’Euler






Prouver l’existence d’un cycle eulerien ou d’une chaıne eulerienne

Peut-on parcourir, une fois et une seule, chacune des aretes de ces graphes sans lever lecrayon ?

Graphe : À

5

2

6

13 4

Graphe : Á

CG

A B

D

FE

Graphe : Â

I

K

H

M

L




Graphe : À

5

2

6

13 4

Le graphe À et connexed’ordre 6. Tous les sommetssont de degre 3, donc cegraphe n’admet pas dechaıne eulerienne.

Graphe : Á

CG

A B

D

FE

Le graphe Á et connexed’ordre 7. Seuls les sommetsC et E sont de degre 3,impair. Le graphe admetune chaıne eulerienned’extremites C et E.C - D - E - F - G - A - B - C - E

Graphe : Â

I

K

H

M

L

Le graphe Â et connexed’ordre 5. Tous les sommetssont de degre pair, donc legraphe admet une cycleeulerien.H - M - L - K - H - L - I - H




Methode

On verifie que le graphe est connexe, puis onrecherche le degre de chacun des sommets.

↓

Si deux sommets seulement sont de degreimpair, alors le graphe admet une chaıne

eulerienne d’extremites ces sommets.

→ Si tous les sommets sont de degrepair, alors le graphe admet un cycle

eulerien.



Mettre en evidence une chaıne eulerienne

Enonce : Dans une region, cinq pays se partagentl’espace geographique. Est-il possible de visiter cespays, en ne traversant qu’une seule fois chaquefrontiere ?

A B

CE

D

Resolution : Le graphe associe est connexe.Degre de chacun des sommets :

sommet A B C D Edegre 3 2 4 2 3

Comme A et E sont les seuls sommets de degreimpair, le graphe admet une chaıne eulerienned’extremites A et E.

C

A B

ED



Mettre en evidence une chaıne eulerienne

Enonce : Dans une region, cinq pays se partagentl’espace geographique. Est-il possible de visiter cespays, en ne traversant qu’une seule fois chaquefrontiere ?

A B

CE

D

Resolution : Le graphe associe est connexe.Degre de chacun des sommets :

sommet A B C D Edegre 3 2 4 2 3

Comme A et E sont les seuls sommets de degreimpair, le graphe admet une chaıne eulerienned’extremites A et E.

C

A B

ED



Methode pour determiner une chaıne eulerienne entre deux sommets

Pour determiner une chaıne eulerienne entre deuxsommets :

1 On choisit l’un des sommets et on decrit uncycle qui retourne a ce sommet ;On efface alors les aretes parcourues dans cecycle et les sommets qui se trouvent isoles ;

2 On choisit un des sommets utilises dans lecycle precedent, et on decrit un autre cycle ;

3 on � soude � les deux cycles par le sommetcommun ;

4 s’il ne reste pas d’aretes, le cycle obtenu est uncycle eulerien ;s’il reste une seule arete, on obtient une chaıneeulerienne.

A B

CE

D

C

A B

ED









Pour decrire une chaıne, on choisitde partir de A :

on prend le cycle A - B - C - Apuis on efface les aretesparcourues et le sommet isoleB

C

A B

ED










on choisit le cycle C - E - D -C , puis on efface les aretesparcourues et les sommetsisoles C et D

C

A

ED










il ne reste plus de cycle, maisune seule arete A - E.Donc le graphe admet pourchaıne eulerienne :A - B - C - E - D - C - A - E

A

E










le graphe admet pour chaıneeulerienne :A - B - C - E - D - C - A - EOn peut donc visiter ces paysen traversant une seule foischaque frontiere.

C

A B

ED



Documents

Introduction à la théorie des grapheslycee.lagrave.free.fr/IMG/pdf/graphes.pdf · Les graphes Le vocabulaire de base : Un graphe est un sch ema constitu e de sommets dont certain