Graphes orientés, matrice d'adjacence

Après avoir découvert en début d'année le nouvel outil matrice, on s'intéresse maintenant à son utilité en faisant le lien avec les graphes orientés. C'est donc la notion de matrice d'adjacente qui va intervenir ici.

La théorie des graphes est issue d'un problème concret posé à Euler lors d'un de ses nombreux voyages en Prusse.

On va d'abord s'intéresser au graphes sans se soucier d'une possible orientation. Il faut alors découvrir et apprendre tout le vocabulaire pour comprendre les questions.

Dans un second temps, on va donner un sens aux chemins avec les graphes orientés. Le sens imposé va donc modifier en profondeur les matrices d'adjacences. Par exemple, elles ne seront plus nécessairement symétriques.

On pourra évidemment faire intervenir le langage PYTHON, qui nous permettra d'effectuer par exemple une marche aléatoire sur un graphe.

Les Documents en Ligne

Liste des vidéos du chapitre