Graphes

Le cours sera fait en classe, sur des feuilles de papier.

Activités

1. TP POO : Dessiner des graphes avec Graphviz sur Capytale

Matrices

Les matrices permettent de représenter les graphes et de les coder en Python.

1. Cours et exercices interactifs : matrices
2. Cours et exercices interactifs : lecture et modification d'un élément d'une matrice
3. TP-cours : écriture de matrices et tic-tac-toe sur Capytale
4. TP : matrices et images sur Capytale
5. Exercice interactif : matrice d'un graphe simple
6. Exercice interactif : matrice d'un graphe orienté
7. TP : représentation de graphes par des matrices sur Capytale

Dictionnaires

Il est également possible de coder des graphes à l'aide de dictionnaires.

1. Cours sur les dictionnaires en vidéo sur le site de Lumni
2. TP-cours sur Capytale
3. TP : Graphes : Implantation par listes de successeurs sur Capytale
4. Ex 2 du sujet de bac écrit 21-NSIJ1G11
5. Ex 2 partie B du sujet de bac écrit 24-NSIJ1AN1
6. Ex 3 du sujet de bac écrit 24-NSIJ2ME1

Parcours d'un graphe

1. Aglorithmes de parcours de graphes en PDF
2. Cadeaux circulaires sur Codex
3. Tourner en rond sur Codex

Chaîne, chemin, cycle

• Dans un graphe non orienté, une chaîne est une suite de sommets dont chacun est un voisin du précédent.
• Un chemin est, dans un graphe orienté, une suite de sommets dont chacun est un successeur du précédent.
• Un cycle est un chemin ou une chaîne où le premier sommet est égal au dernier.

En vidéo

Qui a tué le duc de Densmore ? Graphe d'intervalles

L'énigme des trois maisons : graphe planaire

Chemin le plus court : l'algorihtme de Dijkstra