Fa ulté de Mathématiques Année : 2021/2022
Département de Re her he Opérationnelle 3ème Li RO. A
Module : Théorie des graphes USTHB, le 12/02/2022
EXAMEN FINAL
Durée : 1 heure 30 minutes
1
Problème
I. Considérons les graphes G1 et G2 (Voir page 3/3 2 ) :
1. Les graphes G1 et G2 sont-ils isomorphes ? Justi er ;
2. Le graphe G1 est-il biparti ? ontient-il un isthme ? Justi er ;
3. Montrer que G1 est planaire et déduire le nombre de ses fa es ;
4. Le graphe G2 est-il Hamiltonien ? déduire s'il ontient un point d'arti ula-
tion ? Justi er ;
5. Le graphe omplémentaire G2 est-il Eulérien ? (sans le dresser) Justi er.
II. Le graphe G2 modélise la situation suivante : les sommets représentent huit
étudiants qui se sont ren ontrés un jour à la bibliothèque. Deux sommets x et y
quel onques de G sont reliés si et seulement si les étudiants x et y ne développent
pas les mêmes a nités :
1. On veut déterminer dans G2 le nombre maximum a de personnes qui se sont
ren ontrés et qui s'entendent entre eux ;
(a) Que représente a dans le graphe ? Justi er ;
(b) Déterminer, en justi ant, a.
2. Suite à des travaux, la bibliothèque a mis à la disposition des étudiants un
nombre réduit de tables, mais pouvant ontenir un grand nombre d'étudiants. Les
responsables souhaitent onnaître le nombre minimum b de tables qu'on peut avoir
de telle sorte que haque table ontiendrait des étudiants qui s'entendent entre eux.
(a) Que représente b dans le graphe ? Justi er ;
(b) Déterminer, en justi ant, b.
III.Le graphe G1 modélise une autre situation, donnée omme suit : les sommets
représentent huit joueurs de tennis qui omptent parti iper à un tournoi au pro t
d'oeuvres aritatives. Les arêtes de G1 représentent tous les mat hs possibles du
tournoi. Si au un joueur ne doit disputer deux mat hs le même jour :
1. Les parties I. II. et III. sont indépendantes
2. La feuille supplémentaire est utilisée pour répondre aux questions
1/3
(a) Quel est le nombre maximum de mat hs qu'on peut avoir durant un jour
donné ? Justi er ;
(b) Quel est le nombre minimum de jours qu'on peut proposer pour organiser e
tournoi (tous les mat hs auront lieu. )
Exer i e
1. Soit G un graphe simple d'ordre n, de taille (n − 1) et qui n'est pas un arbre :
(a) Prouver que G n'est pas onnexe ;
(b) Prouver que G admet au moins une omposante onnexe qui est un arbre.
2. Soit T un arbre d'ordre n :
(a) Dire si la proposition suivante est vraie ou fausse en justi ant : " L'arbre T a
que des sommets de degré pair" ;
(b) Montrer que si tous les sommets sont de degré impair alors la taille de T est
impaire.
3. Soit G est un graphe d'ordre 12 ayant que des sommets de degré 1 et des
sommets de degré 3. Le graphe G peut-il avoir la stru ture d'un arbre ? Si oui
dresser G sinon justi er.
4. Soit F une forêt à p (p ≥ 2) omposantes onnexes d'ordre n et de taille m ;
(a) Déterminer m en fon tion de n et p ;
(b) Dresser une forêt F1 pour p = 3 et n = 12.
BON COURAGE
2/3
NOM : ....................... PRENOMS : .............................
Problème
1
a
8 2
h
b
7 3 g
f
d
6 4
5 e
G1 G2
3/3
