Terminale maths expertes : exercice graphe matrice

[mathde59]

bonjour

pouvez vous m'aider sur cet exercice.
Merci

G est un graphe connexe et sans boucle dont la matrice d'adjacence M est telle que :
M²=(3 2 0 1 1
2 2 0 1 1
0 0 1 1 1
1 1 1 3 2
1 1 1 2 3)

Déterminer le nombre d'arêtes du graphe

[hdci]

Bonjour,

La piste est d'identifier la matrice M qui donne au carré celle qui est fournie dans l'énoncé, avec en particularité : M est symétrique et sa diagonale est nulle (pas de boucles) ; et les coefficients sont entiers naturels.

De plus, la diagonale de M² est constituée de somme de carrés. Comme aucune valeur de la diagonale de M² ne dépasse 3, cela indique que les seuls coefficients admissibles sont 0 ou 1.

Cela permet de compter directement le nombre d'arêtes : quel est la relation entre le nombre d'arêtes et les coefficient de la matrice ? Du coup si un coeff diagonal de M² est égal à 3, peut-on en déduire le nombre de "1" dans la ligne correspondante de M ? Etc.

[catamat]

Bonjour,

On peut aussi reconstituer le graphe

En utilisant la diagonale de M², on sait que A est de degré trois, B deux, C un, D et E trois.

D'autre part il y a deux chemins de longueur 2 reliant les sommets A et B donc A-x-B et A-y-B cela implique que A et B ne sont pas reliés sinon B serait de degré 3.

Comme A est de degré 3, il est donc relié à C, D et E.
Par suite B est relié à D et E (pour avoir les chemins A-x-B et A-y-B précédents), il ne peut pas être relié à C qui est de degré 1.

Voilà c'est presque terminé....

[mathde59]

merci beaucoup