← Retour aux chapitres de Maths Expertes
Graphes
GRA-1 : Maîtriser le vocabulaire et les degrés
À retenir. La somme des degrés vaut $2\times$ le nombre d’arêtes. Un graphe simple à $n$ sommets a au plus $\frac{n(n-1)}2$ arêtes.
GRA-2 : Utiliser la matrice d’adjacence et compter des chemins
À retenir. Le coefficient $(i,j)$ de $M^k$ est le nombre de chaînes de longueur $k$ de $i$ à $j$.
GRA-3 : Étudier connexité et chaînes eulériennes
À retenir. Graphe connexe : chaîne eulérienne $\iff$ $0$ ou $2$ sommets de degré impair ; cycle eulérien $\iff$ tous les degrés sont pairs.
GRA-4 : Chercher un plus court chemin dans un graphe pondéré
À retenir. Algorithme de Dijkstra : fixer le sommet non traité le plus proche, mettre à jour les distances de ses voisins, recommencer. Le chemin direct n’est pas toujours le plus court.