Concept orienté

Dans beaucoup d’applications, les relations entre les éléments d’un ensemble sont orientées. Un élément $x$ peut être en relation avec un autre élément $y$ sans que $y$ ne soit nécessairement en relation avec $x$ : on parle alors de graphe orienté, ou encore de digraphe. Pour formaliser un graphe, on le note $G = (X, U)$, déterminé par :

  • Un ensemble fini $X = \{X_1, X_2, \dots, X_n\}$ dont les éléments sont appelés sommets (ou nœuds). Si $X$ possède $n$ éléments distincts, le graphe est dit d’ordre $n$ ; on parle aussi de n-graphe.
  • Les éléments de $X$ peuvent être nommés ou associés à une valeur. On peut par exemple définir une fonction $L(X_i)$ pour associer un label à $X_i$, ou encore $V(X_i)$ pour lui attribuer une valeur.
  • Un ensemble fini $U = \{U_1, U_2, \dots, U_m\}$ dont les éléments sont des couples ordonnés de sommets, appelés arcs. $U$ est donc une sous-famille du produit cartésien $X \times X = \{(x, y) \mid x \in X, y \in X\}$. Pour un arc $u = (X_i, X_j)$, $X_i$ est le nœud initial (ou origine) et $X_j$ le nœud final (ou destination).
  • Un arc $u = (X_i, X_i)$ est appelé une boucle, car le nœud initial et le nœud final sont identiques. Les arcs peuvent être nommés pour définir les relations entre objets, ou associés à une valeur (ou poids de transition).
  • Un $p$-graphe est un graphe dans lequel il n’existe jamais plus de $p$ arcs de la forme $(X_i, X_j)$ entre deux sommets quelconques.
  • Attention a ne pas confondre n-graphe et p-graphe : il faut spécifié exemple un 1-graphe est un ???

Supposons les ensembles $X = \{A, B, C, D, E\}$ et $U = \{(A,B), (B,A), (A,D), (A,C), (A,E), (C,D), (C,E), (C,D), (B,C)\}$. Le graphe résultant est le suivant :

graph LR A((A)) B((B)) C((C)) D((D)) E((E)) A -->|u1|B B-->|u2|A A -->|u3|D A -->|u5|C A -->|u6|E C -->|u7|D C -->|u8|E B-->|u4|C C -->|u9|D

Un graphe $G = (X, E)$ est dit simple s’il n’est pas un multi-graphe et s’il n’existe pas de boucles. Un multi-graphe est un graphe pour lequel on permet d’avoir plusieurs arêtes entre deux sommets.

Attention les notations anglaises sont légèrement différentes :

Concept Notation française Nom en français Notation anglaise Nom en anglais
Ensemble de sommets $X$ Sommets / Nœuds $V$ Vertices / Nodes
Un sommet individuel $X_i$ Sommet / Nœud $v_i$ Vertex / Node
Ensemble d’arcs $U$ Arcs $E$ Edges (orienté : arcs)
Un arc individuel $(X_i, X_j)$ Arc (orienté) $(v_i, v_j)$ Edge / Arc
Arc non orienté $\{X_i, X_j\}$ Arête (non orientée) $\{v_i, v_j\}$ Edge (undirected)



Par exemple dans le domaine 3D (blender, jeux vidéo etc) on parle en terme de vertex et d’indices (numéro des vertexes). Un tuple d’indice permet de crée une ligne (deux indices), un triangle (3 indices) ou un quad (4 indices).

Classification par multiplicité des arcs

La valeur de $p$ dans un $p$-graphe détermine la richesse des connexions possibles entre deux sommets. On distingue trois cas principaux.

Monographe (p = 1)

Chaque paire de sommets possède au maximum un arc dans chaque direction. Cela équivaut à un graphe simple classique, sans arcs multiples entre les mêmes sommets.

Exemple :

graph LR X1((X1)) -->X2((X2)) X2 --> X3((X3)) X3 --> X1

Également un 1-graphe :

graph LR A((A)) --> B((B)) A --> C((C)) B --> C C --> B B --> A C --> A

Également un 1-graphe :

graph TD %% Left side nodes (rows) A11(("x11")) --> B11(("x21")) A12(("x12")) --> B11 A13(("x13")) --> B11 A11 --> B12(("x22")) A12 --> B12 A13 --> B12 A11 --> B13(("x23")) A12 --> B13 A13 --> B13

source : Catharine A Baker - 2002

Bigraphe (p = 2)

Jusqu’à deux arcs sont autorisés entre deux sommets donnés. Ils peuvent être de même sens ou de sens opposés, ce qui est utile pour modéliser des relations bidirectionnelles ou des connexions redondantes.

Exemple :

graph LR A((A)) --> B((B)) C((C)) --> A B --> C A --> B

Également un 2-graphe :

flowchart LR A((A)) --> B((B)) B --> A A -.-> B A --> C((C)) C --> A A -.-> C B --> C C --> B B -.-> C

Multigraphe (p > 2)

Plusieurs arcs parallèles sont autorisés entre deux sommets. Ce type de graphe permet de modéliser des systèmes complexes où plusieurs relations distinctes coexistent entre les mêmes entités (par exemple, plusieurs lignes de bus entre deux arrêts, ou plusieurs types de transactions entre deux acteurs).

graph LR %% Left side nodes (rows) A((A)) B((B)) C((C)) A --> C A --> C C --> B B --> C B --> A B --> A B --> A

Exemple d'un 3-graphe (p = 3)
source : Catharine A Baker - 2002

Applications multivoques

L’application $\Gamma$ qui à tout élément de $X$ fait correspondre une partie de $X$ est appelée une application multivoque. Elle formalise les notions de voisinage dans un graphe orienté :

  • $X_j$ est un successeur de $X_i$ si le couple $(X_i, X_j) \in U$.
    L’ensemble des successeurs de $X_i$ est noté $\Gamma(X_i)$.
  • $X_j$ est un prédécesseur de $X_i$ si le couple $(X_j, X_i) \in U$.
    L’ensemble des prédécesseurs de $X_i$ est noté $\Gamma^{-1}(X_i)$.

Remarque : Pour un 1-graphe, $G$ peut être entièrement déterminé par $(X, \Gamma)$, ce qui est une notation à la base d’une représentation informatique très utilisée : les listes d’adjacence voir cours suivant.

Remarque : On peut également définir une fonction $W$ telle que $W^{+}(X_i)$ représente l’ensemble des arcs sortants de $X_i$, et réciproquement $W^{-}(X_i)$ pour les arcs entrants.

Déduction à partir de $\Gamma$

Soit le graphe défini par :

  • $X = \{x_1, x_2, x_3, x_4, x_5\}$
  • $\Gamma(x_1) = \{x_2\}$
  • $\Gamma(x_2) = \{x_1, x_3\}$
  • $\Gamma(x_3) = \{x_4, x_5\}$
  • $\Gamma(x_4) = \{x_5\}$
  • $\Gamma(x_5) = \{x_1, x_2\}$
graph LR x1((x1)) x2((x2)) x3((x3)) x4((x4)) x5((x5)) x1 --> x2 x2 --> x1 x2 --> x3 x3 --> x4 x3 --> x5 x4 --> x5 x5 --> x1 x5 --> x2

Déduction de $W^{+}$ (arcs sortants) :

  • $W^{+}(x_1) = \{(x_1, x_2)\}$
  • $W^{+}(x_2) = \{(x_2, x_1),\ (x_2, x_3)\}$
  • $W^{+}(x_3) = \{(x_3, x_4),\ (x_3, x_5)\}$
  • $W^{+}(x_4) = \{(x_4, x_5)\}$
  • $W^{+}(x_5) = \{(x_5, x_1),\ (x_5, x_2)\}$

Déduction de $W^{-}$ (arcs entrants) :

  • $W^{-}(x_1) = \{(x_2, x_1),\ (x_5, x_1)\}$
  • $W^{-}(x_2) = \{(x_1, x_2),\ (x_5, x_2)\}$
  • $W^{-}(x_3) = \{(x_2, x_3)\}$
  • $W^{-}(x_4) = \{(x_3, x_4)\}$
  • $W^{-}(x_5) = \{(x_3, x_5),\ (x_4, x_5)\}$

Reconstruction à partir de $\Gamma^{-1}$

Dans cet exemple, on connaît les prédécesseurs de chaque sommet et on en déduit le graphe :

  • $X = \{x_1, x_2, x_3, x_4, x_5\}$
  • $\Gamma^{-1}(x_1) = \{x_1, x_3\}$
  • $\Gamma^{-1}(x_2) = \{x_1, x_4\}$
  • $\Gamma^{-1}(x_3) = \{x_3, x_4, x_5\}$
  • $\Gamma^{-1}(x_4) = \{x_2, x_1\}$
  • $\Gamma^{-1}(x_5) = \{x_3, x_5\}$
graph LR x1((x1)) x2((x2)) x3((x3)) x4((x4)) x5((x5)) x1 --> x1 x1 --> x2 x1 --> x4 x2 --> x4 x3 --> x3 x3 --> x1 x3 --> x5 x4 --> x2 x4 --> x3 x4 --> x5 x5 --> x3

Graphes non orientés

Lors de l’étude de certaines propriétés, domaines ou modélisation, l’orientation des arcs ne joue aucun rôle. On s’intéresse alors uniquement à l’existence de liaisons entre deux sommets, sans que l’ordre ne soit précisé. On appelle arête tout arc dont on ignore l’orientation. L’ensemble des liaisons est alors constitué de paires de sommets non ordonnées.

  • On dit qu’une arête $(X_i, X_j)$ est incidente aux sommets $X_i$ et $X_j$.
  • Pour les graphes non orientés, on note souvent $G = (X, E)$ et $e = [X_i, X_j]$.
  • Un multi-graphe $G = (X, E)$ est un graphe dans lequel il existe plusieurs arêtes entre deux mêmes sommets.

Un graphe $G = (X, E)$ est simple s’il n’est pas un multi-graphe et s’il n’existe pas de boucles.

L’exemple ci-dessous montre comment un même ensemble de sommets et de connexions peut être représenté sous forme orientée (digraphe avec arcs dans les deux sens) ou sous forme non orientée (arêtes simples). Les deux représentations sont équivalentes lorsque chaque paire de sommets reliés l’est dans les deux directions :

Exemple comparatif

graph TB subgraph Orienté A((A)) --> B((B)) A --> C((C)) B --> C C --> B B --> A C --> A end subgraph Non-Orienté A1((A)) --- B1((B)) A1 --- C1((C)) B1 --- C1 end