Scribd
Importer
46 vues2 pages

Exercices d'Algorithmique de Graphe

Le document présente une série d'exercices sur l'algorithmique des graphes et l'optimisation, abordant des concepts tels que le nombre de graphes orientés et non orientés, les degrés des sommets, et des problèmes pratiques de prélèvement de liquide. Il inclut également des questions sur la représentation des graphes par des listes et des matrices, ainsi que des problèmes théoriques liés à la connectivité des graphes. Enfin, il propose des exercices spécifiques sur un graphe donné avec 8 sommets et ses propriétés de connexité.

Transféré par

Ranim Latrous
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
46 vues2 pages

Exercices d'Algorithmique de Graphe

Le document présente une série d'exercices sur l'algorithmique des graphes et l'optimisation, abordant des concepts tels que le nombre de graphes orientés et non orientés, les degrés des sommets, et des problèmes pratiques de prélèvement de liquide. Il inclut également des questions sur la représentation des graphes par des listes et des matrices, ainsi que des problèmes théoriques liés à la connectivité des graphes. Enfin, il propose des exercices spécifiques sur un graphe donné avec 8 sommets et ses propriétés de connexité.

Transféré par

Ranim Latrous
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

E.N.S.

I 2016-2017
I.I.1

Algorithmique de graphe & Optimisation


TD1

Exercice 1
Combien existe-t-il de graphes orientés (resp. non orientés) à n sommets ?

Exercice 2
Montrer que dans un graphe non orienté, il y a toujours deux sommets de même degré.

Exercice 3
On souhaite prélever 4 litres de liquide dans un tonneau. Pour cela, nous avons à notre dis-
position deux récipients (non gradués !), l’un de 5 litres, l’autre de 3 litres. Comment doit-on
faire ?

Exercice 4
Soit G = (X, U ) un graphe, et soit m = |U |
X
1. Montrez que : d(x) = 2m
x∈X
2. Dans un groupe de vingt enfants, est-il possible que sept d’entre eux aient chacun
exactement trois amis, neuf d’entre eux en aient exactement quatre, et quatre d’entre
eux exactement
cinq ?

Exercice 5

1. Donner une représentation du graphe ci-dessus au moyen d’une liste d’adjacence, puis
au moyen d’une matrice d’adjacence.
2. Donner une représentation du même graphe (ci-dessus) en matrice d’incidence . Quels
problèmes rencontre-t-on ?
3. Si B T désigne la transposée de B la matrice d’incidence, que représente la matrice BB T ?

Exercice 6
On a construit des ponts entre les ı̂les d’un archipel de sorte de pouvoir aller (directement ou
indirectement) de toute ı̂le à une autre. De plus, de chaque ı̂le part un nombre pair de ponts.
On a remarqué que, lorsqu’un pont est inaccessible pour cause de travaux, on peut encore aller
de toute ı̂le à une autre.
1. Traduire ce problème en terme de théorie des graphes.
2. Prouver le résultat !

Exercice 7
Soit G le graphe à 8 sommets dont la représentation par liste de successeurs est la suivante :

Sommet Successeurs
A F
B A,C,E,F,G
C E
D H
E A,B
F H
G C,D,E
H D

1. Tracer le graphe G.
2. G est-il fortement connexe ? Sinon, déterminer les composantes fortement connexes de
G.

Vous aimerez peut-être aussi