Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain

1.2 Historique

Les premières études sur la théorie des graphes sont celles effectuées par Leonhard Eulervdans avec sa recherche d'une solution au problème des ponts de Königsberg (Euler 1736). La ville de Königsberg située en Prusse est alors constituée de deux iles reliées par sept ponts (cf. figure 1.1). La ville se nomme aujourd'hui Kaliningrad.

1.2.1 Le problème

Le problème posé est de trouver un chemin permettant de passer sur chaque pont en n'empruntant chaque pont qu'une seule fois.

Plan de la ville

Plan simplifié

^île

^île

^Terre

Figure 1.1 : Les sept ponts de Königsberg.

^{rive A}

^{rive A}

^C

^B

^île B

^{rive D}

^Rivière

^ferme

^Pont

Leonhard Euler va dessiner un schéma où rives et îles seront représentées par des

points et chaque pont comme des « fils » entre ces points, créant ainsi un graphe (cf. Figure

1.2).

^{île C}

^{rive D}

1.2.2 La réponse par le graphe

Les points de terre ferme sont les noeuds ou sommets du graphe. Les noeuds et sommets représentent toujours les objets connectés du graphe. Habituellement un noeud (ou un sommet) représente un objet actif du graphe. Dans un réseau social, les noeuds représentent des personnes et par transposition, les connections leurs relations sociales, par exemple.

^{Nb de ponts=3}

^A

^B

^{Nb de ponts=3}

^C

^{Nb de ponts=5}

^D

^{Nb de ponts=3}

Figure 1.2 : Les sept ponts de Königsberg dans une représentation graphique.

1.2. Historique 29

Chapitre 1. État de l'art, notions, définitions et vocabulaire sur les graphes

Une fois la représentation graphique créée, la question : « Peut-on faire un parcours passant par les sept ponts en n'utilisant qu'une seule fois chaque pont ? » se résume à : « Existe-t-il un chemin pour revenir d'un point ferme à un autre, différent de celui pris pour aller ? ». Si nous notons à coté de chaque noeud (point de terre ferme) le nombre de ponts (cf. figure 1.2), il devient évident que ce nombre étant toujours impair, il ne sera pas possible depuis un point de terre ferme visité en « milieu » de promenade de revenir directement au point précédent sans réemprunter un pont déjà utilisé.

Cette caractéristique n'est pas nécessaire pour tous les noeuds. Elle l'est cependant pour au moins deux : celui de départ et celui de fin. Aucun point de terre ferme n'étant accessible par un nombre pair de pont, la réponse est finalement qu'il n'est pas possible d'effectuer la promenade demandée.

La représentation graphique nous permet donc d'affirmer qu'il n'existe pas de solution à ce problème.

Il est par ailleurs intéressant de noter certains enseignements fournis par ce travail fondateur :

? C'est la pondération des éléments de terre ferme par le nombre de ponts qui permet de trouver la réponse au problème.

? Une fois le graphe créé, il n'est plus nécessaire de le parcourir pour connaître les informations nous permettant de répondre à la question posée. La localisation des ponts et des points de terre ferme n'a plus d'importance. Et on pourrait tout à fait répondre à la question sans représenter les fils entre les points de terre ferme.

Comme on peut le voir, une représentation d'un réseau par un graphe permet de répondre à une question donnée. La représentation et les informations à représenter sont à choisir en fonction de la nature du graphe et de la question à résoudre. Dans notre travail nous aurons donc à rechercher une représentation graphique la plus efficace possible, pour répondre à nos questions de regroupement.

Nous nous devons aussi de souligner que cette étude porte sur un réseau d'usage (nos promeneurs utilisent les ponts) et de « terrain » au sens premier du mot.

1.3. Notions et définitions 30

Chapitre 1. État de l'art, notions, définitions et vocabulaire sur les graphes