INFO TEST NOM : X Prénom : X Date: Déc. Classe: BTS
------------------------------------------------------------------------------------------------------------------------
• Soit G un graphe de sommets ABCDEF. Le tableau des prédécesseurs est :
Prédécesseurs | Sommets |
A | |
A | B |
A | C |
B | D |
B C | E |
D E | F |
•• Donner la matrice M adjacente à G.
Il y a 7 arcs et 6 sommets.
/
0
1
1
0
0
0
\
|
0
0
0
1
1
0
|
|
0
0
0
0
1
0
|
M =
|
0
0
0
0
0
1
|
|
0
0
0
0
0
1
|
\
0
0
0
0
0
0
/
•• Déssiner G.
.•• Trouver M2
/
0
0
0
1
2
0
\
|
0
0
0
0
0
2
|
|
0
0
0
0
0
1
|
M² =
|
0
0
0
0
0
0
|
|
0
0
0
0
0
0
|
\
0
0
0
0
0
0
/
•• Trouver M3
/
0
0
0
0
0
3
\
|
0
0
0
0
0
0
|
|
0
0
0
0
0
0
|
M3 =
|
0
0
0
0
0
0
|
|
0
0
0
0
0
0
|
\
0
0
0
0
0
0
/
•• Y a-t-il des chemins de longueur 2 ? Précisez les.
Il y en a: 1 + 2+ 2+1 = 6
Il y en 1 de A à D : ABD
Il y en a 2 de A à E : ABE ACE
Il y en a 2 de B à F : BDF B EF
Il y en a 1 de C à F: CEF
•• Combien y a -t-il de chemins de longueur 3 arrivant à B ?
Il y en a 0 car la colonne de B dans M3 n'a que des 0.
•• Donner les niveaux des sommets.
Prédécesseurs
Sommets
Niveaux
A
0
A
B
1
A
C
1
B
D
2
B C
E
2
D E
F
3
• Résoudre dans IR3 le système :
2 x - 3 y + z = 6 L1
x + 2 y + 3 z = 2 L2
x + 2 y + z = 0 L3
Considérons L2 ↔ L1
On obtient le système équivalent suivant:
x + 2 y + 3 z = 2 L1
2 x - 3 y + z = 6 L2 x + 2 y + z = 0 L3
Considérons:
L2 ← L2 - 2 L1
L3 ← L3 - L1
On obtient le système équivalent suivant:
x + 2 y + 3 z = 2 L1
- 7 y - 5 z = 2 L2 - 2 z = - 2 L3 Alors : L3 donne z = 1 Puis L2 donne - 7 y = 2 + 5 z = 2 + 5 = 7 y = - 1 Enfin L1 donne x = 2 - 2 y - 3 z = 2 + 2 - 3 = 1 x = 1
Conclusion : SIR3 ={ ( 1 ; - 1 ; 1 ) }