Inscription / Connexion Nouveau Sujet
Exercie Matrices/Graphes
Bonjour 
Alors voilà j'ai un exercice à faire sur les graphes/matrice mais je bloque dessus car je n'ai pas trop bien ce passage là du chapitre où on mélange matrice et graphe.
Voici l'énoncé :
La matrice M suivante est celle d'un graphe orienté G ayant 5 sommets : 1, 2, 3, 4, et 5 pris dans cet orde.
M = 0 1 1 0 1
0 0 1 1 1
1 1 0 1 0
1 1 1 0 0
1 0 1 0 0
1- Justifier en utilisant la matrice M, que le graphe G n'est pas complet.
2- a. A l'aide de la calculatrice, calculer M^2
b. Justifier, en utilisant les matrices M et M^2, que le graphe G est connexe.
3-Dessiner un graphe G de matrice M.
4-a. Indiquer le nombre de chemins de longueur 2 allant du sommet 5 au sommet 2.
b. Décrire ces chemins.
5-a. Quel terme de la matrice M^3 donne le nombre de chemins de longueur 3 allant du sommet 4 au sommet 5 ?
b. Calculer ce terme (détailler les calculs), puis décrire ces chemins de longueur 3 allant du sommet 4 au sommet 5.
6-a. Quel terme de la matrice M^3 donne le nombre de chemins de longueur 3 allant du sommet 1 au sommet 3 ?
b. Calculer ce terme (détailler les calculs), puis décrire ces chemins de longueur 3 allant du sommet 1 au sommet 3.
___________________________________________________________________________________________________________________________________
1- Je sais ce qu'est un graphe complet, mais je ne sais pas comment le déterminer à partir de la matrice.
2-a. M^2 = 0 1 1 0 1
0 0 1 1 1
1 1 0 1 0
1 1 1 0 0
1 0 1 0 0
b.
3- 
4-a. Il y a 2 chemins
b. 5-1-2 et 5-3-2
Pour la 5 et la 6 je n'ai pas tellement compris non plus …
Si quelqu'un pourrait m'aider se serait vraiment gentil 
Bonjour,
1) par exemple première ligne la matrice
0 1 1 0 1
le second "0" signifie le sommet 1 n'est pas relié sommet 4
tu conclus
2) refais le calcul
A2≠A
Merci de ta réponse,
1) Donc pour qu'un graphe soit complet, il faut que la matrice est cette forme
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
Donc le graphe n'est pas complet car les sommets ne sont pas tous reliés, ex : 2 n'est pas relié à 1 ou 5 n'est pas relié à 2.
2) 2 1 2 2 1
3 2 2 1 0
1 2 3 1 2
1 2 2 2 2
1 2 1 1 1
OK tes réponses
5a)le terme a4;5 de A3 est égal au nombre de longueur de chaînes de longueur 3 permettant d'aller du sommet 4 au sommet 5
remarque concernant ton graphe :
La matrice M suivante est celle d'un graphe orienté G ayant 5 sommets :
attention tu n'as pas orienté ton graphe...
pour 5 et 6 je ne sais pas ce que tu as vu en cours...
clique sur ce lien
Est-il orienté maintenant ?
5-b. M^3=a4;5
donc il faut prendre tous les chemins de longueur 3 permettant d'aller du sommet 4 au sommet 5.
4-1-2-5
4-1-3-5
4-3-2-5
4-2-1-5
4-3-1-5
Donc le terme est 5 ?
Comme cela ?tu as des flèches mal placées
chaque 1 correspond à une flèche " dans le bon sens"
par exemple
a21=0 donc tu n'as pas de flèche qui part du sommet 2 vers le sommet 1
corrige je vois 3 autres erreurs...
Cette fois ça devrait être bon
5a) a4;5 il faut détailler les calculs
la 4ème ligne de A2 et 5ème colonne de A
a=1*1+2*1+2*0+2*0+2*0=....
je n'ai pas vu que le 4-2-1-5 est faux puisque a2,1=0
donc pour l'instant
4 -3 -2 -5 OK
4-3-1-5 OK
il en manque 1
1ère ligne de A^2 et 3ème colonne de A
a1;3=2*0+1*1+2*1+2*0+1*0=3
Le terme est 3
b-1-2-4-3
1-5-1-3
1-2-5-3
Super l'exercice est (enfin) fini, j'ai mis le temps 
En tous cas, merci beaucoup à toi pour ton aide !
Annuler
connectez vous