Article Index

Page 1 of 2

Introduction à la théorie des graphes

La théorie des graphes concerne de nombreux domaines d'application, leurs objectifs sont différents mais le langage utilisé est le même. Les graphes sont utilisés pour modéliser des ensembles structurés, complexes, avec de nombreuses applications, telles que la modélisation dans le temps (en économie ou automatique) ou dans des réseaux divers (électrique, routier, adduction d'eau, ...). La théori des graphes est née en 1736 quand Euler démontra qu'il était impossible de traverssr chacun des 7 ponts de la ville russe de Könisberg (KalininGrad) une fois exactement et de revenir au point de départ :

https://upload.wikimedia.org/wikipedia/commons/5/5d/Konigsberg_bridges.png

De manière général, un graphe permet de représenter simplement la structure, les cheminements possibles dans un grand nombre de situations en expriment les relations et les dépendances entre les éléments. Par exemple dans un réseau férroviaire, un arbre généalogique, le diagramme de succession de tâche en gestion .... etc. En plus de son existence purement mathématique, le graphe est aussi une structure de données en informatique, les applications sont nombreuses et indispenssable pour résoudre bon nombres de problèmes d'optimisation.

Concepts orientés

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 notera donc le graphe $G=(X,U)$ qui est déterminer par :

  • Un ensemble fini $X={X_1, X_2, ..., X_n}$ dont les éléments sont appelés sommets (ou noeud)
    si $X$ possède $n$ éléments distincts, le graphe sera dit d'ordre n
  • Un ensemble finit $U={U_1, U_2, ..., U_n}$ dont les éléments sont des couples ordonnées de sommets appelés arcs.
    U est donc une famille du produit cartésion $X*X = {(x,y) | x \in X, y \in X}$
  • Pour un arc $u=(X_i,X_j)$, $X_i$ est le noeud initial/origine et $X_j$ le noeud final/destination

Un P-graphe est un graphe dans le quel il n'existe jamais plus de p arcs de la forme $(X_i,X_j)$ entre deux sommets quelconques. Exemple avec un 3-graphe :

https://www.cairn.info/loadimg.php?FILE=EG/EG_321/EG_321_0060/EG_idPAS_D_ISBN_pu2003-01s_sa06_art06_img006.jpg

Applications multivoques

L'application $\Gamma$ qui à tout élément de $X$ fait correspondre une partie de $X$ est appelée une application multivoque :

  • $X_j$ est le 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 le prédécesseur de $X_i$ si le couple $(X_i,X_j) \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 déterminer par $(X,\Gamma)$ qui est une notation à la base d'une représentation informatique très utilisée, à savoir les listes d'adjacence.
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.

Graphes non orientés

Lors de l'étude de certaines propriétés il arrive que l'orientation des arcs ne joue aucun rôle. On s'intéresse uniquement à l'existence d'arcs entre deux sommets sans que l'ordre ne soit précisé. On appel arrête tout arc sans orientation. L'ensemble $U$ est alors constitué de paires de sommets ordonnés.

  • On dit que $u$ est incidente au sommet pour une arrête $(X_i,X_j)$
  • Pour les graphes non orientés au lieu de noter $G=(X,U)$ et $u=(X_i,X_j)$, on préfère souvent $G=(X,E)$ et $e=[X_i,X_j]$
  • Un multi-graphe $G=(X,E)$ est un graphe dans lequel il existe plusieurs arrêtes entre deux sommets
  • Un graphe $G=(X,E)$ est simple s'il n'est pas multi-graphe et s'il n'existe pas de boucles
  • $G_s=(X_s,V)$ est un sous-graphe de $G$ ou $V$ est l'enssemble des arcs ayant leurs extremites dans $X_s$

Proprietes de certain graphe

  • Graphe reflexif
    • tous les sommets comportent une boucle
    • $\forall x_i \in X, (x_i,x_i) \in U$
  • Graphe irreflexif
    • aucune boucle local
    • $\forall x_i \in X, (x_i,x_i) \not\in U$
  • Graphe symetrique
    • tout sommet lies entre eux est lies dans les deux sens
    • $\forall x_i,x_j \in X, (x_i,x_j) \in U \implies (x_j,x_i) \in U$
  • Graphe asymetrique
    • pas plus d'un arc entre deux sommet, pas de boucle
    • $\forall x_i,x_j \in X, (x_i,x_j) \in U \implies (x_j,x_i) \not\in U$
  • Graphe antisymetrique
    • pas plus d'un arc entre deux sommet,boucle possible
    • $\forall x_i,x_j \in X, x_i \not = x_j, (x_i,x_j) \in U \implies (x_j,x_i) \not\in U$
  • Graphe transitif
    • s'il existe un chemin $x_i \rightarrow x_j \rightarrow x_k$ alors il existe aussi un chemain $x_k \rightarrow x_i$
    • $\forall x_i,x_j,x_k \in X, (x_i,x_j) \in U, (x_j,x_k) \in U \implies (x_i,x_k) \in U$
  • Graphe complet
    • s'il n'existe pas de sommet isole
    • $\forall x_i,x_j \in X, x_i \not = x_j, (x_i,x_j) \not\in U \implies (x_j,x_i) \in U$
  • Graphe simple
    • si tout les arcs sont distincs et s'il n'y a pas de boucles
  • Clique
    • C'est un sous-graphe de $G$ telque tout couple de sommets distincts de $\tilde X$ est relie par un arc ou une arrete de $\tilde E$
    • $\tilde G = (\tilde X, \tilde E), \tilde X \not\in X$
  • Tournoi
    • C'est un graphe complet et asymetrique