Scribd
Importer
114 vues1 page

Série n:02: Exercice 01

Le document contient quatre exercices portant sur la théorie des graphes. Les exercices demandent de représenter des situations sous forme de graphes, de déterminer si les graphes sont connexes ou fortement connexes, et de représenter des tâches sous forme de graphe ordonné.

Transféré par

Jean Oscar Bado
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
114 vues1 page

Série n:02: Exercice 01

Le document contient quatre exercices portant sur la théorie des graphes. Les exercices demandent de représenter des situations sous forme de graphes, de déterminer si les graphes sont connexes ou fortement connexes, et de représenter des tâches sous forme de graphe ordonné.

Transféré par

Jean Oscar Bado
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:02

Exercice 01:
Etant donné un groupe de dix personnes, le tableau suivant indique les paires de personnes qui
ont une relation d'amitié.

I 1 2 3 4 5 6 7 8 9 10
Ami de i 3,6,7 6,8 1,6,7 5,10 4,10 1,2,3,7 1,3,6 2 4,5

1- Représentez cette situation par un graphe?


1- Ce graphe est-il complet? Connexe? (sinon déterminer les composantes connexes )
2- Si l'adage (les amis de nos amis sont nos amis) était vérifié, que pourrait on en conclure sur la
structure du graphe.

Exercice 02:
Soit le graphe G=(X,U) suivant:
x2
x7
x1 x3

x4
x8
x6 8
x5

2- Est-ce que G est connexe?


3- Est-ce que G est fortement connexe? Sinon déterminer les composantes fortement connexes de
G et le graphe réduit Gr.

Exercice 03:
La réalisation d'un projet suppose la réalisation de 5 tâches A, B, C, D, E. les conditions
d'antériorité entre ces différentes taches sont représentées dans le tableau suivant.

Représenter les tâches de ce projet sous forme Les tâches Les tâches précédentes
d'un graphe ordonné. A B,C
B -
C B
D C
E A,D

Exercice 04:
Soit le graphe G=(X,U) suivant: 2
4
1

3
6
5

Est-ce que G est ordonnable? Sinon, déterminer un circuit éventuel.

Vous aimerez peut-être aussi