(Microsoft PowerPoint - théorie des graphes-ISL- partie1)

��

��

��

��

��

��

7 Défis7 Défis7 Défis7 Défis��

��

� �� !�!��

"�"��

!�!��

#�#�$��$��

��

%�%��%�%��

��

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

��la bise, en, France,

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

��

��

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

� ��

"�"�� personnes qui ont habité la terre et qui

ont donné un nombre impair de

!�!��

#�#�$��$�� nombre impair de bises est-il pair ou

impair ?

#�#�$��$��

��

��

impair ?

ModélisationModélisationModélisationModélisation

��

VocabulaireVocabulaireVocabulaireVocabulaireVocabulaireVocabulaireVocabulaireVocabulaire

��

�

�

�

�

�

��

�

�

�

��

�

��

��

VocabulaireVocabulaireVocabulaireVocabulaireVocabulaireVocabulaireVocabulaireVocabulaire

��

��

�

�

�

�

��

�

�

��

��

Différents types de graphesDifférents types de graphesDifférents types de graphesDifférents types de graphes

��

!��"��

��

!��"��


��

��

��

��


��#��$% ��#��1 2

2

$%

$&$

13

2

$&$�

34

4 $�1

13

��

2 5


1 2

4

��'��3 4

5 6

71 2

3 43 4

5

��#'��#��#�#$%(&�

��

Deux propriétésDeux propriétésDeux propriétésDeux propriétésLa somme des degrés des sommets d’un graphe est

égale à deux fois son nombre d’arêtes.égale à deux fois son nombre d’arêtes.� d(x) = 2 A

5

5

4

4

61

12

2 6

6

8

3

7 78

8

��

33

Deux propriétésDeux propriétésDeux propriétésDeux propriétés

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

5

5

Σd(x)=2A 4

4

6

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

1

12

2 6

6

8��

3

7 78

8��

��

33

ProblèmeProblème concretconcretProblèmeProblème concretconcret

?

��

Défi nDéfi n��22Défi nDéfi n��22��

Le ballon de football est un polyèdre dont

��

�� est un polyèdre dont toutes les faces sont

des hexagones ou

��

�� des hexagones ou pentagones réguliers.

Sans les compter,

��

� ��

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

pentagones et d'hexagones?

"�"��

!�!��d'hexagones?

#�#�$��$��

��

��

��


H HP

H H

HH

PPP

HH H

H

H

PPH

��

Qu’est-ce qu’un graphe planaire?planaire?

1 2

1 2

33

4 54 54 5

��


1 2

3

4 5

��


3

6

10

14

15

27

11 13Non planaires48

11 13Non planaires1

5

9

12

16

��

Face ou régionFace ou régionFace ou régionFace ou région

)��2

)��

6 C

1

3A B

4 54 5

��

Formule Formule d'Eulerd'EulerFormule Formule d'Eulerd'Euler

S – A + F = 2S – A + F = 2• S = nombre de

sommets

* +�

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

�

* + • F = nombre de faces

��

�

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

P5H6 +Nombre d'arêtes =

2P5H6 +

Nombre de sommets = 3

P5H6 +

Nombre de faces =

3

P+HNombre de faces = P+H

��

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

S – A + F = 2problème.problème.

S – A + F = 2

P5H6 +P5H6 + P+H� � �2

P5H6 +3

P5H6 + P+H� � �

��

��

��

5P = 3H5P = 3H5P = 3H5P = 3H5P = 3H5P = 3H

��

��

��

��

Critères de planaritéCritères de planaritéCritères de planaritéCritères de planaritéY a-t-il un moyen de Y a-t-il un moyen de

déterminer si une représentation de graphe 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!

sous-graphes non planaires �� Graphe non planaire

��

Théorème admisThéorème admisThéorème admisThéorème admis

Soit G un graphe Soit G un graphe planaire et connexe avec n ��3 sommets. avec n ��3 sommets. Alors G contient au Alors G contient au plus 3n − 6 arêtes.

��

Tout graphe acyclique Tout graphe acyclique est planaireest planaireest planaireest planaire

�� 2

1 3

6

45

��

45

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

�2

• Planaires jusqu'à l'ordre 4 :

13

� 2�

34

��

1

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

��Non planaire à partir de l'ordre 5:��Non planaire à partir de l'ordre 5:

� 4�

13 13

2 5

��

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

• De type K1,n sont planaires : • De type K1,n sont planaires : �

3

2

3

7

16

45

��

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

� �� ! �� "�

�3

� �� !#� �� "� 12

� 3

4

�

12 56

4

��

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

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

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

� 36

2 5

1 41 4

��

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

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

� 36 4�

2

3

2 5

12 6

1 4 5

��

ConséquenceConséquenceConséquenceConséquence

�� 36 � 4

2 5

13

1 4 2 5

��

Pas suffisantPas suffisantPas suffisantPas suffisant

expansion 4

�

expansion 4

7 8 � 4

13

13

2 5

6 9

102 5

��

Théorème de KuratowskiThéorème de KuratowskiThé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

��


Combien de couleurs au

��

�� couleurs au minimum faut-il

pour colorer chaque pays de la

��

� ��

chaque pays de la carte d’Europe de telle sorte que 2

��

"�"��telle sorte que 2 pays voisins ne soient pas de la

"�"��

!�!�� soient pas de la même couleur ?

!�!�

#�#�$��$��

��

��

��


��

Coloration d’un grapheColoration d’un grapheColoration d’un grapheColoration d’un graphe

Graphe planaire

��

ColorationColorationColorationColoration

MMO

B OB O

M

B O

O BO BR V O B

5 couleurs 3 couleurs suffisent

Coloration incorrectesuffisent incorrecte

nombre chromatique χ(G)

��

nombre chromatique χ(G)

Nombre chromatique de Nombre chromatique de graphes complets Kgraphes complets Kgraphes complets Kgraphes complets Knn

3 χχχχ=nVoici K4χ=4χ=4

1 4

2

��

cycle élémentaire cycle élémentaire cycle élémentaire cycle élémentaire

4 Nbre pair de sommets� χ=2

1 3

4

� χ=2

4

25

1 3

Nbre impair de sommets2

Nbre impair de sommets� χ=3

…��

…

L’algorithme de Welsh et Powell.Powell.

�� $��%��&�'(�)��* * ��+��,�� (��* %��-$��%��&�'(�)��* * ��+��,�� (��* %��-

1

��

Sommets Degrés

S1

S2�

��

.� ��+�,��+��.� ��+�,��+��

'(�)��* * ��-'(�)��* * ��-

S2

S3

S4 �

�

S4

S5

S6

�

�

�

S7

S8

S9

�

�

�S9

S10

S11

�

�

�S11

S12

S13

�

1 S14

S15

S16

�

�

�

��

S16 �

Degré Sommets

8 S10��

/��* * ��+��,�� (��+��/��* * ��+��,�� (��+��

�0��+��+�'��+��+�,��0��+��+�'��+��+�,��

8 S10

5 S6

5 S3

��

�0��+��+�'��+��+�,��0��+��+�'��+��+�,��4 S5

4 S8

4 S154 S15

4 S9

3 S43 S4

3 S11

2 S22 S2

2 S7

2 S12

1

1 S1

1 S14

1 S16

��

1 S16

0 S13

Degrés Sommets Couleurs

8 S10�� 8 S10

5 S6

5 S3

��$��%��+��'��$��%��+��'��

4 S5

4 S8

4 S154 S15

4 S9

3 S43 S4

3 S11

2 S2

1

2 S2

2 S7

2 S121 1 S1

1 S14

1 S16

��

1 S16

0 S13

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

��

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

Tout graphe planaire estTout graphe planaire estcoloriable en 4 couleurs.coloriable en 4 couleurs.

��

AutresAutres applicationsapplications dede lalacolorationcoloration dede graphesgraphes

AutresAutres applicationsapplications dede lalacolorationcoloration dede graphesgraphes

��


�� Est-il possible

d’aligner toutes

��

� �� d’aligner toutes les pièces d’un

domino en respectant la

"�"��

!�!� respectant la continuité ?

!�!��

#�#�$��$��#�#�$��$��

��

��


: sommets 0, 1, …, 6: sommets 0, 1, …, 6

: arête

��

4�&��&��

1

4

4

$,

1

13

3

66 70

22

55

��

2 5

Graphe eulérienGraphe eulérien

1 2


'�'�� 1

12

2

3636

45 44

55

��


1 2


1

12

2

3636

45

'�'��4

45

5

��

'�'��

Léonhard Euler (1707-1783)(1707-1783)

��

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

��

��

��

�� .�� .

��

+123 ��4 ��

4

4

+123 ��4 ��

1

13

3

4

66 70

66 7

22

55

��

'�'��'� '�'��'�6

'�'��'� '�'��'�

5

6

7 5

6

7

7

2

3

3

4

2

14

14

'�'��'� '�'��'�'�'��'��6

'�'��'� '�'��'�'�'��'��

5

77

3

2

14

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

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

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

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

��

+123 ��4 ��* ��6

+123 ��4 ��* ��

3 4

1

2 5

��

Documents

(Microsoft PowerPoint - théorie des graphes-ISL- partie1)