Questions graphes

curtis

Bonjour,

Soit $G=(V,E)$ un graphe simple à $n$ sommets et $m$ arêtes. On note $A$ sa matrice d'adjacence.

1) Pourquoi a-t-on $2m\leq n^2$?

2) Pourquoi a-t-on $tr(A^2)=2m$?

Merci

Bu

1) Parce que chaque arête a deux extrémités.
2) Parce que le moyen de revenir où on est parti en deux mouvements, c'est faire un aller-retour le long d'une arête.

curtis

Merci. Je comprend a peu près tes arguments. Tu connais une référence pour approfondir mes connaissances sur ces questions. Je débute en graphes.

Bu

Je n'ai pas de référence à te recommander.

Babcool

Tu peux regarder le cours de théorie des graphes de Denis Lapoire qui est disponible sur devellopez.com : http://lapoire.developpez.com/algorithmique/graphes/, qui aborde certaines généralités sur les graphes.

aoraki

Il y a un bon livre pour les notions de base : "Initiation à la théorie des graphes" de Christian Roux.