Exercice 1:   Marie est très perplexe!  Elle doit sortir samedi soir et choisir pour cela des vétements. Elle dispose dans son armoire de 3 pulls, 3 jupes et 3 paires de chaussures. Mais pour des raisons d'harmonie des couleurs, il y a des incompatibilités entre ses vétements.  On appelle P1 , P2 et P3, ses trois pulls , J1 , J2 et J3 ses trois jupes et C1 , C2 et C3 ses trois paires de chaussures. Les imcompatibilités des couleurs sont résumées dans le tableau suivant:

 

ne peut pas aller avec

P1

J1 , C2 , J3

P2

C1 , J2 , C3 , J3

P3

J1 , J2 , C2

J1

P1 , P3 , C3 , C1

J2

P2 , P1 , C1 , C2

J3

P1 , P2 , C1

1: Représenter les incompatibilités à l'aide d'un graphe dont les sommets sont les vetements.
2: Déterminer les nombre chromatique de ce graphe en expliquant la démarche et en donnant un exemple de coloration.
3: Donner alors les possibilités qu'a Marie pour s'habiller.

Exercice 2:   Dans un atelier de menuiserie, six travaux sont à réaliser. On utilise quatre machines.
M1  , une scie à dégrossir;   M2 , une raboteuse;  M3 , une mortaiseuse;  M4 , une ponceuse.
Chaque travail nécessite l'utilisation de deux machines. Deux travaux ne peuvent être exécutés en même temps que s'ils utlisent deux ensembles disjoints de machines.
PLAN DES UTLISATIONS POUR LES SIX TRAVAUX:

Travail

Machines utilisées

1

M1 , M2

2

M1 , M3

3

M3 , M4

4

M2 , M4

5

M3 , M4

6

M1 , M3

1: Former un graphe dont lequel les sommets sont les travaux , deux sommets étant reliés si les travaux corresponds ne peuvent pas être effectués en même temps sur une même machine.
2: Déterminer une organisation pour la réalisation des six travaux en un minmum de temps.  
     (Les temps d'utilisation des machines est supposé identique pour chaque travail nécessitant cette machine !)
     On expliquera la solution choisie.....

Exercice 3:
Un graphe non orienté G est donné par sa matrice associée M :  
1 : En numérotant les sommets de 1 à 6 , former le graphe G.
2: Pour chaque sommet S , calculer le degré de S.      Quel est le nombre d'arêtes de G ?
3: Peut-on former une chaîne eulérienne dans ce graphe ?      Si oui, indiquez, en donnant l'ordre des sommets, quelle chaîne eulérienne on peut former.
4: Déterminer le nombre chromatique de G.
5: Combien de chaînes de longueurs 4 et d'extrémités (1) et (2) existe-t-il ?