Résumé visuel des principales notions utilisées dans ce livre.

〈u, v〉 est l’arête entre u et v.
Deux sommets u et v sont voisins si le graphe contient l’arête 〈u, v〉. Par exemple, dans le graphe de la figure 1, les sommets 1 et 5 sont voisins, comme les sommets 5 et 3, ainsi que 3 et 4, etc. En revanche, 2 et 4 ne sont pas voisins (il n’y a pas d’arête entre 2 et 4). Le degré d’un sommet dans un graphe est son nombre de voisins. Par exemple, le sommet 5 est de degré 4, le sommet 1 est de degré 1.Un graphe est connexe s’il existe un chemin entre chaque paire de sommets.
Un arbre est un graphe connexe sans cycle.
Un couplage est un ensemble d’arêtes qui n’ont aucun sommet en commun…