Aller au contenu
Théorie des graphes · L1

Leçon 2 sur 5

Chemins, cycles et connexité

Je sais définir chaînes, chemins et cycles, calculer des distances, déterminer les composantes connexes d'un graphe et utiliser les puissances de la matrice d'adjacence pour compter les chemins.

  • 1 h 05
  • 4 exercices corrigés
  • QCM de 5 questions

À la fin de la leçon, vous saurez :

  • Définir chaîne, chaîne élémentaire, cycle et distance dans un graphe
  • Définir la connexité, les composantes connexes et la forte connexité d'un graphe orienté
  • Démontrer qu'un graphe connexe d'ordre n a au moins n − 1 arêtes et caractériser les graphes bipartis par les cycles
  • Compter les chaînes de longueur k avec les puissances de la matrice d'adjacence

Avant de commencer : Leçon 1 de ce cours (graphes, degrés, matrice d'adjacence) ; produit de matrices ; récurrence.

1Je découvre

Pendant la saison des pluies, un pont s'effondre sur une route de Basse-Guinée. Le service des routes se pose aussitôt deux questions : peut-on encore aller de n'importe quelle ville à n'importe quelle autre ? Et si oui, quel est le trajet le plus court en nombre d'étapes ?

Sur le graphe des liaisons routières, la première question est celle de la connexité : le graphe reste-t-il « d'un seul tenant » après la suppression de l'arête ? La seconde est celle de la distance. Un ingénieur ajoute une troisième question : combien d'itinéraires différents en exactement trois étapes relient Kindia à Boké ? Pour un grand réseau, on ne peut pas les compter à la main ; on verra qu'un simple calcul matriciel y suffit.

Comment décrire les déplacements dans un graphe, reconnaître s'il est connexe et compter les chemins ?

La suite se lit avec votre compte Kharandi Université

La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.

Voir toutes les leçons de Théorie des graphes

Signaler une erreur dans cette leçon

Toutes les leçons de Théorie des graphes

Pose ta question à Karamö