GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
Le graphe probabiliste sera constitué de deux sommets A et B origines et extrémités de deux arètes orientées et pondérées. L'arête reliant A à B dans le
Graphes Orientés
Graphes Orientés. 2. Exercice 1. Un club de tennis doit sélectionner deux joueurs parmi quatre pour représenter le club à un tournoi régional. Les quatre
Introduction à la théorie des graphes Solutions des exercices
des graphes. Solutions des exercices. Didier Müller. CAHIER NO 6. COMMISSION ROMANDE DE MATHÉMATIQUE. Page 2. Page 3. 1 Graphes non orientés. Exercice 1. On
Introduction à la théorie des graphes
Corrigés des exercices . 2 Graphes orientés. 2.1 Graphes orientés. En donnant un sens aux arêtes d'un graphe on obtient un digraphe (ou graphe orienté). Le ...
Exercice sur les Graphes
Principe : Parcourir le graphe à partir du point a dans le sens direct (i.e. en suivant les flèches des arcs puisque nous sommes ici dans le cadre orienté)
Optimisation Combinatoire et Graphes Exercices et Solutions
30 avr. 2018 Un graphe (non orienté) G est constitué de deux ensembles : un ensemble fini et non vide V dont les éléments sont appelés sommets et un ...
graphes.pdf
3 graphe orienté matrice d'adjacence
Exercices de théorie des graphes Année académique 2020 − 2021
Exercice 14. Soit k un nombre entier strictement positif. Soit G un graphe simple non orienté
Exercices de Programmation Orientée Objet en Java
A quel affichage conduit l'exécution du programme (éventuellement corrigé)? class Test { int i;. Test(Test t) { if(t == null) this.i =
Exercices dexamen sur les graphes (niveau L3) avec corrigés
Pour ce graphe non orienté à 14 sommets les voisins de chaque sommet sont supposés écrits dans l'ordre croissant de leurs numéros.
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
GRAPHES - EXERCICES CORRIGES. Compilation réalisée à partir d'exercices de BAC TES On a représenté par le graphe ci-dessous les sommets B C
Graphes Orientés
Un graphe orienté est un graphe dont les arêtes sont orientées (c'est à dire : on ne peut parcourir les arêtes Exercice 2 ( sujet bac Liban mai 2006).
graphes.pdf
1.4 corrigés exercices . 3 graphe orienté matrice d'adjacence
Exercices …
Contenu : graphe orienté ; matrice associée à un graphe orienté. Exemple 17 : coloration de graphes. - Montrer que le nombre chromatique du graphe (1) ci-
Exercices de théorie des graphes Année académique 2020 ? 2021
Exercice 14. Soit k un nombre entier strictement positif. Soit G un graphe simple non orienté
Introduction à la théorie des graphes Solutions des exercices
1 Graphes non orientés établi dans l'exercice 7 un tel graphe doit posséder un nombre pair de sommets
ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES
Exercice 1. (o) Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation « être
Optimisation Combinatoire et Graphes Exercices et Solutions
30 avr. 2018 GRAPHES NON ORIENTÉS. Exercice 21 Dans un graphe G soient s et t deux sommets distincts. Montrer qu'il existe une.
Premi`eres notions sur les graphes
TD Graphes et Langages feuille n? 1. Premi`eres notions sur les graphes. Exercice 1 On consid`ere le graphe orienté G = (S A) tels que.
Exercices Corrigés
Exercice 3 : Dessiner un graphe non orienté complet à 4 sommets. Quel est le degré des sommets de ce graphe ? Combien d'arêtes possède-t-il ?
Table des matières
1 graphe, matrices d"adjacence, chaînes et cycles3
1.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 3
1.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 4
1.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 7
1.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 8
1.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 9
1.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 11
1.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 14
2 graphe connexe, trajet Eulérien et algorithme d"Euler19
2.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 19
2.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 19
2.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 20
2.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 21
2.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 22
2.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 24
2.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 26
3 graphe orienté, matrice d"adjacence, graphe étiqueté32
3.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 32
3.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 32
3.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 33
3.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 34
3.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 35
3.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 36
3.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 37
4 graphes pondérés39
4.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 39
4.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 39
4.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 40
4.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 41
4.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 43
4.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 44
5 graphe probabiliste, matrice de transition, état stable47
5.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 47
5.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 47
5.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 49
5.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 50
5.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 51
5.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 52
5.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 53
5.5 travaux pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 55
5.5.1 tableur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 55
16 Minima58
6.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 58
6.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 58
6.1.2 corrigé activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 59
6.1.3 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 60
6.1.4 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 61
6.1.5 activité 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 62
6.1.6 activité 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 63
7 Coloration d"un graphe et nombre chromatique64
7.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 64
7.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 64
7.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 65
7.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 66
8 devoir maison67
8.1 corrigé devoir maison . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 67
9 exercices bac blanc71
1 graphe, matrices d"adjacence, chaînes et cycles1.1 activités
1.1.1 activité 1
tournois(ordre d"un graphe, degré d"un sommet, propriété des poignées de mains) un tournois est organisé entre des équipes,dans chaque cas(si possible):- construire au moins un graphe(indiquer le degré de chaque sommet, une arête représente unmatch)
- construire un tableau de la formeΣd=total de participations
Σa=total de matchs
- donner l"ordre du graphe(nombre de sommets)et indiquer s"il est complet(tous les sommets adjacents 2 à 2)
1. (a)
?trois équipesA,BetC2matchs chacune
A(2)B(2)
C(2)Σd=participations...
Σa=matchs...
(b)?trois équipesA,BetC1match chacune
A(1)B(1)
C(1)Σd=participations...
Σa=matchs...
2. (a)?4 équipesA,B,CetD
1match chacune
A(1)B(1)
D(1)C(1)
A(1)B(1)
D(1)C(1)
A(1)B(1)
D(1)C(1)
Σd Σa (b)?4 équipesA,B,CetD2matchs chacune
A(2)B(2)
D(2)C(2)
A(2)B(2)
D(2)C(2)
A(2)B(2)
D(2)C(2)
Σd Σa (c)?4 équipesA,B,CetD3matchs chacune
A(3)B(3)
D(3)C(3)
Σd Σa3.?5 équipesA,B,C,DetE
1match chacune
A EB DC Σd Σa4.?5 équipesA,B,C,DetE
2matchs chacune
Σd Σa A(2)E(2)B(2)
D(2)C(2)
A(2)E(2)B(2)
D(2)C(2)
5.?5 équipesA,B,C,DetE
3matchs chacune
Σd Σa A EB DC6.?5 équipesA,B,C,DetE
4matchs chacune
Σd Σa A EB DC7. (a) est-il possible d"organiser un tournois avec6équipes où chacune joue5matchs? (justifier)
(b) est-il possible d"organiser un tournois avec7équipes où chacune joue5matchs? (justifier)(c) quelle relation y a t-il entre le nombre d"arêtes d"un graphe et la somme des degrés de chaque
sommet? (justifier)1.1.2 activité 2
parmi les graphes ci dessous, lesquels peuvent décrire une même situation? (on pourra indiquer le degré de chaque sommet ainsi que l"ordre du graphe) ?G1 G2 G3 G4 G5G61.1.3 activité 3
1.2 à retenir
définition 1 :(graphe non orienté, ...)(1) un graphe est défini par la donnée de deux ensembles,?l"ensemble de sesnsommetsS={s1,s2,...,sn},n?N?
l"ensemble de sesparêtesA={a1,a2,...,ap},p?N?? s5s 1 s 2 s 3s4a 1a2 a 6a5 a 4a 3 où chaque arête est un sous ensemble{si;sj}de deux sommets du graphe (2) un????graphe est d"ordren(n?N)??il a exactement????nsommets (3) un????sommet est de degrén(n?N)??il appartient à exactement????narêtes (4) deux sommets sont????adjacents??????il existe une arête qui les contient tous les deux (5) un graphe est????complet??tous ses sommets(distincts)sont????adjacents deux à deux exemple: le grapheGdessiné ci dessus - est d"ordre5car il a5sommets{s1;s2;s3;s4;s5} - a6arêtes{a1;a2;a3;a4;a5;a6} - le sommets1est de degré2car il appartient à exactement2arêtesa1eta2 -s1ets2sont adjacents par l"arêtea2 -s1ets3ne sont pas adjacents donc le graphe n"est pas complet propriété 1 quel que soit le graphe non orientéG? ???somme des degrés des sommets = 2×nombre d"arêtes justification: chaque arête compte pour2dans la somme des degrés exemple pour le grapheG? s5(2)s 1(2) s 2(3) s3(2)s4(3)a
1a2 a 6a5 a 4a3nombre d"arêtes×2=6×2 = 12
somme des degrés des sommets =2 + 3 + 2 + 3 + 2 = 12 remarques :(découle de la propriété précédente)1. la somme des degrés des sommets d"un graphe est nécessairement pair
2. le nombre de sommets de degré impair est nécessairement pair
définition 2 :(matrice d"adjacence d"un graphe non orienté ) quel que soit le graphe non orientéGànsommets{s1,s2,...,sn}(n?N?)Aest matrice d"adjacence deG
???Aest une matrice carrée d"ordren quel que soit le coefficientaijde la matriceA,? ???aij=nombre d"arêtes reliantsiàsj exemple pour le grapheG, matrice d"adjacence =A=((((((010 0 11 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0))))))
a12= 1car 1 arête relies1às2
a31= 0car 0 arête relies3às1
s5(2)s 1(2) s 2(3) s3(2)s4(3)a
1a2 a 6a5 a 4a 3 remarque la matrice d"adjacence d"un graphe est symétrique définition 3 :(chaîne, cycle ) quel que soit le graphe non orientéGànsommets{s1,s2,...,sn}(n?N?) (1) une????chaîne est une????liste ordonnée de sommets adjacents (2) une????chaîne est fermée si ses????extrémités sont égales (3)????un cycle est une????chaîne fermée dont toutes les????arêtes sont distinctes exemple: pour le grapheG? s5(2)s 1(2) s 2(3) s3(2)s4(3)a
1a2 a 6a5 a 4a3s2s3s4s2est une chaîne fermée et un cycle
s2s3s4s2s3s4s2est une chaîne fermée mais pas un cycle
propriété 2quel que soit le graphe non orientéGànsommets{s1,s2,...,sn}(n?N?) et de matrice d"adjacence deA?
???le termeaijde la matriceApoup?N? est égal au????nombre de chaînes de longueurpqui relient les sommetssietsj exemple pour le grapheG, on a :A=((((((010 0 11 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0))))))
s5(2)s 1(2) s 2(3) s3(2)s4(3)a
1a2 a 6a5 a 4a 3 la calculatrice donne :A3=((((((052 1 4
5 2 4 6 1
2 4 2 4 2
1 6 4 2 5
4 1 2 5 0))))))
a12= 5donc5chaînes de longueur3relients1às2:
s a31= 2donc2chaînes de longueur3relients3às1:
s3s4s2s1,s3s4s5s1
1.3 exercices
exercice 1 : soit le grapheGreprésenté ci contre :A B C D EF G H1. quel est l"ordre de ce graphe?
128413
2. combien a t-il d"arêtes?128413
3. quel est le degré du sommetC?128413
4. quel sommet est de degré 1?ABFaucun
5. quel sommet est adjacent au sommetD?AEGH
6. combien de sommets sont adjacents au sommetH?3241
7. le graphe est-il complet?ouinonon ne peut pas savoir
8. combien ajouter d"arêtes pour que le graphe soit complet?031516
9. quelle est la longueur de la chaineABCDFH?0256
10. quelle chaine est fermée?ABDACDBABACAABDCAB
11. quelle chaine est un cycle?ABDACDBABACAABDCA
12. combien de lignes la matrice d"adjacenceMa t-elle?891213
13. combien de colonnes la matrice d"adjacenceMa t-elle?891213
14. que vaut le coefficientm33de la matrice d"adjacenceM?014on ne peut pas savoir
15. que vaut le coefficientm23de la matrice d"adjacenceM?014on ne peut pas savoir
16. que vaut le coefficientM214de la matrice d"adjacence au carréM2?012on ne peut pas savoir
exercice 2 :1. quelle matrice peut-être la matrice d"adjacence d"un graphe non orienté?
A=((0 1 01 0 10 1 1))B=?1 0 10 1 0?C=((0 11 00 1))D=((0 1 11 0 10 1 0))E=((0 1 11 0 11 1 0))2. soitM=((((0 1 1 11 0 1 01 1 0 11 0 1 0))))
la matrice d"adjacence d"un grapheG (a) combien de sommetGa t-il?3416on ne peut pas savoir
(b) combien d"arêtesGa t-il?4510on ne peut pas savoir (c) quel est le degré du premier sommet?345on ne peut pas savoir (d) les2eet4esommets sont-ils adjacents?ouinonon ne peut pas savoir (e) les2eet3esommets sont-ils adjacents?ouinonon ne peut pas savoir (f) quel est le grapheG? s1s2 s4s3 s1s2 s4s3 s1s2 s4s3 (g)M2=((((3 1 2 11 2 1 22 1 3 11 2 1 2)))) ,M3=((((4 5 5 55 2 5 25 5 4 55 2 5 2)))) ,M4=((((15 9 14 99 10 9 10
14 9 15 9
9 10 9 10))))
i. combien de chemins de longueur2des3às3? 0123ii. combien de chemins de longueur3des4às2?2345 iii. combien de chemins de longueur4des2às3?9101415 exercice 3 :
1. dessiner les graphes complets pourn= 2,n= 3,n= 4,n= 5
2. dessiner les graphes simples d"ordresn= 2,n= 3,n= 4,n= 5dont tous les sommets sont de degré
23. dessiner tous les graphes simples possible d"ordren= 2,n= 3,n= 4
exercice 4 :1. est-i possible de relier en réseau,15ordinateurs tels que chacun soit relié à exactement5ordinateurs?
(justifier)2. à une soirée ou sont présentes17personnes, est-il possible que chacune des personnes serrela main
d"exactement15personnes? (justifier)3. dans un graphe simple(une arête au maximum entre deux sommets), combien y a t-il de sommets de
degré impair? (justifier)4. comment tracer 5 segments sur une feuille, de telle manière que chaque segment en coupe exactement
3 autres?
1.4 corrigés exercices
corrigé exercice 1 : soit le grapheGreprésenté ci contre :A B C Dquotesdbs_dbs21.pdfusesText_27[PDF] exercices corrigés incoterms 2020
[PDF] exercices corrigés les bascules pdf
[PDF] exercices corrigés les filtres passe bas/haut en pdf
[PDF] exercices corrigés les nombres réels
[PDF] exercices corrigés ligne de transmission
[PDF] exercices corrigés logique et raisonnement
[PDF] exercices corrigés logique et raisonnement pdf
[PDF] exercices corriges loi binomiale premiere es
[PDF] exercices corrigés loi de probabilité à densité
[PDF] exercices corrigés loi exponentielle pdf
[PDF] exercices corrigés machine a courant continu
[PDF] exercices corriges machines a courant continu
[PDF] exercices corrigés management de la qualité pdf
[PDF] exercices corrigés maths 1ere es derivation