Connexité

Il est parfois utile de pouvoir aller d'un sommet à n'importe quel autre sommet d'un graphe. Par exemple, une compagnie aérienne a intérêt à proposer à ses clients une façon d'aller de n'importe quel aéroport qu'elle dessert à n'importe quel autre aéroport également desservi, sans avoir à faire appel à une autre compagnie sur une partie de la chaîne.

Le concept qui exprime exactement cela s'appelle la connexité d'un graphe. Plus formellement :

Définition 5.6   Un graphe $G$ est connexe si et seulement si $\forall s_1, s_2 \in V(G)$, il existe une chaîne entre $s_1$ et $s_2$.