Théorie des graphes

Un article de Wikipédia, l'encyclopédie libre.

Fig. 1: Un graphe non orienté avec 6 sommets et 7 arêtes.
Fig. 1: Un graphe non orienté avec 6 sommets et 7 arêtes.
Fig. 2: Un graphe orienté avec 5 sommets et 6 arcs dont une boucle.
Fig. 2: Un graphe orienté avec 5 sommets et 6 arcs dont une boucle.

Le terme de graphe possède deux acceptions en mathématiques :

  • le graphe d'une fonction, et
  • l'objet de mathématique combinatoire que nous décrivons ici, généralisant le concept de relation binaire et celui de polyèdre, et utile pour la modélisation de divers problèmes du "monde réel" (c'est-à-dire que l'on rencontre en dehors des mathématiques, comme par exemple ceux liés à la notion de réseau qu'il soit informatique, social, routier ou autre…).


Sommaire

[modifier] Définition formelle

On fait généralement remonter la théorie des graphes aux années 60, depuis les bases posées par Claude Berge dans Graphes et hypergraphes, même si le concept est nettement plus ancien. Berge a essentiellement réuni au sein de cette théorie des résultats de combinatoire, déjà connus, et motivé l'étude des graphes par des applications, des liens avec la théorie des jeux et par l'existence de conjectures (dans Pour l'honneur de l'esprit humain, Jean Dieudonné dit qu'une branche des mathématiques est vivace si elle pose beaucoup de questions…).

[modifier] Graphes

De nos jours on donne une définition intuitive des graphes (donnée plus bas) qui diffère en apparence de la définition donnée par Berge, mais en fait bien sûr elles sont équivalentes : Berge définit un graphe comme un triplet (V,E,φ) où φ est une fonction \phi:E\rightarrow V\times V.

Le vocabulaire de la théorie des graphes est ensuite emprunté à la géométrie des polyèdres. Un cas particulier de graphe est un triplet (V,E,φ) où V est l'ensemble des sommets d'un polyèdre, E celui des arêtes du polyèdre et où φ(e) = (u,v) si l'arête e relie les deux sommets u et v. Ce vocabulaire est conservé et d'une manière générale on dit pour tout graphe que V est son ensemble de sommets, E celui de ses arêtes (ou des arcs si le graphe est orienté) et φ est sa fonction d'incidence (qui à chaque arête (arc) associe un couple de sommets). Aussi on dira, quand φ(e) = (u,v), que e et u sont incidents (idem pour e et v), que u et v sont adjacents et que ces deux sommets sont les extrémités de e. De deux arêtes on dit qu'elles sont adjacentes si elles sont incidentes à un même sommet. De nos jours, l'habitude est prise d'écrire explicitement qu'une arête est incidente à un sommet, donc de n'utiliser aucune notation pour la fonction d'incidence et en fait de supposer son existence. On écrit ainsi : soit G = (V,E) un graphe... Cette notation n'est en fait strictement rigoureuse que pour les graphes simples.

Si le graphe est orienté, u est l'extrémité initiale de e et v est son extrémité terminale (dans le cas non orienté ces sommets sont des extrémités tout simplement, sans autre précision). Dans les graphes orientés, deux arêtes sont consécutives si elles sont adjacentes et si leur extrémité commune est initiale pour une arête et terminale pour l'autre.

Une arête (arc) est appelée une boucle si ses deux extrémités sont identiques. Deux arêtes (arcs) sont parallèles si elles ont les mêmes extrémités (même extrémité initiale et même extrémité terminale pour les arcs). La multiplicité d'une arête (arc) est 1 si elle n'est parallèle avec aucune autre et sinon, on dit qu'elle est multiple et sa multiplicité est le nombre total (y compris elle même) de ses arêtes parallèles. Le concept de graphe orienté sans arc multiple correspond précisément à celui de relation binaire tandis que le concept de graphe non-orienté sans arête multiple correspond à celui de relation binaire symétrique.

Un graphe est dit simple s'il n'a ni boucle ni arête multiple. Le nombre maximum d'arêtes d'un graphe simple est donc n(n − 1) / 2 s'il est non-orienté et n(n − 1) s'il est orienté, où n est le nombre de sommets (voir graphe complet). Ces graphes correspondent aux relations binaires non-réflexives. Les graphes simples orientés sans paire d'arcs de la forme (u,v) et (v,u) correspondent aux relations binaires non-réflexives et antisymétriques.

[modifier] Hypergraphes

Le concept de graphe non-orienté se généralise par celui d'hypergraphe mais le concept de connexité (existence de chemin) s'exporte mal des graphes aux hypergraphes et encore moins aux hypergraphes orientés dont aucune des diverses définitions possibles ne s'est encore imposée.

[modifier] Un peu d’histoire

Le résultat connu, sans doute le plus ancien, que l'on peut inclure dans la théorie des graphes est la caractérisation des graphes Eulériens, motivée par le problème des sept ponts de Königsberg, par Euler en 1736.

En 1835, Gustav Kirchhoff a publié ses lois des circuits pour calculer la tension et le courant dans un circuit électrique. Ceci allait être dans les années 50 à l'origine des concepts de flot et de coupe dans les graphes. Ces deux concepts réunis ont permis de poser les bases de la dualité en programmation linéaire et de l'existence des théorèmes min-max en optimisation combinatoire, donnant un nouvel éclairage à d'anciens résultats (comme les théorèmes de Menger et König).

C'est en 1852 que Francis Guthrie a posé le fameux problème des quatre couleurs, problème résolu plus d'un siècle après son énonciation. Ce résultat majeur à donné ses "lettres de noblesse" à la théorie des graphes. Le vocabulaire même de la théorie des graphes provient du contexte de la résolution de ce problème qui s'intéresse uniquement aux graphes issus des polyèdres.

En 1914, "tout graphe biparti régulier a un couplage parfait" annoncé par König (publié en 1916).

En 1927, Théorème de Menger premier résultat de connectivité en graphe et, a posteriori, premier théorème min-max.

En 1931, Théorème de König.

En 1935, Théorème de Hall (généralisé par Tutte, puis Tutte-Berge) sur les couplages parfaits dans les graphes bipartis. Ce résultat allait être à l'origine de la classe co-NP, puis associé à l'algorithme du couplage parfait d'Edmonds, à l'origine de la conjecture \textrm{P} = \textrm{NP}\cap \textrm{co-NP} en Théorie de la complexité.

L'année 1956 est une "double-date", c'est celle du théorème flot-max/coupe-min généralisant les théorèmes de Menger, de König et de Hall, et à l'origine de la programmation linéaire. De plus, c'est l'année de l'algorithme de Kruskal, premier algorithme glouton en graphe. Ce résultat est à l'origine d'une véritable renaissance pour la théorie des matroïdes qui va être étroitement reliée à la théorie des graphes par Tutte.

En 1960, conjecture de Berge.

En 1976, Théorème des quatre couleurs (résolution du problème posé par Guthrie).

En 2002, Théorème des graphes parfaits (résolution de la conjecture de Berge).

La seconde moitié du XXe siècle, aura vu la théorie des graphes interagir avec de nombreux autres domaines. Au sortir de la guerre, les problèmes de flots dans les graphes ont été à l'origine de la programmation linéaire et de l'algorithme du simplexe. Les problèmes d'arbres couvrants allaient être à l'origine de la généralisation du concept de graphe par celui de matroïde et des parallèles entre les deux théories, en particulier au niveau algorithmique (ce qui influencera le vocabulaire des deux théories). Les problèmes de couplage allaient être à l'origine à la fois de la Théorie de la complexité (incluant les algorithmes d'approximation) et de l'approche polyèdrale. Pour analyser l'efficacité de son algorithme de couplage, Jack Edmonds a défini le concept d'algorithme polynomial, poussant ainsi Cook à montrer l'existence du premier problème NP-complet. La facilité du problème de couplage contrastait avec la difficulté du transversal mais l'optimum difficile à obtenir est toujours borné par l'optimum facile multiplié par 2, ainsi l'algorithme de couplage max est le premier algorithme approché. Edmonds a ensuite montré que l'enveloppe convexe des couplages de tout graphe peut être décrit par un certain type d'inégalités linéaires, c'est le premier résultat polyèdral. Cette approche allait connaitre un grand succès lorsque son efficacité en pratique allait être révélée par les travaux sur le voyageur de commerce (qui est par-ailleurs le premier problème non-approximable), et son efficacité théorique par le théorème Optimisation/Séparation et les caractérisations polyèdrales des graphes bipartis et des graphes parfaits.

[modifier] Présentation informelle

Tout graphe orienté peut se représenter par un dessin, comme l'illustre la figure 2. C'est d'ailleurs de cette représentation que le terme "arc" est issu (même si "flèche" semblerait plus approprié). Sur un dessin, on peut représenter les sommets par des points (ou des cercles) et les arcs par des flèches : un arc relie un sommet vers un autre. Pour les graphes non-orientés, on remplace les flèches par des traits comme dans la figure 1.

[modifier] Définition intuitive

La façon intuitive (avec un formalisme moins lourd que celui des années 60) de présenter les graphes simples orientés est la suivante :

Un graphe simple orienté G est un couple (S, A), où :
  • S est un ensemble dont les éléments sont les sommets ;
  • A est un ensemble de couples (ordonnés) de sommets, appelés arcs.

Pour le graphe de la figure 2 représenté plus haut, on aurait S = \left\{ 1, 2, 3, 4, 5 \right\} et A = \left\{ (1,2), (2,3), (3,1), (2,5), (4,5), (5,5) \right\}.

De la même manière on peut définir les graphes simples non-orientés :

Un graphe simple non-orienté G est un couple (S, A), où :
  • S est un ensemble dont les éléments sont les sommets ;
  • A est un ensemble de paires (non ordonnées) de sommets, appelées arêtes.

Pour les graphes plus généraux (pas forcément simples) on peut s'en sortir en parlant de collection (ou de famille) de paires (ou de couples pour le cas orienté) à la place d'ensemble.

D'autres types de graphes existent :

  • On parle de multigraphe ou p-graphe quand au plus p arcs (resp. arêtes) peuvent relier deux sommets. On peut le définir par une application de S\times S dans \mathbb{N}.
  • Un graphe est valué si à tout arc (resp. arête) est associée une valeur (par exemple : un poids, un coût, une distance, ...). On parle de fonction de valuation définie de S\times S dans \mathbb{R}.

[modifier] Représentations informatiques des graphes

On peut stocker un graphe à l'aide de différentes structures. On peut numéroter les sommets, puis donner les arcs sous la forme d'une liste de couples. On peut aussi utiliser une matrice d'adjacence, plus rapide mais exigeant plus d'espace mémoire. Enfin, on peut associer à chaque sommet une liste d'adjacence, c'est-à-dire une liste contenant tous les sommets vers lesquels pointent les arêtes partant de ce sommet.

Voir aussi :

[modifier] Intérêt dans le "monde réel"

Les graphes servent à modéliser, entre autres :

  • Un réseau routier à grande échelle : chaque ville est un sommet, chaque route entre deux villes est un arc (si elle ne passe pas par une autre ville), et même en général deux arcs : un dans chaque sens si la route n'est pas à sens unique.
  • Un réseau routier à petite échelle : chaque intersection est un sommet, chaque tronçon de rue entre deux intersections est un arc.
  • Un réseau de bus, un réseau ferré…
  • En analyse des réseaux sociaux les graphes permettent d'observer et décrire les aspects formels des réseaux sociaux pour en faire par la suite l'analyse sociologique[1].
  • Le web : chaque page est un sommet, chaque lien hypertexte est un arc (de la page qui le contient vers la page pointée).
  • Le réseau internet est un graphe dont les sommets sont les serveurs et les utilisateurs, et les arêtes les différentes interconnexions.
  • Beaucoup de systèmes discrets : qui passent d'un état à un autre de façon discontinue au cours du temps, par des sauts. Voir automate fini et système de transition d'états.
  • En mécanique du solide, le graphe des liaisons est un outil d'aide à la modélisation cinématique des mécanismes. Les propriétés du graphe ont parfois une signification (nombre de cycle, classe, etc.).
  • En électronique, ils représentent les circuits intégrés.
  • Un réseau de neurones formels peut se représenter par un graphe orienté, valué — chaque arc porte une valeur — et dont chaque sommet est valué aussi de son seuil d'activation.

Les graphes sont beaucoup utilisés en informatique. Outre leur efficacité dans la modélisation programmatique de structure de données complexes, on les rencontre par exemple pour :

  • les bases de données : un modèle relationnel de données est représentable par un graphe orienté regroupant des relations (sommets du graphe) et des dépendances (arcs du graphe). On parle notamment de graphe sémantique normalisé pour désigner un schéma de données relationnel résultant du processus de normalisation ;
  • le Web sémantique : une ontologie se décrit comme un ensemble de concepts (sommets du graphe orienté) et de relations (arcs du graphe) ;
  • le parallélisme : les techniques d'optimisation d'algorithme ou de détermination d'ordre d'exécution cohérente dans ce domaine prennent souvent en entrée des graphes de dépendance de flot d'instructions ou de données, où les sommets sont respectivement des instructions (de code à exécuter) et des données (initiales ou calculées) et les arcs des relations de dépendance temporelle (telle instruction doit s'exécuter après telle autre ; telle donnée doit être calculée avant telle autre).

[modifier] Critiques

Alain Connes considère que les connaissances sur la théorie des graphes ne forment pas une théorie mais "un savoir, une série de faits"[2]. Il est en fait assez largement accepté que la théorie des graphes est une théorie "horizontale" plutôt que "verticale", dans le sens où elle se disperse autour de thèmes apparemment sans lien (comme la connexité et la coloration) au lieu d'échafauder une pyramide de résultats fortement dépendants.


[modifier] Algorithmique et théorie des graphes

La théorie des graphes contient de nombreux objets (chemins, arbres, couplages, cliques, colorations…) dont on peut donner une représentation simple (par le dessin). Du point de vue algorithmique, les problèmes (généralement d'optimisation) liés à ces objets peuvent être très difficiles (de par la nature "explosive" ou "exponentielle" des objets combinatoires) ou être de la plus grande simplicité (lorsque les objets ont de très fortes propriétés). Ainsi le problème de l'arbre couvrant est des plus simples (la simplicité de cette structure est captée par le concept plus général de matroïde) tandis que le problème de la coloration fait partie des plus durs à résoudre. C'est dans ce contexte, même si ses fondements appartiennent sans conteste à la logique, que la théorie de la complexité s'est développée, jusqu'à s'appliquer de nos jours à bien des domaines.

Parmi les problèmes classiques dont on connait la complexité algorithmique citons:

Il existe bien sûr des problèmes dont la difficulté (complexité théorique) n'est pas encore établie, c'est le cas du problème fondamental de l'isomorphisme de graphe. On dit de deux graphes G = (S,A) et G' = (S',A') qu'ils sont isomorphes si

il existe une bijection f : S \leftrightarrow S' telle que tout couple de sommets (u,v) \in S^2 on ait (u,v) \in A si et seulement si (f(u),f(v))\in A' ; c'est-à-dire que si l'on renomme bien les sommets de G', on obtient alors G' = G.

Ironiquement on ne sait pas (on ne connait pas de bon algorithme pour) reconnaitre deux graphes identiques, pire on ne sait pas si ce problème est facile ou difficile !

  • Isomorphisme de graphes : difficulté inconnue (aucun algorithme polynomial connu et aucune réduction polynomiale connue d'un problème NP-complet à ce problème)

[modifier] Voir aussi

[modifier] Liens internes

[modifier] Logiciels

  • Graphviz : suite logicielle de manipulation et visualisation de graphes
  • Pajek logiciel permettant de visualiser de larges réseaux

[modifier] Liens externes

[modifier] Notes et références

  1. ↑ Inspiré de Alain Degenne, Michel Forsé (1994): Les réseaux sociaux pp. 75
  2. ↑ Alain Connes, Triangle de pensées, Editions Odile Jacob, p. 132.