Connexité unilatérale (graphe)

Imaginez des villes reliées par des routes à sens unique. Entre deux villes quelconques, il suffit qu’un itinéraire existe dans un sens au moins : on peut aller de la première à la seconde, ou revenir dans l’autre sens, sans exiger les deux trajets. Le réseau est alors un graphe orienté unilatéralement connexe. Une chaîne A → B → C → D en donne un exemple : chaque ville placée plus tôt peut atteindre celles qui suivent, mais aucun trajet ne remonte la chaîne.

La connexité unilatérale est une propriété d’un graphe orienté, c’est-à-dire d’un ensemble de sommets reliés par des arcs auxquels un sens est attribué. Pour deux sommets distincts quelconques, notés u et v, on doit pouvoir trouver un chemin orienté de u vers v ou un chemin orienté de v vers u. Le choix du sens peut changer d’une paire à l’autre.

Dans la chaîne A → B → C → D, le chemin A → B → C relie A à C et le chemin B → C → D relie B à D. Plus généralement, tout sommet situé plus tôt dans la chaîne atteint tout sommet situé plus tard. Le graphe est donc unilatéralement connexe. La propriété concerne l’existence d’un chemin, pas nécessairement d’un arc direct.

La connexité simple oublie le sens des arcs et demande seulement une liaison dans le graphe sous-jacent. La forte connexité exige, pour chaque paire, un chemin dans les deux sens. La connexité unilatérale se situe entre ces deux exigences : elle conserve l’orientation, tout en n’imposant qu’un sens accessible pour chaque paire.

Un graphe orienté possède quatre éléments utiles ici. Les sommets représentent les points comparés, les arcs relient deux sommets, la flèche de chaque arc fixe le sens du déplacement et un chemin est une suite d’arcs dont les extrémités s’enchaînent. La connexité unilatérale dépend donc des sommets, des arcs et de leur orientation, non de la forme du dessin ni de la couleur des flèches.

Dans A → B → C → D, l’arc A → B fournit le premier pas, puis B → C et C → D prolongent les chemins. La présence de B → C permet d’atteindre C depuis A parce que les arcs s’enchaînent. Inversement, l’absence d’un arc vers l’amont empêche de remonter la chaîne. Ces données suffisent à vérifier la propriété pour chaque paire.

Considérons quatre sommets placés dans une chaîne orientée. Les données sont : A, B, C et D ; les arcs A → B, B → C et C → D ; aucun arc dans le sens inverse.

Pour les six paires non ordonnées, on peut choisir le sens suivant : A–B, A → B ; A–C, A → B → C ; A–D, A → B → C → D ; B–C, B → C ; B–D, B → C → D ; C–D, C → D. Chaque paire dispose ainsi d’un chemin orienté dans au moins un sens, sans qu’un retour soit nécessaire.

Chaque paire de sommets possède donc un chemin dans au moins un sens. Le graphe est unilatéralement connexe. Le contrôle consiste à examiner les six paires non ordonnées de sommets, puis à trouver pour chacune un sens de parcours, sans exiger un retour.

Dans un graphe de dépendances, un sommet peut représenter une tâche et un arc orienté une dépendance. Vérifier la connexité unilatérale aide à savoir si deux tâches sont reliées par une chaîne de dépendances dans au moins un sens. Si aucune chaîne n’existe entre une paire, il faut traiter les composantes séparément.

Dans un réseau de communication orienté, la même vérification indique si deux points peuvent être reliés par un itinéraire dans au moins une direction. Elle ne garantit pas un échange réciproque : pour cela, le critère pertinent est la forte connexité.

La connexité simple ne tient pas compte des flèches. Un graphe dont les arcs forment A → B et C → B est simplement connexe, car son dessin non orienté relie les trois sommets, mais il n’est pas unilatéralement connexe : A et C n’ont de chemin dans aucun sens.

La forte connexité demande davantage. Dans A → B → C → D, D n’atteint pas A, alors le graphe n’est pas fortement connexe, même s’il est unilatéralement connexe. Un chemin dans un sens suffit pour la connexité unilatérale ; les deux sens sont nécessaires pour la forte connexité.

Le piège principal consiste à confondre une paire d’arcs opposés avec un chemin dans les deux sens pour tout le graphe. Deux sommets peuvent communiquer réciproquement tandis qu’un troisième reste inaccessible depuis eux. Il faut alors vérifier toutes les paires, et non conclure à partir d’un seul cycle.

Un graphe avec plusieurs composantes séparées échoue immédiatement : si aucune suite d’arcs ne relie un sommet d’une composante à un sommet d’une autre, cette paire n’est accessible dans aucun sens. La propriété se vérifie sur les sommets du graphe considéré ; elle ne se récupère pas en ajoutant mentalement des liaisons non dessinées.

Enfin, l’expression « dans un sens ou dans l’autre » autorise un seul sens pour une paire. Exiger systématiquement un aller-retour transforme le test en critère de forte connexité et écarte à tort la chaîne A → B → C → D.

Un prolongement naturel consiste à étudier les composantes fortement connexes. Elles regroupent les sommets qui peuvent s’atteindre réciproquement ; leur condensation forme un graphe orienté sans cycle entre composantes. Cette lecture permet de repérer où la circulation est réversible et où elle ne fonctionne que dans un sens.