[PDF] graphes PDF graphes.pdf

exercice 2 : 1 quelle matrice peut-être la matrice d'adjacence d'un graphe non orienté? A = 0 1 0

Ces excursions sont résumées sur le graphe ci-dessous dont les sommets trace de recherche même incomplète ou d'initiative même non fructueuse sera prise en de deux sommets A et B origines et extrémités de deux arètes orientées et

[PDF] TD no 1

Exercice 8 Un sommet x d'un graphe non orienté connexe G est dit point d' articulation de G si G−x est non connexe Montrer que tout graphe connexe contient au

[PDF] ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES

Exercice 16 (o) Essayez de construire un graphe non orienté ayant au moins deux sommets et tel que tous les sommets ont des degrés distincts Qu'

[PDF] Exercices de théorie des graphes Année académique 2020 − 2021

Exercice 7 Pour chacun des graphes simples non orientés suivants, donner un exemple d'existence ou prouver l'inexistence a) Un graphe biparti

[PDF] quelques exercices 1 Quelques propriétés des graphes

Dans les exercices suivants, `a moins d'indications contraires, on travaille sur grés de tous les sommets d'un graphe non-orienté est un nombre pair Com-

[PDF] Graphes non orientés

Distance entre deux sommets et diamètre d'un graphe Graphe pondéré et plus courte chaîne Matrice associée à un graphe Exercices d'apprentissage AA AB

[PDF] 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 (s, t)-chaîne dans G

[PDF] Introduction à la théorie des graphes Solutions des exercices

1 Graphes non orientés Exercice 1 On obtient le graphe biparti suivant (à gauche) : P1 C1 P2 C2 P3 C3 P1 C1 P2 C2 P3 C3 En colorant les arêtes de ce

[PDF] Exercices

Exercices Dans les exemples sont reliés si leur intersection est non vide ; Ci-après, la matrice M est associée à un graphe orienté G qu'on représentera

[PDF] graphes

exercice 2 : 1 quelle matrice peut-être la matrice d'adjacence d'un graphe non orienté? A = 0 1 0

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

6 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,BetC

2matchs chacune

A(2)B(2)

C(2)

Σd=participations...

Σa=matchs...

(b)?trois équipesA,BetC

1match 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,CetD

2matchs 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,CetD

3matchs chacune

A(3)B(3)

D(3)C(3)

Σd Σa

3.?5 équipesA,B,C,DetE

1match chacune

A EB DC Σd Σa

4.?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 DC

6.?5 équipesA,B,C,DetE

4matchs chacune

Σd Σa A EB DC

7. (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)

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 G5G6

1.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) s

3(2)s4(3)a

1a2 a 6a5 a 4a

3nombre 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 1

1 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0))))))

12= 1car 1 arête relies1às2

31= 0car 0 arête relies3às1

s5(2)s 1(2) s 2(3) s

3(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) s

3(2)s4(3)a

1a2 a 6a5 a 4a

3s2s3s4s2est une chaîne fermée et un cycle

2s3s4s2s3s4s2est une chaîne fermée mais pas un cycle

propriété 2

quel 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 1

1 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0))))))

s5(2)s 1(2) squotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] graphes

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

6 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

Σd=total de participations

Σa=total de matchs

1. (a)

2matchs chacune

A(2)B(2)

Σd=participations...

Σa=matchs...

1match chacune

A(1)B(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)