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

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


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


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


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 ?


4.4. Les dominosLes dominos


6.6. PlatonPlaton


ModélisationModélisation


SommetAdjacents

Ordre

VocabulaireVocabulaire

8

1

9

5



IsoléPendant

9

7

6

4

32

10

ArêteDegré


d(x5)=48

1

9

5



9

7

6

4

32

10

Différents types de graphesDifférents types de graphes

Graphe simple


Multi-graphe


Graphe connexe


Graphe non connexe


Graphe complets1 2

2

K2

K3

K


13

1

2

34

1

2

3

4

5

K3

K4

K5


1 2

3 4

5 6

Graphe bipartite


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


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


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


?

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

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

des hexagones ou


2.2. Le ballon de Le ballon de

footfoot


des hexagones ou pentagones réguliers.

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

pentagones et d'hexagones?

footfoot




6.6. PlatonPlaton


H HP



H H

HH

HH

H

H

P

PP

PP

Qu’est-ce qu’un graphe planaire?

1 2

1 2


3

4 5

3

4 5


1 2


3

4 5



Non planaires

2

6

C

Face ou régionFace ou région

Faces


1

3

4 5

A B

S – A + F = 2

Formule Formule d'Eulerd'Euler


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 +


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.


2P5H6 +

3P5H6 + P+H- + = 2

P = 12P = 12

Une autre relation intéressante

5P = 3H5P = 3H


5P = 3H5P = 3H

12

Solution


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 ?


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 .


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

Tout graphe acyclique Tout graphe acyclique est planaireest planaire

2


1 3

45

6

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

2

• Planaires jusqu'à l'ordre 4 :


13

1

2

34

• Non planaire à partir de l'ordre 5:

4

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


1

2

3

5

• De type K1,n sont planaires :

3

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


1

2

3

45

6

7

• De type K2,n sont planaires :

12

3

3

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


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.


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


1

2

4

5

12

3

5

6

ConséquenceConséquence

36 4


1

2

4

5

1

2

3

5

Pas suffisantPas suffisant

4

7 8 4

expansion


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


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



3.3. La carte de La carte de


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

ggééoo



6.6. PlatonPlaton




Coloration d’un grapheColoration d’un graphe

Graphe planaire


ColorationColoration

B O

M

B O

M

B O

O


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


1

2

4

cycle élémentaire cycle élémentaire

1 3

4

4

Nbre pair de sommets� χ=2


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.


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


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


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


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:


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

Tout graphe planaire est


Tout graphe planaire estcoloriable en 4 couleurs.

AutresAutres applicationsapplications dede lalacolorationcoloration dede graphesgraphes



Est-il possible d’aligner toutes





d’aligner toutes les pièces d’un

domino en respectant la continuité ?



6.6. PlatonPlaton


: sommets 0, 1, …, 6

: arête



1

13

3

4

4cycle eulcycle euléérienrien

K7


2

25

5

66 70

cycle 1

12

2

36

Graphe eulérienGraphe eulérien


3

4

45

5

6

1

12

2

36

Graphe eulérienGraphe eulérien


cycle eulérien

3

4

45

5

6

Léonhard Euler (1707-1783)


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

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


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


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


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

cycle c2

3 4

6

d(x)=5 → impair


1

2 5


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





6.6. PlatonPlaton


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


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.


sont de degré impair.

DessinonsDessinons

1

12

2

3

34

4

5 5

1

12

2

3

34

4

5 5

1 2

34


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


51

6

2

43

3 463 46

34

1

2 3

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


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

ballade sur des polyèdres

platoniciens. Existe -t-il un chemin






Existe -t-il un chemin qui lui permette de

visiter une seule fois chaque sommet ?



6.6. PlatonPlaton


DéfinitionDéfinition

o Polyèdre

polyèdre polyèdre


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


Le dodécaèdre L’icosaèdre

Le cubeLe cube


�

Le tétraèdreLe tétraèdre


�

L’octaèdreL’octaèdre


�

Le dodécaèdreLe dodécaèdre


�

L’icosaèdreL’icosaèdre


�

Cycle HamiltonienCycle Hamiltonien

1 2


34

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

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

1


1

2

3

4

5

6


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


hamiltonien. 1

2

3

4

5


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

2


1

2

3

45

Autres propriétésAutres propriétés

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


Corolaire de Diracd(x) ≥n/2

Conditions suffisantesConditions suffisantes

Mais non

nécessaires !


1 2

3

45

Pas completPas OrePas Dirac

Le cubeLe cube

78

Ne répond à aucune propriété.

Pourtant, voici un cycle hamiltonien:


1 2

3 4

5 6

Le tétraèdreLe tétraèdre

Graphe de type K4

Voici un cycle hamiltonien:


L’octaèdreL’octaèdre

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

1Voici un cycle hamiltonien:


2 3

4 56

Le dodécaèdreLe dodécaèdre

Ne répond à aucun critère.



L’icosaèdreL’icosaèdre

Ne répond à aucun critère.


1


2 3

4

5

67

8 9

10

11

12

La course du cavalierLa course du cavalier


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


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


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


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


é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






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 ?



6.6. PlatonPlaton

7.7.Le circuitLe circuit



arêtes à sens unique!

DiDi--graphegraphe


1010

Matrice d’adjacenceMatrice d’adjacence

S1 S2 S3 S4

S


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


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


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

1220

2120

2010

Chemins de 500 m

S2

S3

S4


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

2120S1 S2 S3 S4

S1


Chemins de 500 m

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

1120

1210

2010

2120 S1

S2

S3

S4


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

3230

S1 S2 S3 S4

S1


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


Le voyageur de Le voyageur de

commercecommerce

H F


2

10

41

poidspoids


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


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


H

D C

F

2

2

1

10

6 4

3

H

D C

F

2

2

1

10

6 4

3

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞


B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞


H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞2222DDDD


B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞1111DDDD


H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB


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


H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH

12121212HHHH


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


H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH

12121212HHHH9999CCCC


B

D C A

E

1

2

1

12

37

3

B

D C A

E

1

2

1

12

37

3

0000

∞∞∞∞

∞∞∞∞

∞∞∞∞

1111DDDD13131313BBBB10101010CCCC


H F

2 1

10

6 4

H F

2 1

10

6 4

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH


13131313FFFF


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


H

D C

F

2

2

1

10

6 4

3

H

D C

F

2

2

1

10

6 4

3

∞∞∞∞

∞∞∞∞

∞∞∞∞

∞∞∞∞

2222DDDD

4444BBBB3333HHHH


13131313FFFF11111111EEEE


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


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


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


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

$$ $$


$$ $$

En conclusionEn conclusion

• Claude BERGE


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

théorie moderne des graphes.









Logiciel

•GRIN40– Téléchargement

Gratuit


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

Documents

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