Scribd
Importer
89 vues1 page

Ef 2019-2020

Le document est un examen final de théorie des graphes pour un cours d'informatique, comprenant trois exercices. Le premier exercice porte sur l'analyse d'un graphe orienté, le second sur la planification de tâches avec contraintes, et le troisième sur les propriétés des graphes simples. Chaque exercice demande des justifications et des calculs spécifiques liés aux concepts de théorie des graphes.

Transféré par

Nadia Makhloufi
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
89 vues1 page

Ef 2019-2020

Le document est un examen final de théorie des graphes pour un cours d'informatique, comprenant trois exercices. Le premier exercice porte sur l'analyse d'un graphe orienté, le second sur la planification de tâches avec contraintes, et le troisième sur les propriétés des graphes simples. Chaque exercice demande des justifications et des calculs spécifiques liés aux concepts de théorie des graphes.

Transféré par

Nadia Makhloufi
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

U.S.T.H.B., F.E.I.

Département Informatique 27 Janvier 2020


L3 (S5) Informatique Générale –A–

Examen Final de Théorie des Graphes


Durée 1h15’

Exercice 1. (08 pts)


Soit le graphe orienté G=(X, U) représenté dans le tableau ci-dessous par le dictionnaire des prédécesseurs :
xX . 1 2 3 4 5 6 7 8 9
Prédécesseurs de x .: 2 6 1, 9 2 1, 3, 8 2, 4 1, 3, 8 4, 6 4, 5, 7
1. Etudier les propriétés de G (simple, complet, régulier). Justifier.
2. G admet-il un parcours Eulérien ? Justifier.
3. Trouver un cycle Hamiltonien dans G.
4. Calculer la matrice de fermeture transitive M̂ .
5. Donner les composantes fortement connexes de G. Tracer le graphe réduit GR de G.
6. Proposer le nombre minimal d’arcs à rajouter à G pour qu’il soit fortement connexe.

Exercice 2. (08 pts)


Un projet requiert la réalisation de six (06) tâches, le tableau suivant donne pour chaque tâche, le temps
(en jours) requis et les contraintes liées au début d’exécution des tâches.
Tâche i Durée de i Contraintes liées au début d’exécution de la tâche i
1 5 -
2 7 Ne peut débuter que 2 jours après le début des travaux et après la fin de 1
3 1 Après la fin de 1 et 2.
4 4 Après la fin de 3 et ne doit pas dépasser k jours après le début de 2.
5 8 Après la fin de 1 et 3.
6 3 Après la fin de 4.

1. Ecrire les contraintes sous forme d’inéquations.


2. Donner la représentation du problème en graphe MPM (Potentiel-tâches).
3. Trouver un circuit dans le graphe obtenu. Pour quelles valeurs de k, le problème admet une solution ?
4. On pose k=10. Donner les dates de début au plus tôt de chaque tâche et la durée optimale du projet.
5. Donner les dates au plus tard, et déduire les taches critiques.

Exercice 3. (05 pts)


Soit G un graphe non orienté tel que |X|=n et |E|=m.
1. Montrer que si G est simple complet alors m=n(n-1)/2.
2. Montrer que si G est simple avec p composantes connexes, le nombre maximum possible d'arêtes
dans G est m= (n-p)(n-p+1)/2.

Bon Courage

Vous aimerez peut-être aussi