Scribd
Importer
304 vues1 page

Exercices de Graphes et Applications

Le document présente 5 exercices sur la théorie des graphes. Les exercices portent sur la représentation de différentes situations sous forme de graphes, comme des liaisons aériennes ou une programmation de matches, et sur l'analyse de graphes existants.

Transféré par

mtaallah amal
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
304 vues1 page

Exercices de Graphes et Applications

Le document présente 5 exercices sur la théorie des graphes. Les exercices portent sur la représentation de différentes situations sous forme de graphes, comme des liaisons aériennes ou une programmation de matches, et sur l'analyse de graphes existants.

Transféré par

mtaallah amal
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Théorie deS grapheS Série n:01

Exercice 01:
Le tableau ci-dessous donne les liaisons internes assurées par différentes compagnies d'Air
Algérie.

Alger Bejaia Annaba Oran Constantine Tamanrasset


Alger /
Bejaia / /
Annaba / /
Oran /
Constantine / /
Tamanrasset / / /

1- Représenter les différentes liaisons par un graphe.


2- Déterminer les destinations des vols partant de Annaba.

Exercice 02:
Le tableau suivant représente l'intervention de 5 arbitres dans un tournoi, 6 rencontres sont
programmées pour la première journée.

Arbitres A1 A2 A3 A4 A5
Rencontres M1 – M2 M3 – M4 – M2 M5 – M4 – M6 M1– M3 M6 – M5

Représenter la programmation du déroulement des rencontres de la première journée par un graphe.


Indication: Deux sommets sont reliés par une arête si les rencontres correspondantes peuvent se
dérouler au même moment.

Exercice 03:
Représenter les situations ci-dessous à l'aide d'un graphe:
1- On considère un cube; un sommet est associé à une face du cube et deux sommets sont reliés
par une arête si les faces correspondantes ont une arête commune;
2- Les sommets du graphe sont tous les sous-ensembles à deux sommets 1,2,3,4; deux sommets
sont reliés si leur intersection est non vide;
3- Comparer les deux graphes définis ci-dessus.

Exercice 04:
Une ligue de football comporte 5 équipes.
1- Il est décidé par le bureau de la ligue que lors d'un week-end d'entraînement, chaque équipe jouera
quatre matches.
Faire un planning des rencontres sachant que deux équipes ne peuvent pas se rencontrer plus
d'une fois?
2- le calendrier étant trop chargé, les organisateurs décident que chaque équipe ne jouera que trois
matches. Comment l'organiser?

Exercice 05:
On défini une relation R sur l'ensemble des 9 premiers entiers naturels non nuls comme suit:
xRy  x est un diviseur de y
1- Représenter cette relation par un graphe orienté.
2- Déterminer à partir du graphe l'ensemble des nombres pairs et l'ensemble des nombres premiers.

Vous aimerez peut-être aussi