th orie des graphes - UCLouvain · Gaston LagRafarrive, Faites Graphe àvous! pour découvrir la...

Gaston Gaston LagRafLagRaf arrive,arrive,Gaston Gaston LagRafLagRaf arrive,arrive,Faites Graphe Faites Graphe àà vous!vous!

pour dpour déécouvrir la couvrir la

ththééorie des graphesorie des graphes7 d7 dééfisfis

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

7 Défis7 Défis1.1. Les bisesLes bises

2.2.Le ballon de footLe ballon de foot

3.3.La carte de gLa carte de gééoo 5.5. Le dessinLe dessin

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

3.3.La carte de gLa carte de gééoo

4.4.Les dominosLes dominos

5.5. Le dessinLe dessin

6.6. PlatonPlaton

7.7. Le circuitLe circuit

8.8. ........

Défi nDéfi n°°°°°°°°11En Belgique, on ne se fait qu’une fois la bise, en, France,

2, 3, 4 fois, cela dépend de…heu,

1.1. Les bisesLes bises

2.2. Le ballon de footLe ballon de foot

3.3. La carte de gLa carte de gééoo

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

dépend de…heu, bref, le nombre de personnes qui ont

habité la terre et qui ont donné un

nombre impair de bises est-il pair ou

impair ?

3.3. La carte de gLa carte de gééoo

4.4. Les dominosLes dominos

5.5. Le dessinLe dessin

6.6. PlatonPlaton

7.7. Le circuitLe circuit

ModélisationModélisation

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

SommetAdjacents

Ordre

VocabulaireVocabulaire

8

1

9

5

VocabulaireVocabulaire

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

IsoléPendant

9

7

6

4

32

10

ArêteDegré

VocabulaireVocabulaire

d(x5)=48

1

9

5

VocabulaireVocabulaire

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

9

7

6

4

32

10

Différents types de graphesDifférents types de graphes

Graphe simple

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Multi-graphe

Différents types de graphesDifférents types de graphes

Graphe connexe

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Graphe non connexe

Différents types de graphesDifférents types de graphes

Graphe complets1 2

2

K2

K3

K

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

13

1

2

34

1

2

3

4

5

K3

K4

K5

Différents types de graphesDifférents types de graphes

1 2

3 4

5 6

Graphe bipartite

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

71 2

3 4

5

Graphe bipartite complet ( K2,3)

La somme des degrés des sommets d’un graphe est égale à deux fois son nombre d’arêtes.

∑ d(x) = 2 A5

5

Deux propriétésDeux propriétés

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

12

2

33

4

4

6

6

7 78

8

Le nombre de sommets de degré impaird'un graphe est pair.

5

5

Deux propriétésDeux propriétés

Σd(x)=2A

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

12

2

33

4

4

6

6

7 78

8

Σd(x)=2A Σd(x)= Σdi(x)+ Σdp(x)

pairs

ProblèmeProblème concretconcret

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

?

Défi nDéfi n°°°°°°°°22

Le ballon de football est un polyèdre dont toutes les faces sont

des hexagones ou

1.1. Les bisesLes bises

2.2. Le ballon de Le ballon de

footfoot

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

des hexagones ou pentagones réguliers.

Sans les compter, combien y a-t-il de

pentagones et d'hexagones?

footfoot

3.3. La carte de gLa carte de gééoo

4.4. Les dominosLes dominos

5.5. Le dessinLe dessin

6.6. PlatonPlaton

7.7. Le circuitLe circuit

H HP

ModélisationModélisation

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

H H

HH

HH

H

H

P

PP

PP

Qu’est-ce qu’un graphe planaire?

1 2

1 2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

3

4 5

3

4 5

Qu’est-ce qu’un graphe planaire?

1 2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

3

4 5

Qu’est-ce qu’un graphe planaire?

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Non planaires

2

6

C

Face ou régionFace ou région

Faces

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

3

4 5

A B

S – A + F = 2

Formule Formule d'Eulerd'Euler

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

A

B C

D

• S = nombre de sommets

• A = nombre d'arêtes • F = nombre de faces

Résolution de notre Résolution de notre problème.problème.

Nombre d'arêtes =2

P5H6 +

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Nombre de sommets =

Nombre de faces =

3P5H6 +

P+H

S – A + F = 2

P5H6 +P5H6 + P+H- + = 2

Résolution de notre Résolution de notre problème.problème.

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

2P5H6 +

3P5H6 + P+H- + = 2

P = 12P = 12

Une autre relation intéressante

5P = 3H5P = 3H

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

5P = 3H5P = 3H

12

Solution

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

20

Critères de planaritéCritères de planarité

Y a-t-il un moyen de déterminer si une

représentation de graphe est celle d’un graphe

planaire ?

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

planaire ?

Graphe planaire →→→→ sous -graphes planaires

sous-graphes non planaires →→→→ Graphe non planaireRéciproque fausse!

Théorème admisThéorème admis

Soit G un graphe planaire et connexe avec n ����3 sommets .

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

avec n ����3 sommets . Alors G contient au plus 3n − 6 arêtes .

Tout graphe acyclique Tout graphe acyclique est planaireest planaire

2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1 3

45

6

Les graphes complets Les graphes complets sont ...sont ...

2

• Planaires jusqu'à l'ordre 4 :

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

13

1

2

34

• Non planaire à partir de l'ordre 5:

4

Les graphes complets Les graphes complets sont ...sont ...

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

3

5

• De type K1,n sont planaires :

3

Les graphes bipartites Les graphes bipartites complets... complets...

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

3

45

6

7

• De type K2,n sont planaires :

12

3

3

Les graphes bipartites Les graphes bipartites complets ... complets ...

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

4

12

4

56

36

Les graphes bipartites... Les graphes bipartites... Les graphes bipartites Les graphes bipartites

completscomplets ……

de type Kde type K3,33,3 ne sont pas planaires.ne sont pas planaires.

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

4

5

36

Les graphes bipartites... Les graphes bipartites... Les graphes bipartites …Les graphes bipartites …

Pourtant, ses sousPourtant, ses sous--graphes le sont!graphes le sont!

4

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

4

5

12

3

5

6

ConséquenceConséquence

36 4

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

4

5

1

2

3

5

Pas suffisantPas suffisant

4

7 8 4

expansion

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

3

5

6 9

10

1

2

3

5

Théorème de KuratowskiThéorème de Kuratowski

Un graphe fini est planaire si et seulement

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Un graphe fini est planaire si et seulement s'il ne contient pas de sous-graphequi soit une expansion de K5 ou K3,3

Défi nDéfi n°°°°°°°°33Combien de couleurs au

minimum faut-il pour colorer

chaque pays de la

1.1. Les bisesLes bises

2.2. Le ballon de footLe ballon de foot

3.3. La carte de La carte de

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

chaque pays de la carte d’Europe de telle sorte que 2 pays voisins ne soient pas de la même couleur ?

ggééoo

4.4. Les dominosLes dominos

5.5. Le dessinLe dessin

6.6. PlatonPlaton

7.7. Le circuitLe circuit

ModélisationModélisation

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Coloration d’un grapheColoration d’un graphe

Graphe planaire

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

ColorationColoration

B O

M

B O

M

B O

O

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

O BR V O B

5 couleurs 3 couleurs suffisent

Coloration incorrecte

nombre chromatique χ(G)

Nombre chromatique de Nombre chromatique de graphes complets Kgraphes complets Knn

3 χχχχ=nVoici K4χ=4

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

4

cycle élémentaire cycle élémentaire

1 3

4

4

Nbre pair de sommets� χ=2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

25

1

2

3

4

Nbre impair de sommets� χ=3

…

Étape 1Étape 1 Attribuer à chaque sommet du graphe un nombre.Attribuer à chaque sommet du graphe un nombre.

L’algorithme de Welsh et Powell.

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

Repérer le degré de Repérer le degré de

chaque sommet.chaque sommet.

Sommets Degrés

S1

S2

S3

S4

S5

S6

S7

S8

S9

3

5

4

6

2

4

4

1

2

Étape 2Étape 2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

S9

S10

S11

S12

S13

S14

S15

S16

4

8

3

2

0

1

4

1

Classer les sommets du graphe dans Classer les sommets du graphe dans

l’ordre décroissant de leur degrél’ordre décroissant de leur degré

Degré Sommets

8 S10

5 S6

5 S3

4 S5

4 S8

4 S15

4 S9

3 S4

Étape 3Étape 3

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

3 S4

3 S11

2 S2

2 S7

2 S12

1 S1

1 S14

1 S16

0 S13

Degrés Sommets Couleurs

8 S10

5 S6

5 S3

4 S5

4 S8

4 S15

4 S9

3 S4

Étape 4Étape 4Attribution des couleursAttribution des couleurs

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

3 S4

3 S11

2 S2

2 S7

2 S12

1 S1

1 S14

1 S16

0 S13

Voici le résultat:Voici le résultat:

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Théorème des Théorème des 44 couleurscouleurs

Tout graphe planaire est

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Tout graphe planaire estcoloriable en 4 couleurs.

AutresAutres applicationsapplications dede lalacolorationcoloration dede graphesgraphes

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Défi nDéfi n°°°°°°°°44

Est-il possible d’aligner toutes

1.1. Les bisesLes bises

2.2. Le ballon de footLe ballon de foot

3.3. La carte de gLa carte de gééoo

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

d’aligner toutes les pièces d’un

domino en respectant la continuité ?

4.4. Les dominosLes dominos

5.5. Le dessinLe dessin

6.6. PlatonPlaton

7.7. Le circuitLe circuit

: sommets 0, 1, …, 6

: arête

ModélisationModélisation

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

13

3

4

4cycle eulcycle euléérienrien

K7

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

2

25

5

66 70

cycle 1

12

2

36

Graphe eulérienGraphe eulérien

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

3

4

45

5

6

1

12

2

36

Graphe eulérienGraphe eulérien

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

cycle eulérien

3

4

45

5

6

Léonhard Euler (1707-1783)

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Un graphe simple connexe G=(X ,A) est eulérien si et

Théorème d’EulerThéorème d’Euler

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

G=(X ,A) est eulérien si et

seulement si tous ses sommets

sont de degré pair.

∀∀∀∀ x ∈∈∈∈ X, d(x) est pair.

1

13

3

4

4

d(x)=6 → pair

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

2

25

5

66 70

5

6

7 5

6

7

cycle c1 cycle c2

1

2

3

4

1

2

3

4

5

6

7

cycle c1 cycle c2 cycle c3

1

2

3

4

0 -1 – 2 – 3 – 4 – 5 – 6 – 0

cycle c1

cycle c2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

0 – 1 – 3 – 6 – 2 – 1 – 2 – 3 – 4 – 5 – 6 – 0

cycle c2

3 4

6

d(x)=5 → impair

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2 5

Défi nDéfi n°°°°°°°°55

Est-il possible de tracer ces figures sans lever le crayon et sans repasser

1.1. Les bisesLes bises

2.2. Le ballon de footLe ballon de foot

3.3. La carte de gLa carte de gééoo

5.5. Le dessinLe dessin

6.6. PlatonPlaton

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

deux fois par le même trait ?

4.4. Les dominosLes dominos 7.7. Le circuitLe circuit

Extension Extension du théorème ddu théorème d’’’’’’’’EulerEuler

Degrés impairs

Degrés impairs

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

12

2

3

34

4

5 5

Degrés impairs

Degrés pairs

Degrés pairs

ThéorèmeThéorème

Un graphe simple est semi-eulérien ssi

au plus 2 de ses sommets sont de degré impair.

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

sont de degré impair.

DessinonsDessinons

1

12

2

3

34

4

5 5

1

12

2

3

34

4

5 5

1 2

34

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2 3

5

4

3 43 4

1

2

3

DessinonsDessinons

1

12

2

3

34

5 5

6

1

12

2

3

34

5 5

6

1 2

34

1 2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

51

6

2

43

3 463 46

34

1

2 3

les 7 ponts de les 7 ponts de KönigsbergKönigsberg

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Défi nDéfi n°°°°°°°°66Une fourmi se

ballade sur des polyèdres

platoniciens. Existe -t-il un chemin

1.1. Les bisesLes bises

2.2. Le ballon de footLe ballon de foot

3.3. La carte de gLa carte de gééoo

4.4. Les dominosLes dominos

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Existe -t-il un chemin qui lui permette de

visiter une seule fois chaque sommet ?

4.4. Les dominosLes dominos

5.5. Le dessinLe dessin

6.6. PlatonPlaton

7.7. Le circuitLe circuit

DéfinitionDéfinition

o Polyèdre

polyèdre polyèdre

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

o Convexe

o Régulier

polyèdre polyèdre platonicienplatonicien

Il en existe 5Il en existe 5Le cube Le tétraèdre L’octaèdre

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Le dodécaèdre L’icosaèdre

Le cubeLe cube

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

�

Le tétraèdreLe tétraèdre

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

�

L’octaèdreL’octaèdre

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

�

Le dodécaèdreLe dodécaèdre

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

�

L’icosaèdreL’icosaèdre

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

�

Cycle HamiltonienCycle Hamiltonien

1 2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

34

Propriété nPropriété n°°11

Un graphe possédant un sommet de degré 1 ne peut être hamiltonien.

1

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

3

4

5

6

Propriété nPropriété n°°22

Si un sommet dans un graphe est de degré 2, alors, les deux arêtes incidentes à ce sommet doivent faire partie du cycle hamiltonien.

1

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

hamiltonien. 1

2

3

4

5

Propriété nPropriété n°°33

Les graphes complets Kn sont hamiltonienslorsque n est supérieur à 3.

2

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1

2

3

45

Autres propriétésAutres propriétés

Théorème d’Ore d(x) + d(y) ≥n

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Corolaire de Diracd(x) ≥n/2

Conditions suffisantesConditions suffisantes

Mais non

nécessaires !

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1 2

3

45

Pas completPas OrePas Dirac

Le cubeLe cube

78

Ne répond à aucune propriété.

Pourtant, voici un cycle hamiltonien:

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1 2

3 4

5 6

Le tétraèdreLe tétraèdre

Graphe de type K4

Voici un cycle hamiltonien:

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

L’octaèdreL’octaèdre

Ore � Pour tout x, y , d(x)+d(y)=8>6

1Voici un cycle hamiltonien:

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

2 3

4 56

Le dodécaèdreLe dodécaèdre

Ne répond à aucun critère.

Pourtant, voici un cycle hamiltonien:

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

L’icosaèdreL’icosaèdre

Ne répond à aucun critère.

Pourtant, voici un cycle hamiltonien:

1

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

2 3

4

5

67

8 9

10

11

12

La course du cavalierLa course du cavalier

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Il y a des millions de solutions!

Euler et la symétrieEuler et la symétrie

37 62 43 56 35 60 41 50

44 55 36 61 42 19 34 59

63 38 53 46 57 40 51 48

≠ → 32

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

54 45 64 39 52 47 58 33

1 26 15 20 7 32 13 22

16 19 8 25 14 21 6 31

27 2 17 10 29 4 23 12

18 9 28 3 24 11 30 5

≠ → 32

Carrés semiCarrés semi--magiquesmagiques

1 30 47 52 5 28 43 54

48 51 2 29 44 53 6 27

31 46 49 4 25 8 55 42

50 3 32 45 56 41 26 7

260

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

50 3 32 45 56 41 26 7

33 62 15 20 9 24 39 58

16 19 34 61 40 57 10 23

63 14 17 36 21 12 59 38

18 35 64 13 60 37 22 11

260

130

130

Et tout cela grâce à Et tout cela grâce à Hamilton!Hamilton!

L’L’icosianicosian gamegame

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

William Rowan Hamilton

Aujourd’hui encore, la Aujourd’hui encore, la théorie des graphes théorie des graphes hamiltonienshamiltoniens n’a pas n’a pas

été percée à jour et les été percée à jour et les

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

été percée à jour et les été percée à jour et les recherches continuent recherches continuent

toujours dans ce toujours dans ce domaine.domaine.

Défi nDéfi n°°°°°°°°77Un parcours de santé est aménagé pour les sportifs dans le parc de la ville. Il

est composé de chemins en sens unique, et de repères

tous distants de 500

1.1. Les bisesLes bises

2.2. Le ballon de footLe ballon de foot

3.3. La carte de gLa carte de gééoo

4.4. Les dominosLes dominos

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

tous distants de 500 mètres, comme indiqué sur

la figure ci-contre. Tout trajet commence en S1 et

se termine en S4. Combien y a-t-il de trajets

différents de 1.5 Km ? 2.0 Km ? 2.5 Km ?

4.4. Les dominosLes dominos

5.5. Le dessinLe dessin

6.6. PlatonPlaton

7.7.Le circuitLe circuit

ModélisationModélisation

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

arêtes à sens unique!

DiDi--graphegraphe

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

1010

Matrice d’adjacenceMatrice d’adjacence

S1 S2 S3 S4

S

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

M.=M.=M.=M.=

0110

1010

1000

1010 S1

S2

S3

S4

ThéorèmeThéorème

Soit G(X,A), un digraphe, avec X = {x1; x2 : : : ;xn}

de matrice d’adjacence M(G) =(mi,j).Notons Mk=(m(k)i,j )

Alors m vaut

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Alors m(k)i,j vaut

le nombre de chemins de longueur k, différents, allant du sommet xi au sommet xj .

2010

2120

Résolution du problèmeRésolution du problème

Trajets différents de 1.5 Km de l’entrée S 1 à la sortie S 4 ?

S1 S2 S3 S4

S1

S

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

M.M.M.M.3333====

1220

2120

2010

Chemins de 500 m

S2

S3

S4

Résolution du problèmeRésolution du problème

Trajets différents de 2 Km de l’entrée S 1 à la sortie S 4 ?

2120S1 S2 S3 S4

S1

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Chemins de 500 m

M.M.M.M.4444====

1120

1210

2010

2120 S1

S2

S3

S4

Résolution du problèmeRésolution du problème

Trajets différents de 2,5 Km de l’entrée S 1 à la sortie S 4 ?

3230

S1 S2 S3 S4

S1

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Chemins de 500 m

3120

3230

3220

3230

M.M.M.M.5555====S2

S3

S4

Un dernier problèmeUn dernier problème

Le plus court cheminLe plus court chemin

Le voyageur de Le voyageur de

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Le voyageur de Le voyageur de

commercecommerce

H F

Le plus court cheminLe plus court chemin

2

10

41

poidspoids

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

D A

B

D C A

E

2

1

1

3

6

12

73

1

OptimiserOptimisertempstempsdistancedistance coûtcoût

Algorithme de DijkstraAlgorithme de Dijkstra

GloutonGlouton

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Edsger Wybe Dijkstra (1930-2002)

GloutonGlouton

Affecter la valeur de

poids 0 au sommet αααα

Affecter la valeur P=∞∞∞∞aux autres sommets

Sélectionner le sommet X

non encore sélectionné

de poids minimumY a-t-il d’autres

Non

Oui

Y a-t-il des sommets X non sélectionnés?

Oui

Pour tout sommet Y adjacent à X,

calculer p=poids de X+poids de l’arête X-Y

P > pAffecter la valeur

de p à P

Choisir un sommet Y non sélectionné

Y a-t-il d’autres

sommets Y

adjacents à X?

Non Oui

Oui

La plus courte chaîne de αααα à ωωωω est obtenue

en écrivant de droite à gauche le chemin partant de ωωωω

Non

Le plus court cheminLe plus court chemin

H

D C

F

2

2

1

10

6 4

3

H

D C

F

2

2

1

10

6 4

3

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞

Le plus court cheminLe plus court chemin

H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞2222DDDD

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞1111DDDD

Le plus court cheminLe plus court chemin

H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

B

D C A

E

1

2

1

12

3

6

7

3

B

D C A

E

1

2

1

12

3

6

7

3

0000

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

1111DDDD

4444BBBB

13131313BBBB

Le plus court cheminLe plus court chemin

H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH

12121212HHHH

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

1111DDDD

4444BBBB

13131313BBBB

3333HHHH

Le plus court cheminLe plus court chemin

H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH

12121212HHHH9999CCCC

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞

∞∞∞∞

1111DDDD13131313BBBB10101010CCCC

Le plus court cheminLe plus court chemin

H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH

12121212HHHH9999CCCC

13131313FFFF

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

B

D C A

E

1

2

1

12

3

6

7

4

3

B

D C A

E

1

2

1

12

3

6

7

4

3

0000

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

1111DDDD

4444BBBB

13131313BBBB

3333HHHH

10101010CCCC

13131313FFFF

Le plus court cheminLe plus court chemin

H

D C

F

2

2

1

10

6 4

3

H

D C

F

2

2

1

10

6 4

3

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH

12121212HHHH9999CCCC

13131313FFFF11111111EEEE

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞

1111DDDD13131313BBBB10101010CCCC

E ACHD

Traveling Salesman Problem ou TSP

1) Par tous les points d’un parcours,

Le voyageur de commerce

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

d’un parcours,

2) Sans passer deux fois au même endroit,

3) Par le trajet le plus court.

N villes reliées entre elles

Ville départ →→→→n-1 chemins

Traitement en1 ns

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Ville départ →→→→n-1 cheminsEtape 2 →→→→n-2 chemins

…(n-1)!/2

Nombre de villes n

Nombre de trajets

Temps de traitement

Traitement en1 ns

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

10 (9!) / 2 = 181 440 1,8.10-4 s

100(99!) / 2

= 4,7.10155

4,7.10146 s

Soit environ 4,7.10139 années

$$ $$

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

$$ $$

En conclusionEn conclusion

• Claude BERGE

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

• Claude BERGE• Le « père » de la

théorie moderne des graphes.

En conclusionEn conclusion

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

En conclusionEn conclusion

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

En conclusionEn conclusion

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

En conclusionEn conclusion

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

Logiciel

•GRIN40– Téléchargement

Gratuit

ThThééorie des graphes ISL Marcheorie des graphes ISL Marche--enen--FamenneFamenne

– Coloration– Chemin eulérien– Chemin le plus court– …