Connexité par arcs est une notion fondamentale en théorie des graphes. Elle caractérise les graphes où chaque sommet peut rejoindre tout autre via une suite d’arêtes. Cette propriété est cruciale pour l’analyse des réseaux et des structures discrètes.

Connexité par arcs

Soit $G = (V, E)$ un graphe non orienté simple. Les sommets sont les éléments de $V$. Les arêtes sont les couples non ordonnés $\{u, v\}$ avec $u \neq v$.

Définition formelle du chemin

Un chemin de $u$ à $v$ est une suite finie de sommets $(v_0, v_1, \dots, v_k)$ telle que :

• $v_0 = u$ et $v_k = v$,
• pour tout $i \in \{0, \dots, k-1\}$, $\{v_i, v_{i+1}\} \in E$.

Le nombre $k$ est la longueur du chemin. Les sommets peuvent se répéter.

Définition de la connexité par arcs

Le graphe $G$ est connexe par arcs si pour tout $u, v \in V$, il existe un chemin de $u$ à $v$. Sinon, $G$ est non connexe.

Théorèmes et propriétés

Relation d’équivalence

On définit la relation binaire $\sim$ sur $V$ par : $u \sim v \iff \exists$ un chemin de $u$ à $v$.

Théorème 1. $\sim$ est une relation d’équivalence.

Preuve :

• Réflexivité. Pour tout $u \in V$, le chemin $(u)$ (de longueur 0) relie $u$ à lui-même. Donc $u \sim u$.
• Symétrie. Si $u \sim v$, il existe un chemin $P = (v_0=u, v_1, \dots, v_k=v)$. Le chemin inverse $P’ = (v_k, v_{k-1}, \dots, v_0)$ relie $v$ à $u$. Donc $v \sim u$.
• Transitivité. Si $u \sim v$ et $v \sim w$, il existe un chemin $P_1$ de $u$ à $v$ et un chemin $P_2$ de $v$ à $w$. En concaténant $P_1$ et $P_2$ (en identifiant le sommet commun $v$), on obtient un chemin de $u$ à $w$. Donc $u \sim w$. $\blacksquare$

Composantes connexes maximales

Les classes d’équivalence de $\sim$ sont appelées composantes connexes par arcs.

Théorème 2. Soit $C$ une composante connexe par arcs. Alors :

• Le sous-graphe induit $G[C]$ est connexe par arcs.
• $C$ est maximal pour cette propriété : l’ajout de tout sommet $x \notin C$ rend le sous-graphe induit non connexe.

Preuve :

• Connexité de $G[C]$. Soient $u, v \in C$. Par définition, il existe un chemin $P$ dans $G$ de $u$ à $v$. Tout sommet $w$ de $P$ vérifie $u \sim w$ et $w \sim v$, donc $w \in C$. Ainsi $P \subseteq C$, et $P$ est aussi un chemin dans $G[C]$. Donc $G[C]$ est connexe.
• Maximalité. Soit $x \notin C$. Si $x$ était adjacent à un sommet $c \in C$, alors $\{x,c\} \in E$, donc $x \sim c$, ce qui impliquerait $x \in C$, contradiction. Ainsi aucune arête ne relie $x$ à un sommet de $C$. Dans le sous-graphe induit par $C \cup \{x\}$, le sommet $x$ n’est adjacent à aucun sommet de $C$. Donc $x$ et tout sommet de $C$ ne sont pas connectés. Le sous-graphe n’est pas connexe. $\blacksquare$

Exemples et contre-exemples

Exemples de graphes connexes

• Graphe complet $K_n$. Toute paire de sommets est directement reliée par une arête. Donc le graphe est connexe.
• Cycle $C_n$. Le chemin circulaire $(v_1, v_2, \dots, v_n, v_1)$ permet de relier tous les sommets.
• Arbre. Un arbre est un graphe connexe et acyclique. Par définition, il est connexe.

Contre-exemples

• Deux sommets isolés. $V = \{a,b\}$, $E = \emptyset$. Aucun chemin ne relie $a$ et $b$. Le graphe a deux composantes : $\{a\}$ et $\{b\}$.
• Deux triangles disjoints. $G$ consiste en deux copies de $K_3$ sans arêtes entre elles. Chaque triangle est une composante connexe. Le graphe total n’est pas connexe.

Conclusion et ressources

La connexité par arcs est une relation d’équivalence dont les classes sont des sous-graphes induits maximaux. Cette notion permet de décomposer un graphe en blocs homogènes. Elle intervient dans de nombreux algorithmes, comme la recherche en profondeur (DFS) ou en largeur (BFS) pour détecter les composantes.

Pour approfondir ces notions, consultez notre collection de cours et exercices de mathématiques supérieur, licence et prépa. Des ressources complémentaires sont également disponibles sur CultureMath.