Kala te souhaite la bienvenueKalaMaths
9

Graphes et matrice d'adjacence

GRATUIT

Fiche élève

Les énoncés du chapitre, à imprimer ou à travailler à l'écran. Sans compte !

Pour aller plus loin

Réservé aux abonnés : la fiche interactive, le corrigé et la fiche prof.

Fiche interactive

Cours + 3 ateliers manipulables + exos auto-corrigés.

🔒 Réservé aux abonnésEssayer un atelier gratuitementS'abonner pour débloquerou ce chapitre seul, 2,99 €, voir plus bas.

Corrigé

La correction détaillée, avec les rappels utiles.

🔒 Réservé aux abonnésS'abonner pour débloquer

Fiche prof

La version enseignant, pour préparer et animer.

🔒 Réservé aux abonnésS'abonner pour débloquer

Juste besoin de ce chapitre ? Débloquez-le pour 2,99 € : paiement unique, accès à vie (fiche interactive, corrigé, fiche prof et corrigés des exercices).

Avec un code de parrainage, c'est −20 % sur cette première commande.

Débloquer ce chapitre – 2,99 €

Cet achat est réservé à un adulte.

Le chapitre en bref

Ce que tu vas savoir faire

  • Connaître le vocabulaire des graphes : sommets, arêtes, ordre, degré, boucle, orienté, pondéré.
  • Utiliser le lemme des poignées de main : la somme des degrés vaut deux fois le nombre d'arêtes.
  • Manier les notions de chaîne, de longueur, de cycle, de connexité et de distance.
  • Passer du graphe à sa matrice d'adjacence, et de la matrice au graphe.
  • Démontrer et utiliser : (MkM^{k}) en position (i ; j)(i \,;\, j) = nombre de chemins de longueur k de i à j.

Le plan du chapitre

  1. 1Sommets, arêtes et degrés
  2. 2Orientation, chaînes et connexité
  3. 3La matrice d'adjacence
  4. 4Puissances de M : compter les chemins
  5. 5Lire un réseau : distance et connexité

À retenir

  • Ordre = nombre de sommets ; degré = nombre d'arêtes issues d'un sommet (une boucle compte pour 2).
  • Lemme des poignées de main : somme des degrés =2= 2 × nombre d'arêtes ; donc le nombre de sommets de degré impair est pair.
  • Longueur d'une chaîne = nombre d'arêtes ; distance =longueur= \text{longueur} du plus court chemin.
  • Matrice d'adjacence : MijM_{ij} =1= 1 s'il y a une arête i–j, 0 sinon ; symétrique si le graphe n'est pas orienté ; somme de la ligne i=degreˊ de ii = \text{degré de } i.
  • (MkM^{k}) en position (i ; j)(i \,;\, j) = nombre de chemins de longueur exactement k de i à j ; la diagonale de M2M^{2} donne les degrés.
  • Connexité : tous les coefficients de I+M+⋯+Mn−1I + M + \dots + M^{n-1} sont strictement positifs.

Les questions éclair

C'est quoi le degré d'un sommet ?

Le nombre d'arêtes qui en partent (une boucle compte pour deux).

Que dit le lemme des poignées de main ?

La somme des degrés vaut deux fois le nombre d'arêtes, car chaque arête a deux extrémités.

Que compte le coefficient (MkM^{k}) en position (i ; j) ?

Le nombre de chemins de longueur exactement k reliant le sommet i au sommet j.

Comment lire une distance dans les puissances de M ?

C'est le plus petit exposant k pour lequel le coefficient (M puissance k) en (i ; j) est non nul.

Le sais-tu ?

La théorie des graphes est née d'une promenade : en 1736, Leonhard Euler s'est demandé s'il était possible de traverser les sept ponts de Königsberg en empruntant chacun une fois et une seule. Sa réponse, non, tient tout entière dans les degrés des sommets : un tel parcours impose que le nombre de sommets de degré impair soit 0 ou 2, or ici les quatre le sont. Ce petit problème de flânerie a fondé une branche entière des mathématiques.