Graphe orienté et non-orienté

Imaginez quatre carrefours reliés par des routes. Si chaque route se parcourt dans les deux sens, un simple trait entre deux carrefours suffit : le graphe est non orienté. Si certaines routes sont à sens unique, il faut dessiner des flèches : le graphe est orienté. Une flèche de A vers B autorise ce trajet, mais ne garantit pas le retour de B vers A. Les points sont les sommets ; les traits sans flèche sont des arêtes et les flèches sont des arcs.

Dans la convention d’un graphe simple, un graphe est décrit par un ensemble de sommets, noté V, et un ensemble de liens, noté E. On l’écrit G = (V, E). Les sommets représentent les objets étudiés ; les liens indiquent quelles paires d’objets sont en relation. Si les liens multiples sont autorisés, leurs occurrences doivent être distinguées dans E ou enregistrées avec leur multiplicité. La position des sommets dans une représentation graphique et la longueur des liens ne font pas partie de cette définition.

Dans un graphe non orienté, un lien est une arête : la paire {u, v} n’a pas d’ordre, si bien que u est relié à v comme v l’est à u. Dans un graphe orienté, aussi appelé digraphe, un lien est un arc : le couple (u, v) est ordonné et se lit « de u vers v ». L’arc (u, v) ne donne donc aucune information sur l’existence de l’arc (v, u).

Deux sommets reliés sont adjacents. Dans le cas non orienté, le degré d’un sommet compte ses arêtes incidentes. Dans le cas orienté, le degré entrant compte les arcs qui arrivent et le degré sortant ceux qui partent. Cette distinction convient aux relations symétriques ou asymétriques, des routes aux contraintes de précédence.

Un graphe réunit quatre éléments de lecture. Les sommets forment l’ensemble V et portent les objets. Les liens forment l’ensemble E et relient certains sommets. Leur nature dépend de l’orientation : une arête associe deux sommets sans ordre, tandis qu’un arc possède une origine et une extrémité. L’adjacence découle des liens présents. Les degrés découlent à leur tour du nombre de liens incidents, entrants ou sortants.

Les ensembles V et E suffisent à reconstruire le graphe et à calculer les degrés. En revanche, déplacer un sommet, courber un lien ou changer la couleur du dessin ne change pas le graphe. Dans un digraphe, effacer les pointes des flèches change l’information : après identification des sens dans un graphe simple, deux arcs opposés éventuels deviennent une seule arête ; si chaque lien est conservé, ils deviennent deux arêtes parallèles.

Un réseau possède quatre carrefours A, B, C et D. Ses cinq sens uniques sont A vers B, A vers C, C vers B, B vers D et D vers C. La figure montre ces données avec puis sans orientation.

1. Placez les quatre sommets et les cinq arcs. Aucun arc B vers A n’est annoncé : le trajet A vers B ne vaut pas dans l’autre sens.

2. De A, deux arcs partent et aucun n’arrive : ses degrés sortant et entrant valent 2 et 0. De B, un arc part et deux arrivent.

3. Pour chaque sommet v, notons d⁺(v) son degré sortant et d⁻(v) son degré entrant. Les totaux valent 2 + 1 + 1 + 1 = 5 et 0 + 2 + 2 + 1 = 5. Chaque arc figure une fois dans chaque total : ${\sum }_{v\in V}{d}^{+}(v)={\sum }_{v\in V}{d}^{-}(v)=5\backslash sum\_\{v\; \backslash in\; V\}\; d^+(v)=\backslash sum\_\{v\; \backslash in\; V\}\; d^-(v)=5$.

4. Effacez les pointes. Le graphe devient non orienté, avec les arêtes {A, B}, {A, C}, {B, C}, {B, D} et {C, D}.

Le contrôle donne les degrés 2, 3, 3 et 2. Leur somme vaut 10, soit deux fois 5, car chaque arête touche deux sommets.

Pour représenter des routes, choisissez un graphe orienté dès qu’un trajet autorisé dans un sens peut être interdit dans l’autre. Si toutes les voies sont à double sens, le graphe non orienté évite de doubler inutilement les liens.

Pour organiser des tâches, un arc de A vers B peut signaler que A doit précéder B. Une arête non orientée ne conviendrait pas, car la relation de précédence n’est pas symétrique.

Pour décrire une relation mutuelle, comme deux objets simplement reliés, utilisez un graphe non orienté. Le bon test est toujours le même : inverser les deux sommets conserve-t-il exactement l’information ?

Graphe orienté et graphe pondéré. L’orientation donne un sens aux liens ; une pondération leur associe une valeur. Une route A vers B marquée 7 possède à la fois une direction et un poids : les deux propriétés sont indépendantes.

Orientation et connexité. L’orientation indique comment parcourir chaque lien ; la connexité demande quels sommets peuvent être rejoints. Un graphe peut avoir des flèches tout en laissant certains sommets inaccessibles depuis A.

Arc et arête. Un arc possède une origine et une extrémité, contrairement à une arête. Entre A et B, les arcs A vers B et B vers A sont deux liens distincts, alors que l’arête {A, B} n’en forme qu’un.

Deux flèches opposées. Voir A vers B et B vers A ne transforme pas le digraphe en graphe non orienté : il reste deux arcs. Il faut conserver les deux sens dans les calculs de degrés.

Boucle. Un lien peut partir d’un sommet et revenir au même sommet si la convention choisie autorise les boucles. Dans un digraphe, cette boucle ajoute alors 1 au degré entrant et 1 au degré sortant du sommet.

Liens multiples. Certaines définitions autorisent plusieurs liens entre les deux mêmes sommets, d’autres imposent un graphe simple. Avant de compter, il faut préciser la convention et conserver chaque lien autorisé comme une donnée distincte.

Croisement du dessin. Deux arêtes qui se croisent ne créent pas automatiquement un sommet. Un nouveau sommet existe seulement s’il appartient à V et si les liens de E y aboutissent.

matrice d'adjacence. Encodez les liens d’un graphe dans une grille et observez comment l’orientation rend cette grille potentiellement non symétrique.

degré d'un sommet d'un graphe. Approfondissez le comptage des liens incidents et la distinction entre degrés entrant et sortant.

arc. Précisez le rôle d’un lien dirigé et sa lecture entre une origine et une extrémité.