8/3/2019 Td Theorie Des Graphes

1/2

Universit e dAbomey-Calavi Annee Acad emique 2010 - 2011ENEAM Filiere : LP-RIM

TD nr2 Graphes et Combinatoire

Exercice 1

Mr Jean veut organiser une soiree dansante, a laquelle il invite Antoine, Basile, Gaston, Honore, Lucette,

Mireille, Natalie, Orneillia et Simone.

Si lon excepte Gaston, qui na pas dexclusives, Jean et ses amis ont un caract ere capricieux : chacundeux ne supporte de danser quavec des compagnes bien precises :

... compagnes de danse

(ne veut danser quavec) ...

Antoine Lucette et Orneillia

Basile Lucette

Honore Lucette et Orneillia

Jean Lucette, Orneillia et Simone

1. Repesenter la situation de la soiree au moyen dun graphe G (les demoiselles invitees ayant toutes

excellent caractere, acceptent tous les cavaliers.

2. Prouver que la matrice booleene M du graphe G peut se mettre sous la forme

M=

0 M0M

00

,

ou M0 et M

Osont deux matrices a determiner.

3. Donner le degre de chaque sommet. Comment peut-on interpreter ici les degres des sommets.

Exercice 2

Une universite doit organiser les horaires des examens. On suppose quil y a 7 epreuves a planifier, corre-

spondant aux cours numerotes de 1 a 7 et que les paires de cours suivantes ont des etudiants communs : 1

et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et 7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et 6 et 7.

Comment organiser ces epreuves de facon quaucun etudiant nait a passer deux epreuves en meme temps

et cela sur une duree miminale ?

Exercice 3

Une personne dispose de huit poissons que lon designe par A,B,C,D,E,F,G et H. Dans le tableau ci-dessous,

une croix signifie que les poissons ne peuvent cohabiter dans un meme aquarium :

A B C D E F G H

A x x x x x

B x x x x

C x x x x x

D x x x x

E x x x x

F x x x

G x x x x

H x x x

1

8/3/2019 Td Theorie Des Graphes

2/2

Quel nombre minimum daquariums faut-il ?

Exercice 4

2