什么是 Graphe, matrice d’adjacence？

Un graphe est constitué de sommets $1, 2, \dots, n$ et d’arêtes joignant certaines paires de sommets (couples ordonnés pour un graphe orienté). Sa matrice d’adjacence est la matrice $n \times n$ $M$ avec $m_{ij} = 1$ s’il y a une arête de $i$ vers $j$, et $0$ sinon. Un chemin de longueur $k$ de $i$ vers $j$ est une suite de $k$ arêtes consécutives menant de $i$ à $j$.