Graphes et réseaux

Historique - Promenade sur les ponts de Königsberg

La théorie des graphes prend naissance au 17^ème siècle à Königsberg (actuellement la ville russe Kaliningrad) dans laquelle sept ponts permettent de relier les différentes parties de la ville traversée par une rivière:

Königsberg et ses ponts *(source: Wikipédia)*

Le problème connu à l'époque était de savoir s'il était possible de se promener dans la ville en traversant chaque pont une seule fois, et en revenant finalement au point de départ.

Exercice 1

Qu'en pensez-vous ?

Leonhard Euler résolu ce problème en 1736. Le problème initial et sa réponse semblent maintenant bien ludiques voire insignifiants mais les travaux et les développements proposés par Euler le sont beaucoup moins.
Ce problème peut tout d'abord se schématiser:

et même par le graphe

$\psset{unit=1.5cm,linewidth=1.5pt} \begin{pspicture}(0,0)(5,5) \pscurve(2,0)(1,.2)(-.1,2) \pscurve(.2,1.9)(1.4,1)(2,0) \psline(2,0)(4,2) \psline(0,2)(4,2) \psline(4,2)(2,4) \pscurve(-.1,2)(1,3.8)(2,4) \pscurve(1.9,3.9)(1.4,3)(0,2) \pscircle[fillstyle=solid,fillcolor=blue](2,0){.3} \pscircle[fillstyle=solid,fillcolor=blue](2,4){.3} \pscircle[fillstyle=solid,fillcolor=blue](0,2){.3} \pscircle[fillstyle=solid,fillcolor=blue](4,2){.3} \end{pspicture}$

Graphe

Un graphe est un modèle abstrait constitué par des sommets (aussi appelés nœuds ou points) et des arêtes (ou liens) reliant ces sommets.
Un graphe peut être symétrique, ou non-orienté, comme c'est le cas précédemment pour les sept ponts de Königsberg.
Un graphe peut aussi être orienté, par exemple en transposant l'exemple précédent à une époque contemporaine et où, entre autre, les ponts seraient à sens unique; chaque arête du graphe est donc une flèche qui représente le sens de parcours.

Voir aussi réseaux et graphes, quelques généralités, principes et applications.

La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes. Cette théorie permet d'étudier, et de fournir des méthodes de résolution de problèmes, dans de nombreux domaines:

Problème logistique

Dans le même registre que Königsberg, un livreur doit passer par les villes A, B, C et D. Bien sûr il est préférable qu'il ne passe pas plusieurs fois par la même ville.

$\psset{unit=1cm,linewidth=1.5pt} \begin{pspicture}(-.3,-.3)(4.3,4.3) \psline(0,0)(4,0)(4,4)(0,4)(0,0)(4,4) \psline(0,4)(4,0) \pscircle[fillstyle=solid,fillcolor=blue](0,4){.3}\rput(0,4){\bf\white A} \pscircle[fillstyle=solid,fillcolor=blue](4,4){.3}\rput(4,4){\bf\white B} \pscircle[fillstyle=solid,fillcolor=blue](4,0){.3}\rput(4,0){\bf\white D} \pscircle[fillstyle=solid,fillcolor=blue](0,0){.3}\rput(0,0){\bf\white C} \end{pspicture}$

Exercice 2

Donner plusieurs itinéraires possibles.

Dans le graphe précédent, on peut aussi prendre en compte les distances entre chaque ville, on obtient un graphe pondéré:

$\psset{unit=1cm,linewidth=1.5pt} \begin{pspicture}(-1,-.4)(5,4.4) \psline(0,0)(4,0)(4,4)(0,4)(0,0)(4,4) \psline(0,4)(4,0) \pscircle[fillstyle=solid,fillcolor=blue](0,4){.3}\rput(0,4){\bf\white A} \pscircle[fillstyle=solid,fillcolor=blue](4,4){.3}\rput(4,4){\bf\white B} \pscircle[fillstyle=solid,fillcolor=blue](4,0){.3}\rput(4,0){\bf\white D} \pscircle[fillstyle=solid,fillcolor=blue](0,0){.3}\rput(0,0){\bf\white C} \rput(2,4.2){4\,km} \rput[l](4.1,2){2 km} \rput[r](-.1,2){3 km} \rput(2,-.25){5 km} \rput(1.5,3.2){1 km} \rput(1.5,.8){1 km} \end{pspicture}$

Exercice 3

Déterminer l'itinéraire le plus court parcourant le graphe pondéré précédent.

Ce problème fait partie d'une classe de problèmes assez simples en apparence, mais en réalité bien plus complexes:

Exercice 4

Réaliser un graphe avec 2 villes, combien d'itinéraires passant par toutes les villes sont possibles ?
Même questions avec 3 villes, puis 4 villes, 5 villes, 10 villes et 30 villes.
Admettons que le calcul d'un itinéraire nécessite 1 microseconde. Combien de temps prend le calcul de tous les itinéraires pour 2 villes ? pour 3 villes ? pour 10 villes ? pour 30 villes ?

Ce problème est très connu sous le nom de "problème du voyageur de commerce", et est couramment utilisé: problème logistique de livraison postal, itinéraire de bus scolaire, inspection d'installation à domicile, optimisation de trajectoire de machines outils, …

Plus généralement, ce problème adresse l'optimisation de trajet sur une carte, carte dans un sens très général et symbolique: en fait graphe.

Problèmes d'étude de réseaux

un réseau informatique est un ensemble d'ordinateurs connectés entre eux. Bien sûr, tous les ordinateurs ne sont pas directement et physiquement reliés à tous les autres.
Un graphe permet de décrire ces connexions.
Trouver un chemin (une route en terme informatique) reliant deux ordinateurs quelconques et leur permettant d'échanger des données n'est pas une question des plus simples.
un réseau social est un ensemble de personnes en relation entre elles. Cette relation est ici un lien de connaissance: un réseau social se représente sous la forme d'un graphe dont les sommets sont des personnes et les arêtes indiquent celles qui se connaissent. Ce graphe peut-être non-orientée (Facebook) ou au contraire orienté (Twitter: la raltion est "ˆtre abonné au fil d'un autre compte").
Il est difficile d'imaginer le graphe complet indiquant les relations entre quelques 7 milliards de sommets représentant chacun une personne. Stanley Milgram a proposé et réalisé une expérience montrant le concept des "six degrés de séparation", théorie établie initialement par le hongrois Karinthy en 1929, idée qui est restée et est maintenant connue sous le nom de "paradoxe de Milgram" ou encore de "effet du petit monde" (ou "small world effect").
Exercice 5
1. Rechercher, détailler, et expliciter cette expérience et ce concept.
2. Imaginer, comme dans cette expérience, que vous vouliez faire parvenir une note, par une chaîne "main à la main entre connaissances", jusqu'au proviseur du lycée. Quelle chaîne imaginez-vous ?
3. Même question pour faire parvenir cette note au président de la république ?
4. Même question pour faire parvenir cette note à Roger Federer ou à Brad Pitt ?
5. Même question pour faire parvenir cette note à un citoyen américain pris au hasard ?
un réseau de télécommunication, tel un réseau informatique …

Documents et pages du web

Ceux-ci sont liés entre eux (par des liens hypertextes).
On peut représenter le web sous la forme d'un graphe dont chaque page est un sommet, relié ou non aux autres pages/sommets.

Exercice 6

Chercher tous les liens de cette page: liens vers un élément dans la même page, liens vers une page du même site ou encore liens vers une page d'un autre site.
Comment les rechercher simplement et efficacement ?
Détailler de même les liens dans une page sur un autre site.

Éléments techniques et terminologie des graphes

Dans un graphe, deux sommets sont adjacents lorsqu'il existe une arête qui les relie.

Un graphe est dit complet lorsque deux sommets quelconques sont toujours adjacents.
Un sous-graphe est un graphe extrait en ne conservant qu'un certain nombre de sommets et tous les liens du graphe de départ reliant ces sommets.

On parle de graphe partiel lorsqu'on ne conserve pas tous les liens.
Un graphe est connexe (ou simplement connexe) lorsque deux sommets quelconques sont toujours joignables par un chemin; en d'autres termes, il n'a pas de sommet isolé dans un graphe connexe.
Le degré d'un sommet est le nombre d'arêtes auquelles il est relié.
La distance entre deux sommets est la longueur du plus court chemin entre ces deux sommets.
Le diamètre d'un graphe est la plus grande distance entre deux sommets du graphe.
Remarque: si le graphe n'est pas connexe, on peut dire que son diamètre est infini
La matrice d'adjacence d'un graphe est la matrice, ou tableau, dans lequel le chiffre de la ligne i et de la colonne j est 1 si il y a un lien entre les sommets i et j, et 0 sinon.

Exemple:

\[\psset{unit=1cm}
\begin{pspicture}(-.3,-2.3)(6.3,5.3)
\psline(0,0)(4,0)(4,4)(0,4)(0,0)(4,4)
\psline(0,0)(2,-2)
\psline(0,4)(6,5)(4,0)
\pscircle[fillstyle=solid,fillcolor=blue](0,4){.3}
\rput(0,4){\bf\white$s_1$}
\pscircle[fillstyle=solid,fillcolor=blue](4,4){.3}
\rput(4,4){\bf\white$s_2$}
\psarc(4.35,-.35){.5}{170}{105}
\pscircle[fillstyle=solid,fillcolor=blue](4,0){.3}
\rput(4,0){\bf\white$s_4$}
\pscircle[fillstyle=solid,fillcolor=blue](0,0){.3}
\rput(0,0){\bf\white$s_3$}
\pscircle[fillstyle=solid,fillcolor=blue](2,-2){.3}
\rput(2,-2){\bf\white$s_5$}
\pscircle[fillstyle=solid,fillcolor=blue](6,5){.3}
\rput(6,5){\bf\white$s_6$}
\end{pspicture}\]

Ce graphe comporte 6 sommets.
Il n'est pas complet, car par exemple s₁ et s₅ ne sont pas reliés.
La distance entre s₁ et s₅ est 2.
Le degré su sommet s₁ est 3, celui de s₅ est 1, et celui de s₄ est 4.
Le diamètre est 3: la distance entre s₅ et s₆.
La matrice d'adjacence est

$\begin{array}{cc} & \phantom{\begin{array}{*6{c}}s_1 &s_2&s_3&s_4&s_5&s_6\end{array}}\\[.3em] \phantom{\begin{array}{c}s_1\\s_2\\s_3\\s_4\\s_5\\s_6\end{array}} &\lp\begin{array}{*6{p{.9em}}} 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 \enar\right) \enar$ $\begin{array}{cc} & \begin{array}{*6{c}}s_1 &s_2&s_3&s_4&s_5&s_6\enar\\[.3em] \begin{array}{c}s_1\\s_2\\s_3\\s_4\\s_5\\s_6\end{array} &\lp\begin{array}{*6{p{.9em}}} 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 \enar\right) \enar$

Exercice 7

On s'intéresse à un graphe social, c'est à dire au graphe pour lequel les sommets sont des personnes et les liens représentent la relation "être ami".

Exprimer dans une terminologie adaptée le degré d'un sommet.
Exprimer dans une terminologie adaptée les éléments techniques d'un graphe donnés précédemment.
Traduire le concept/paradoxe de Milgram en utilisant la terminologie des graphes.
Comment appeler, avec un vocabulaire usuel, un sous-graphe complet ?

Voir aussi la version plus récente, et numérique, de l'expérience de Milgram: Oubliez les « 6 degrés de séparation », il y en a 4,74 !

Exercice 8

Quels sont les diamètres des graphes suivants ?

\[\psset{linewidth=1.5pt,fillstyle=solid}
\begin{pspicture}(-2.2,-2.7)(3.2,2.2)
\psline(1.5,-2.5)(0,2)\psline(0,2)(-1.5,-2.5)\psline(3,1)(-2,0)\psline(-2,0)(1.5,-2.5)\psline(3,1)(-1.5,-2.5)\pscircle(0,2){.2}\pscircle(-2,0){.2}\pscircle(3,1){.2}\pscircle(-1.5,-2.5){.2}\pscircle(1.5,-2.5){.2}
\end{pspicture}\]

\[\psset{linewidth=1.5pt,fillstyle=solid}
\begin{pspicture}(-2.2,-2.7)(3.2,2.2)
\psline(0,2)(-2,0)(-1.5,-2.5)(1.5,-2.5)(3,1)(0,2)
\pscircle(0,2){.2}
\pscircle(-2,0){.2}
\pscircle(3,1){.2}
\pscircle(-1.5,-2.5){.2}
\pscircle(1.5,-2.5){.2}
\end{pspicture}\]

\[\psset{linewidth=1.5pt,fillstyle=solid}
\begin{pspicture}(-2.2,-2.7)(3.2,2.2)
\psline(0,2)(-1.5,1.5)(-2,0)(-1.5,-2.5)(1.5,-2.5)(2.5,-1)(3,1)(0,2)
\pscircle(0,2){.2}\pscircle(-1.5,1.5){.2}\pscircle(-2,0){.2}\pscircle(-1.8,-1.2){.2}\pscircle(3,1){.2}\pscircle(-1.5,-2.5){.2}\pscircle(2.5,-1){.2}\pscircle(1.5,-2.5){.2}
\end{pspicture}\]

\[\psset{linewidth=1.5pt,fillstyle=solid}
\begin{pspicture}(-.3,-1.8)(4.3,1.8)
\psline(2,-1)(0,0)(2,1)\psline(4,1.5)(2,1)(4,.5)\psline(4,-1.5)(2,-1)(4,-.5)\pscircle(0,0){.2}\pscircle(2,1){.2}\pscircle(2,-1){.2}\pscircle(4,1.5){.2}\pscircle(4,.5){.2}\pscircle(4,-1.5){.2}\pscircle(4,-.5){.2}
\end{pspicture}\]

\[\psset{linewidth=1.5pt,fillstyle=solid}
\begin{pspicture}(-2.3,-3.8)(4.3,3.8)
\psline(0,2)(-2,0)(0,-2)
%
\psline(2,1)(0,2)(2,3)\psline(4,3.5)(2,3)(4,2.5)\psline(4,.5)(2,1)(4,1.5)
\pscircle(0,2){.2}\pscircle(2,3){.2}\pscircle(2,1){.2}\pscircle(4,3.5){.2}\pscircle(4,2.5){.2}\pscircle(4,.5){.2}\pscircle(4,1.5){.2}
%
\psline(2,-1)(0,-2)(2,-3)\psline(4,-3.5)(2,-3)(4,-2.5)\psline(4,-.5)(2,-1)(4,-1.5)\pscircle(0,-2){.2}\pscircle(2,-3){.2}\pscircle(2,-1){.2}\pscircle(4,-3.5){.2}\pscircle(4,-2.5){.2}\pscircle(4,-.5){.2}\pscircle(4,-1.5){.2}
%
\pscircle(-2,0){.2}\end{pspicture}\]

Exercice 9

Pour les deux graphes suivants, donner la matrice d'ajacence et le diamètre du graphe:

\[\psset{unit=1cm}
\begin{pspicture}(-.3,-2.3)(6.3,5.3)
\psline(4,4)(0,4)(0,0)
\psline(0,0)(2,2)(0,4)
%\psarc(-.45,4.25){.5}{0}{300}
\pscircle[fillstyle=solid,fillcolor=blue](0,4){.3}
\rput(0,4){\bf\white$s_1$}
\pscircle[fillstyle=solid,fillcolor=blue](4,4){.3}
\rput(4,4){\bf\white$s_2$}
\psarc(2.35,1.65){.5}{170}{105}
\pscircle[fillstyle=solid,fillcolor=blue](2,2){.3}
\rput(2,2){\bf\white$s_4$}
\pscircle[fillstyle=solid,fillcolor=blue](0,0){.3}
\rput(0,0){\bf\white$s_3$}
\end{pspicture}\]

\[\psset{unit=1cm}
\begin{pspicture}(-.3,-2.3)(6.3,5.3)
\psline(4,4)(0,4)(0,0)
\psline(0,0)(2,-2)(4,4)
\psline(0,0)(2,2)
\psarc(-.45,4.25){.5}{0}{300}
\pscircle[fillstyle=solid,fillcolor=blue](0,4){.3}
\rput(0,4){\bf\white$s_1$}
\pscircle[fillstyle=solid,fillcolor=blue](4,4){.3}
\rput(4,4){\bf\white$s_2$}
\psarc(2.35,1.65){.5}{170}{105}
\pscircle[fillstyle=solid,fillcolor=blue](2,2){.3}
\rput(2,2){\bf\white$s_4$}
\pscircle[fillstyle=solid,fillcolor=blue](0,0){.3}
\rput(0,0){\bf\white$s_3$}
\pscircle[fillstyle=solid,fillcolor=blue](2,-2){.3}
\rput(2,-2){\bf\white$s_5$}
\end{pspicture}\]

Exercice 10

Huit pays sont représentés ci-dessous avec leurs frontières (une frontière est un segment, non réduit à un point, entre deux pays adjacents).

\[\psset{xunit=1.3cm,linewidth=1.5pt,fillstyle=solid}
\begin{pspicture}(-.2,-.2)(6.2,5.2)
\pspolygon(0,0)(6,0)(6,5)(0,5)
\psline(1.5,0)(1.5,5)
\psline(0,1.5)(6,1.5)
\psline(1.5,3.5)(0,3.5)
\psline(1.5,1.5)(3,3.5)(6,3.5)
\pspolygon(4,1.5)(4,2.5)(5,2.5)(5,1.5)
\psline(4.5,2.5)(4.5,3.5)
\rput(.75,.75){7}
\rput(.75,2.5){6}
\rput(.75,4.25){5}
\rput(3.75,.75){1}
\rput(5.5,2.5){2}
\rput(3.25,2.5){3}
\rput(3.25,4.25){4}
\rput(4.5,2){8}
\end{pspicture}\]

Représentez cette carte sous la forme d'un graphe: les huits pays en étant les sommets, et les liens représentant la relation "avoir une frontière commune".
Ce graphe est-il complet ? Connexe ? Quel est le degré de chaque noeud ? le nombre d'arêtes ?
Écrire la matrice d'adjacence de ce graphe.
Quelle est la distance entre les sommets 1 et 5 ? Quel est le diamètre du graphe ?
Colorez les huit pays avec un nombre minimum de couleurs de telle façon que deux pays adjacents portent deux couleurs différentes

Exemples de problèmes étudiés par la théorie des graphes

Robustesse

Quel est l'effet de la modification d'un réseau ? En d'autres termes sa stabilité et/ou sa robustesse.

En temps de guerre (une des grandes sources d'innovation scientifique …), les réseaux de télécommunication constituent ...
Dans un écosystème donné, quel peut être l'effet de la disparition d'une espèce ?
Dans un réseau social, quelle est l'importance d'une personne dans la pérénnité du sous-réseau ?

On vise ici à déterminer les éléments cruciaux, et donc ceux à protéger en priorité.

Une idée simple et naïve est de considérer que plus un sommet à un degré élevé, plus il est important: plus une personne a de connaissance plus … plus une page sur le web a de liens qui pointent vers elle plus elle est pertinente. Ce dernier point est le fondement de l'algorithme de base de Google, nommé PageRank.

Propagation sur un réseau

Dans certains cas, on cherche à étudier la propagation sur un réseau: propagation d'une information (importante ou fake news), d'un virus (informatique ou humain), …
Un objectif peut être alors de chercher à limiter, ou ralentir, la diffusion, ou au contraire d'en augmentant la vitesse et l'étendue comme dans une campagne marketing et publicitaire.

Voir aussi

Plongée au cœur du Web: réseaux et graphes au cœur des algorithmes mathématiques de Google, Amazon, Facebook, &helip;
Promenade aléatoire dans un graphe et principe du référencement de pages web. Activité de programmation en python.
Tout est graphe ! Introduction à une théorie aux applications multiformes
Fouille de graphes et réseaux sociaux
Small world et expérience de Milgram, et théorie des six degrés de séparation ou théorie de Karinthy
Une version plus récente, et numérique, de l'expérience de Milgram sur la théorie de Karinthy: Oubliez les « 6 degrés de séparation », il y en a 4,74 !