Download Exercice Graphe 3 PDF

TitleExercice Graphe 3
Tags Mathematical Concepts Mathematical Relations Discrete Mathematics Physics & Mathematics
File Size303.7 KB
Total Pages27
Document Text Contents
Page 14

Équipe académique Mathématiques page 14
Bordeaux

2 Agences de voyage



Sept agences de voyage Romaines proposent des visites de monuments et lieux touristiques : Le
Colisée, le Forum romain, Le musée du Vatican et les thermes de Caracalas.
Un même lieu ne peut être visité par plusieurs groupes de compagnies différentes le même jour. La
première Compagnie fait visiter uniquement le Colisée ; la seconde le Colisée et le musée du
Vatican; la troisième les thermes de Caracalas; la quatrième le musée du Vatican et les thermes de
Caracalas ;la cinquième le Colisée et le Forum romain; la sixième le Forum romain et les thermes
de Caracalas ; la septième le musée du Vatican et le forum romain.
Ces agences peuvent-elles organiser les visites sur les trois premiers jours de la semaine ?



Colisée Forum Vatican Thermes
1 X
2 X X
3 X
4 X X
5 X X
6 X X
7 X X






















sommet 2 4 5 6 7 1 3
n° couleur 1 2 2 1 3 3 3



L’algorithme donne trois couleurs.
Le graphe contient un graphe complet d’ordre 3 : 1 2 5 ; on ne pourra pas obtenir moins de trois couleurs.
Le nombre chromatique de ce graphe est donc 3.

Page 26

Équipe académique Mathématiques page 26
Bordeaux

D Corrigés des exercices



Exercices 1, 2 3 & 4

Voir transparents


Exercice 5

Construire un automate permettant de reconnaître une date donnée sous la forme 02/05 (pour le 2 mai), en se
limitant à l’année en cours…







0

0,2

9

1…9

0…9

3

1,3,5,7,8

0…8

0,1,2


/

0
1…9

1 1

2

/

1

0

1,3,4,9

0

1

/

0

1

Similer Documents