Accueil  / Semaine 11 / Introduction à la théorie des graphes dirigés

Introduction à la théorie des graphes dirigés

Petit rappel

Il est possible que vous sentiez le besoin de revoir le texte sur les vecteurs et matrices de la première semaine avant de lire le présent texte. Dans ce cas, n’hésitez pas à le revoir.

Graphes dirigés

Un graphe dirigé est un concept mathématique que nous allons utiliser pour modéliser le web. Si V est l’ensemble des « sommets », et que E est l’ensemble des liens (arêtes) entre deux sommets, alors (V,G) est un graphe. On dit que le graphe est dirigé si les arêtes sont à sens unique (si le sommet A est lié au sommet B, alors le sommet B n’est pas nécessairement lié au sommet A) : on appelle alors les liens entre les sommets des arcs.

Par exemple, si l’ensemble des sommets est un ensemble de bigrammes, et que la relation recherchée entre les bigrammes est du type « le premier se termine par la lettre avec laquelle le second débute », alors nous pourrions avoir le graphe dirigé suivant :

Exemple de graphe dirigé

Ce type de graphe est un exemple simple de graphe de « de Bruijn ». Un graphe de de Bruijn est un graphe où les sommets sont des n-grammes et où deux sommets sont liés seulement si le premier n-gramme se termine par un n-1-gramme débutant le second n-gramme (comme dans « ABC » et « BCD »).

Un graphe peut aussi être représenté par une « matrice d’adjacence ». Pour construire la matrice d’adjacence, il suffit de faire la liste des n sommets [1] et de construire une matrice n par n où la première colonne (et rangée) correspond au premier sommet, et ainsi de suite. On place alors soit la valeur 0, soit la valeur 1, dans chaque composante de la matrice selon qu’il y a un lien entre le sommet correspondant à la rangée, et le sommet correspondant à la colonne (valeur « 1 ») ou non (valeur « 0 »).

Par exemple, la matrice d’adjacence de notre graphe de bigrammes est la matrice suivante (avec les bigrammes dans l’ordre « AB,BC,CA ») :

\left [ \begin{array}{lll} 
0  &   1  & 0   \\
 0  & 0   &   1 \\
  1  & 0   & 0 \end{array}  \right  ].

Naturellement, on peut aussi associer des poids à chaque arc, comme dans cet exemple :

Distance des trajets entre quelques villes

Dans la matrice d’adjacence, on peut alors remplacer les 0 et les 1 par les poids correspondants :

\left [ \begin{array}{lll} - & 450 & 120 \\ - & - & 330\\ - & 310 & - \end{array} \right ]

digraph road "Montréal" -> "Québec" [ label = "450 km" ] ; "Montréal" -> "Drummondville" [ label = "120 km" ] ; "Québec" -> "Drummondville" [ label = "330 km" ] ; "Drummondville" -> "Québec" [ label = "310 km" ] ;

Les degrés

Le degré d’un sommet est le nombre d’arêtes auquel il appartient. Le degré entrant d’un sommet est nombre d’arêtes se terminant sur le sommet alors que le degré sortant est le nombre d’arêtes partant du sommet en question. Par exemple, dans le graphe précédent, le sommet « Montréal » a un degré sortant de 2 et un degré entrant de zéro.

Autres termes

Un sous-graphe est tout simplement une partie d’un graphe où on n’a choisi que quelques sommets.

Une clique est un graphe tel qu’il y a un arc entre tous les sommets : tout le monde est lié à tout le monde.

Un graphe bipartie est un graphe qu’on peut découper en deux parties (deux groupes de sommets) telles qu’il n’y a aucun arc entre deux sommets du même groupe.


[1L’ordre des sommets importe peu.