Graphes et matrice d'adjacence
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.
Corrigé
La correction détaillée, avec les rappels utiles.
Fiche prof
La version enseignant, pour préparer et animer.
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 €
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 : () en position = nombre de chemins de longueur k de i à j.
Le plan du chapitre
- 1Sommets, arêtes et degrés
- 2Orientation, chaînes et connexité
- 3La matrice d'adjacence
- 4Puissances de M : compter les chemins
- 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 × nombre d'arêtes ; donc le nombre de sommets de degré impair est pair.
- Longueur d'une chaîne = nombre d'arêtes ; distance du plus court chemin.
- Matrice d'adjacence : s'il y a une arête i–j, 0 sinon ; symétrique si le graphe n'est pas orienté ; somme de la ligne .
- () en position = nombre de chemins de longueur exactement k de i à j ; la diagonale de donne les degrés.
- Connexité : tous les coefficients de 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 () 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.
