Scribd
Importer
21 vues1 page

Graph Es

Ce document présente une épreuve de théorie des graphes pour une licence professionnelle en informatique de gestion, avec des exercices portant sur les concepts de réseau PERT, les flots dans un réseau de transport, et l'analyse d'un graphe orienté. Les étudiants doivent définir des termes clés, analyser un flot donné, dessiner un graphe, et calculer des matrices. L'épreuve dure 2 heures et est notée sur 20 points.

Transféré par

chrisngollo
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
21 vues1 page

Graph Es

Ce document présente une épreuve de théorie des graphes pour une licence professionnelle en informatique de gestion, avec des exercices portant sur les concepts de réseau PERT, les flots dans un réseau de transport, et l'analyse d'un graphe orienté. Les étudiants doivent définir des termes clés, analyser un flot donné, dessiner un graphe, et calculer des matrices. L'épreuve dure 2 heures et est notée sur 20 points.

Transféré par

chrisngollo
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

LICENCE PROFESSIONNELLE - SECOND SEMESTRE

ANNÉE ACADÉMIQUE 2024/2025


SPÉCIALITÉ: Th1FORMATIQUE DE GESTION (IGJ)
ÉP~UVE DE : THÉORIE DES GRAPHES
SESSION DE : NORMALE
DURÉE: 2H

EXERCICE 1 (Questions de cours) : (6 points) .


Définir, en une phrase, chacune des expressions suivantes en réseau PERT :
1-) Etape; 2-) Tâche ; 3-) Tâches de début; 4-) Tâches de fin; 5-) Tâches simultanées ;
6-) cul--de-~ac; 7-) marge totale.

EXERCICE 2: (6 points)
· . . On considère le réseau de transport suivant où les arcs sont munis de capacités (c(x,y) ) et pour lequel une
• application {fJ est donnée. · '

N.B. les valeurs entre parenthèses sont les capaciJés des arcs. Par exemple : c(e , 1) = 13 et q,(e, 1);:: 5
1-) Montier que les valeurs <p (x, y) figurant sur les arcs forment un flot
2-) Quelle est la valeur de ce flot ?
3-) Ce flot est-il compatible ?
4-) Montrer que ce flot n'est pas complet Le modifier pour le rendre complet
· 5-) Quelle est la valeur de ce nouveau flot ?

EXERCICE 3 : (8 points)
On considère la matrice dl'!~dja~~e ~ d'~] graphe orienté telle que :
0 1 1 0
M= 0 0 0 1
0 1 1 0
0 1 1 0
1-) Dessiner le graphe correspondant. .
2-) Déterminer les degrés internes et externes de chaque sommet ; puis, vérifier les relations qui
Existent éntre le nombre des arcs et les degrés des sommets.
3-) Y a-t-il des sources ou des puits 7 _ . . _ •
3
4-) Calculer les matrices M 2 et M pws, en dedwre le nombre de chemins de lOllcaueur 3
ou moins de V1 à V3. · •
S-J Que dire de la connexité de ce graphe? . .
6-) Peut-on ~ire que cc graphe est un graphe plnruure et pourquoi ?

Vous aimerez peut-être aussi