salut

je ne comprends pas pourquoi ta matrice d'adjacence est notée M² et pas M ...

que dit ton cours ?

combien de sommets compte ton graphe ?

les arêtes sont-elles orientées ? non orientées ?

il n'y a pas de boucle donc essaie de faire un schéma ...

Salut,

Oups! erreur de ma part: ce n'est pas "on donne la matrice d'adjacence" mais "La matrice d'adjacence M du graphe G est telle que "

La matrice donnée est en effet au carrée: on a donc le nombre de chaînes de longueur 2 reliant chaque sommet à un autre mais pas le nombre d'arêtes..

Forcément ici, le graphe comporte 5 sommets puisque M^2 est de la forme 5x5 (je pense?)

Les arêtes ici ne sont pas orientées

Je vais faire un schéma mais petite question: comme , cela signifie qu'il y a 3 chaînes de longueur 2 reliant le sommet 1 à lui-même?

Merci

Après de nombreuses tentatives, je n'ai pas réussi à faire le graphe associée à M^2: à chaque fois que je rajoute une arête ou en enlève une, un des coefficients de la matrice M^2 n'est plus vérifié... La méthode graphique est-elle la seule efficace ici?

Merci d'avance

Re,

J'ai réessayé de faire le graphe, sans succès

Cependant, j'ai eu une autre idée: faire l'inverse de M^2: je trouve donc:

Mais ici je n'ai que et M^(-2), je ne vois donc vraiment nul part comment obtenir M à partir de M^2 et dessiner un graphe semble vraiment trop compliqué à partir des chaines de longueur 2.

Si tu peux me dire par où commencer, ou si quelqu'un d'autre à une idée..

Merci!

Rectification (faute de frappe):



J'ai essayé de multiplier M^2 par cette matrice, mais bien sûr j'obtiens la matrice identité...

Bonsoir,
sur la matrice M² on lit le nombre de chemins de longueur 2 qui relient deux sommets.
Quels sont les chemins de longueur 2 qui relient un sommet à lui-même ?

PS : en tenant compte du fait qu'il n'a pas de boucle.

bonjour,

on peut certes répondre à la question posée, (nombre d'arêtes) sans connaitre le graphe ni la matrice M elle même
mais un tel graphe existe-t-il ?
pas plus que CapitainePois, je n'en ai trouvé.

il y a d'innombrables problèmes où le calcul d'une certaine quantité est possible à partir de données impossibles ...
donc donne un prétendu "résultat" qui n'a aucun sens.

le problème n'est valide que si on peut exhiber un graphe qui convient.
(ou une matrice d'adjacence M elle même c'est pareil)

Bonsoir mathafou.
Je n'avais pas vérifié l'existence d'un graphe répondant au problème,
mais il y en existe bien au moins trois.

ah ?
qui donnent ce M² là ?

des graphes avec ces degrés là sur les 5 sommets, oui, mais aucun ne donne un M² qui convient.

Bonjour à vous,

Si je ne me trompe pas, les chemins de longueur 2 qui relient un sommet à lui-même sont ceux situés sur la diagonale principale: donc







Il y en a donc 3+2+1+3+3=12 en tout!

Mais alors il suffit maintenant uniquement de soustraire ce nombre à tous les autres coefficients restants de la matrice? c'est-à-dire:



Est-ce bien celà?
Merci!

oups
je n'avais pas tout vérifié.
En effet aucun graphe ne convient, tout mes excuses.

@ CapitainePois :
comme le graphe est sans boucle un chemin de longueur 2 qui relie un sommet à lui-même est un aller-retour de ce sommet à un autre.
Les coefficients diagonaux de la matrice M² donnent le degré du sommet correspondant.

Et, finalement, il y a bien un graphe qui convient.
Quand je ne répond pas trop lentement, je répond trop vite.

Re,

Alors si les coefficients diagonaux de la matrice M2 donnent le degré du sommet correspondant, on a:

Ordre du sommet 1: 3
donc 3 arêtes

Ordre du sommet 2: 2
donc 2 arêtes

Ordre du sommet 3: 1
donc 2 arêtes

Ordre du sommet 4: 3
donc 3 arêtes

Ordre du sommet 5: 3
donc 3 arêtes

Ce qui donnerait 13 arêtes

Mais cependant, ici je compte des arêtes en plusieurs fois je crois, il faut donc faire un graphe en prenant compte de l'ordre de chacun des sommets ici:

J'ai donc fait le graphe ci joint

Et en comptant les arêtes sur ce graphe, on compte 6 arêtes.

Il y a donc 6 arêtes.

Cependant, lorsque je fais la matrice d'adjacence de ce graphe et que je la mets au carré, je trouve:



et donc lorsqu'on la met au carré on trouve:



qui ne correspond pas à M^(2)...
Est-ce normal?

Et dernière petite question: Y a-t-il une autre justification qu'en dessinant un graphe, peut-on directement déduire les arêtes "confondues" à partir de l'ordre de chaque sommet?

Merci!

Par ailleurs,

Encore par ailleurs: lorsque je parle d'ordre, je voulais dire degré* (désolé)

Tu as bien calculer le nombre d'arêtes qui part de chaque sommets (avec la correction pour le sommet 3 ).
Mais si je regarde deux sommets A et B reliés par une arête je vois une extrémité d'arête en A et une extrémité d'arête en B.

Re,

Oui, bien-sûr, c'est la raison pour laquelle j'ai fait le graphe, afin d'éviter les "doublons" liés aux arêtes reliant deux sommets.

Je trouve donc à la fin en prenant compte de ces doublons grâce au graphe que j'ai dessiné 6 arêtes.
Est-ce bien cela?

Pourrais-tu également m'expliquer comment tu as trouvé un graphe vérifiant la matrice M^2 et également la matrice M? S'il s'agit d'une technique ou alors via un ordinateur?

à la main ça marche très bien

en considérant S1 (degré 3) et S3 (degré 1) il y a deux points de départ selon que S3 est relié à S1 ou à un autre :



en bleu les arêtes restantes à considérer d'un graphe complet
il n'existe aucun sommet de degré 4 donc une des arêtes bleues partant de D du premier graphe est à éliminer et S2 sera B ou C etc
il reste deux graphes possibles à tester
l'un d'eux marche effectivement

Re!

Je crois que j'ai tout compris! Je pense que j'aurai ceci à refaire en DS donc si possible de me confirmer la méthode:

- On regarde les coefficients de la diagonale principale de M^2, qui correspondent au degré de chaque sommet (ici A: 3 ; B:2 ; C:1 ; D: 3 ; E: 3

- On dessine des graphes jusqu'à trouver le bon (voir ici les deux bons en pièces jointes)

- Lorsqu'on a ce(s) graphe(s), on peut vérifier en retrouvant la matrice d'adjacence M et en recalculant M^2

On a ici pour les deux graphes:



et en la mettant au carré, on retrouve bien la matrice donnée dans le sujet

Est-ce la bonne méthode?

Merci beaucoup

Bonsoir,
tu as dessiné deux fois le même graphe.
Et oui, c'est le graphe cherché.

quand on a les degrés des sommets c'est terminé
pas besoin de graphe pour compter les arêtes

parce que :
tu as trouvé que la somme des degrés est 12 (sans erreur d'addition )
chaque arête ajoute 1 au degré de chacun de ses sommets
par conséquent :
dans tout graphe la somme des degrés est le double du nombre d'arêtes.
donc le nombre d'arêtes est 6

ensuite chercher les graphes qui conviennent c'est surtout pour vérifier (que l'énoncé est cohérent et pas une entourloupette)

tes deux graphes sont identiques, même s'ils sont dessinés différemment.
d'ailleurs ils ont la même matrice d'adjacence, qui définit le graphe sans ambiguïté

Merci beaucoup. J'ai bien compris la méthode.

Bonne soirée à vous !