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 :

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 :

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)$

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

Representation d'un graphe

Il existe plusieurs types de représentation pour décrire un graphe. On distingue principalement la représentation par matrice d'adjacence, par matrice d'incidence sommet-arcs et par liste d'adjacences.

Matrice d'adjacence

Pour un 1-graphe, la matrice d'adjacence fait correspondre les sommets origines des arcs (classes en ligne dans la matrice) au sommets destination (classes en colonnes dans la matrice). Dans un formalisme matrices booléenne, l'existence d'un arc $(x_i,x_j)$  se traduit par la présence d'un 1 a l'intersection de la ligne $x_i$ et de la conne $x_j$ et l'absence d'un arc par un 0. Dans un autre formalisme, la valeur correspond a un poid de transition sur l'arc, s'il n'existe pas d'arc, le poid est fixe a $-1$. C'est une des représentations les plus utilisées.

donc par exemple on peu simplement utiliser une matrice numpy pour ce type de representation :

n = 4 # number_of_nodes
connection = np.zeros((n,n))
connection[0,0] = 1 # boucle sur x_1
connection[0,2] = 1 # arc de x_1 -> x_3
# etc ....

Matrice d'incidence sommet-arc

Pour établir cette matrice, les lignes sont constituées des sommets du graphe et les connes sont constituées des arcs. On pose la valeur $1$ pour le sommet d'origine et $-1$ pour le sommet de destination.

encore une fois une simple matrice numpy peu etre utilise, mais ce type de representation est moin flexible a la modification (ajout / suppression d'arc plus couteux)

n = 2 # number_of_nodes
m = 1 # number_of_arcs
connection = np.zeros((n,m))
connection[0,0] = -1 # arc de x_1
connection[1,0] = 1 # vers x_2

Liste d'adjacence

L'objectif ici est de représenter chaque arc par sont extréminée finale, l'extrémintée initial étant défini implicitement. On pose alors que tout les arcs émanant d'un même sommet sont liés entre eux dans une liste. A chaque arc sont associés le sommet de destination et le pointeur au prochain sommet de la liste. Pour un 1-graphe, il y a un avantage à utiliser la représentation par liste d'adjacence grâce à l'application $\Gamma$ car il y a un gain en place mémoire par rapport à la matrice d'adjacence. Elle est donc mieux adapté pour une implémentation.

La représentation par liste d'adjacence nécéssite la création de deux tableaux. Un premier nommé $LP$ (ListePointeur) de dimension $n+1$ et un second nommé $LS$ (Liste Successeurs) de dimension $m$ pour les graphes orientés et $2m$ pour les graphes non-orienté. Pour chaque sommet $i$, la liste des successeurs de $i$ est contenue dans le tableau $LS$ à partir de la case numéro $LP[i]$. L'ensemble des informations relatives au sommet $i$ est contenue dans les cases $LP[i]$ à $LP[i+1]-1$ du tableau $LS$.

• $w^{+}(i) = LP[i+1] - LP[i]$ dans le cas orienté
• $w^{+}(i) = LP[i+1] - LP[i]$ dans le cas non-orienté $\rightarrow$ identique
• $LP[i] = 1 + \sum_{j=1}^{i-1}{w^{+}(j)}$

Cette représentation revient à décrire le graphe par sont application multivoque $i \rightarrow \Gamma(i)$

1. On construit $LS$ par $\Gamma(1], \Gamma(2], ..., \Gamma(n]$
2. On construit $LP$ qui donne pour tout sommet l'indice dans $LS$ ou commence la liste des successeurs.
3. Pour le sommet $i$, son premier suivant est $LS[LP[i]]$ et le second $LS[LP[i+1]]$
   L'enssemble ce situe dans les border $LP[i]$ et $LP[i+1]-1$ du tableau $LS$
4. Si un sommet $i$ n'a pas de successeur, on pose $LP[i]=LP[i+1]$.
   C'est à dire une liste coincée entre les successeurs de $i-1$ et $i+1$.

La place mémoire utilisé est $n^2$ pour un graphe d'ordre n. Mais cette fois-ci il existe plusieurs implémentations possibles et on peu ce simplifier un peu la vie en programmation, en utilisant un peu plus de mémoire, c'est a dire en utilisant une liste pour chaque noeud, ce qui simplifie grandement les manipulations et l'ajout/suppression d'arcs :

nodes = [[] for _ in range(nomber_of_nodes)]
nodes[0] = [1] # liste des successeurs de x_1
nodes[1] = [0,2] # liste des successeurs de x_2
nodes[2] = [0,1,4]
nodes[3] = [2]
nodes[4] = [5]
nodes[5] = [2,5] # boucle local

Par contre ce type de représentation ne permet pas de modéliser le poids des arcs, il faut donc rajouter un autres tableau similaire a $LS$ qui en contiendra les poids des arcs. On pourrais également aller plus loin en utilisant des classes.

Voir aussi jerryyin.info