Théorie des graphes - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.
Un exemple de graphe non orienté avec 6 sommets et 7 arêtes.
Un exemple de graphe non orienté avec 6 sommets et 7 arêtes.

Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :

  • le graphe d'une fonction (à distinguer de sa représentation graphique)
  • un objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans...) représentant une relation binaire (En mathématiques, une relation binaire sur un ensemble E, ou tout simplement relation sur un...), orientée ou non, entre des éléments d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) (dans le cas de relations entre plusieurs éléments, on parle d'hypergraphe).

La théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux...) concerne cette seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui...) acception.

Historiques

Jalons théoriques

Un des premiers résultats importants de la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer,...) des graphes est apparu dans les articles de Leonhard Euler (Leonhard Paul Euler, né le 15 avril 1707 à Bâle et mort le...) avec le problème des sept ponts de Königsberg, publié en 1736. Il est aussi considéré comme un des premiers résultats topologiques en géométrie ; en effet, il ne dépend d'aucune mesure. Ces faits caractérisent la relation profonde qui existe entre la théorie des graphes et la topologie (La topologie est une branche des mathématiques concernant l'étude des déformations...).

En 1835, Gustav Kirchhoff a publié ses lois des circuits pour calculer la tension (La tension est une force d'extension.) et le courant dans un circuit électrique (Un circuit électrique est un ensemble simple ou complexe de conducteurs et de composants...).

En 1852, Francis Guthrie a énoncé le problème des quatre couleurs étudiant la possibilité de colorier, en utilisant uniquement quatre couleurs, n'importe quelle carte géographique (Une carte géographique est une représentation d'un espace géographique. Elle met en...) de telle façon que deux pays (Pays vient du latin pagus qui désignait une subdivision territoriale et tribale d'étendue...) qui présentent une frontière (Une frontière est une ligne imaginaire séparant deux territoires, en particulier deux...) commune soient de couleur (La couleur est la perception subjective qu'a l'œil d'une ou plusieurs fréquences d'ondes...) distincte. Ce problème a été résolu par Kenneth Appel et Wolfgang Haken en 1976, soit un siècle (Un siècle est maintenant une période de cent années. Le mot vient du latin saeculum, i, qui...) après son énonciation ; il peut être considéré comme le point (Graphie) de naissance de la théorie des graphes. De nombreux termes et concepts théoriques fondamentaux de la théorie des graphes ont découlé des tentatives de résolution de ce problème.

Fondements contemporains

Plus récemment (années 1960), Claude Berge (Claude Berge, né le 5 juin 1926 et décédé le 30 juin 2002, était un mathématicien et artiste...) a posé les bases de la théorie moderne des graphes.

La première définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) formelle d'un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) n'est plus usitée à cause de sa lourdeur. À l'origine, Claude Berge définit un graphe par un ensemble de sommets, un ensemble d'arêtes et une fonction d'incidence qui associe deux sommets à chaque arête. Une arête est appelée une boucle si ses deux sommets sont identiques. Une arête est dite multiple s'il existe au moins une autre arête avec les mêmes sommets, sa multiplicité étant le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un...) d'arêtes ayant ces sommets.

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 Comb (2,n) = \frac{n(n-1)}{2}, où n est le nombre de sommets.

Présentation informelle

Un exemple de graphe orienté avec 5 sommets et 6 arcs, dont une boucle (sommet étiqueté 5).
Un exemple de graphe orienté avec 5 sommets et 6 arcs, dont une boucle (sommet étiqueté 5).

Un graphe possède des sommets et des arcs (ou arêtes). Un arc relie deux sommets entre eux : un sommet de départ et un sommet d'arrivée. Sur un dessin, on peut représenter les sommets par des points (ou des cercles) et les arcs par des flèches.

Les graphes peuvent servir à modéliser, entre autres :

  • Un réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des...) routier à grande échelle : chaque ville (Une ville est une unité urbaine (un « établissement humain » pour...) est un sommet, chaque route (Le mot « route » dérive du latin (via) rupta, littéralement « voie...) 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 (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but...) si la route n'est pas à sens unique.
  • Un réseau routier à petite échelle : chaque intersection est un sommet, chaque tronçon de rue (La rue est un espace de circulation dans la ville qui dessert les logements et les lieux...) entre deux intersections est un arc.
  • Un réseau de bus, un réseau ferré, ...
  • Un réseau social (Un réseau social est un ensemble d'entités sociales tel que des individus ou des organisations...).
  • Le web : chaque page est un sommet, chaque lien hypertexte (Un système hypertexte est un système contenant des documents liés entre eux par des hyperliens...) est un arc (de la page qui le contient vers la page pointée).
  • Beaucoup de systèmes discrets : qui passent d'un état à un autre de façon discontinue au cours du temps (Le temps est un concept développé par l'être humain pour appréhender le...), par des sauts. Voir automate (Un automate est un dispositif se comportant de manière automatique, c'est-à-dire sans...) fini et système de transition d'états.
  • En mécanique (Dans le langage courant, la mécanique est le domaine des machines, moteurs, véhicules, organes...) du solide, le graphe des liaisons est un outil (Un outil est un objet finalisé utilisé par un être vivant dans le but d'augmenter son...) d'aide à la modélisation cinématique (En physique, la cinématique est la discipline de la mécanique qui étudie le...) des mécanismes. Les propriétés du graphe ont parfois une signification (nb de cycle, classe etc.).
  • En électronique, il peut servir à déterminer le nombre d'équations indépendantes (loi des mailles) disponibles.

Les graphes sont beaucoup utilisés en informatique (L´informatique - contraction d´information et automatique - est le domaine...).

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 (Le modèle relationnel est une manière de modéliser les informations contenues dans une base de...) 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 (En mathématiques, le résultant est une notion qui s'applique à deux polynômes....) 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 (Flots) 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 (Une instruction est une forme d'information communiquée qui est à la fois une commande et une...) doit s'exécuter après telle autre ; telle donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent...) doit être calculée avant telle autre).

Définitions élémentaires

Il existe différents types de graphes. La définition la plus générale est celle du graphe non orienté donnée (Dans les technologies de l'information, une donnée est une description élémentaire,...) ci-dessous :

Un graphe 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.

Une autre définition, celle du graphe orienté, est couramment utilisée :

Un graphe 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 ci-dessus, 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\}.

D'autres types de graphes existent. On cite notamment :

  • Le multigraphe ou p-graphe : 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}.
  • Le graphe valué : à tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) arc (resp. arête) est associée une valeur (par exemple : un poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la...), un coût, une distance, ...). On parle de fonction de valuation (En mathématiques, plus particulièrement en géométrie algébrique et en...) définie de S\times S dans \mathbb{R}.
  • L' hypergraphe (Les hypergraphes sont des objets mathématiques généralisant la notion de graphes. Ils ont été...) : un (hyper-)arc (resp. arête) peut relier plus de deux sommets entre eux. L'ensemble A des (hyper-)arcs (resp. arêtes) vérifie : A\subseteq \bigcup_i S^i\,Si désigne le produit cartésien (En mathématiques, le produit cartésien de deux ensembles X et Y, appelé...) de i occurrences de S.

En informatique, de nombreuses implémentations de graphes existent. On peut par exemple 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 (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir...). 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.

Exemples de représentation par des graphes

  • Le graphe du web peut être modélisé par un graphe orienté dont les sommets sont des pages web et un arc représente un lien hypertextuel qui pointe d'une page vers une autre.
  • Un réseau routier peut se représenter comme un graphe — non orienté, sauf si on tient compte d'éventuelles voies à sens unique — dont les sommets sont les villes et les arêtes les routes qui mènent directement d'une ville à une autre sans passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques...) par une ville intermédiaire.
  • 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.
  • Le réseau internet (Internet est le réseau informatique mondial qui rend accessibles au public des services...) est un graphe dont les sommets sont les serveurs et les utilisateurs, et les arêtes les différentes interconnexions.

Champ (Un champ correspond à une notion d'espace défini:) d'utilisation

La théorie des graphes étudie les propriétés de ces objets. Parmi les problèmes classiques figurent :

  • Le problème des sept ponts de Königsberg ou la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue...) de cycles eulériens.
  • La connexité : existe-t-il un chemin reliant deux sommets ?
  • L'arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en...) couvrant de poids minimal.
  • Le plus court (respectivement: le plus long) chemin entre deux sommets d'un graphe valué.
  • La coloration de graphe (Le problème de la coloration de graphe est en fait à l'origine de la théorie des graphes...) avec un nombre fixé de couleurs.
  • Les sous-graphes denses maximaux (parfois appelés cliques).
  • Les problèmes de flots maximaux ou minimaux.
  • L'allocation de ressources.
  • Le problème du voyageur de commerce (terme anglais : TSP — travelling salesman problem).
  • Le problème du postier chinois.
  • La décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils...) d'un graphe en niveaux.
  • La gestion de projet (La gestion de projet ou conduite de projet est une démarche visant à structurer, assurer et...) avec le réseau PERT (Le graphique PERT (PERT : initiales de Program (ou Project) Evaluation and Review Technique,...).
  • Les graphes hamiltoniens et hypo-hamiltoniens.

Cette théorie est fortement liée à l'algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées...) et à la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...).

Quelques problèmes algorithmiques importants de la théorie des graphes

  • Coloration (des sommets)
Donnée : un graphe G = (S,A) non orienté et un entier positif k;
Question : existe-t-il une fonction de S dans \{1,\dots,k\} telle que si deux sommets a et b de G sont adjacents alors col(a)\neq col(b) ?
  • Isomorphisme de graphes
Donnée : deux graphes G = (S,A) et G' = (S',A')
Question : Les graphes G et G' sont-ils identiques à un renommage de leurs sommets près? Ou plus formellement, existe-t-il une fonction bijective f : S \rightarrow S' telle que \forall (u,v) \in S^2, (u,v) \in A \Leftrightarrow (f(u),f(v)) \in A'

La complexité théorique de ce problème n'est, à ce jour (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la...), pas complètement (Le complètement ou complètement automatique, ou encore par anglicisme complétion ou...) établie. Il n'a jamais été montré que le problème appartenait à la classe des problèmes NP-complets mais aucun algorithme de résolution de complexité polynomiale n'a été trouvé. En pratique, ce problème est généralement simple. L'algorithme Nauty, basé sur la théorie des groupes, résout très efficacement ce problème. Il existe des algorithmes polynomiaux pour certains graphes particuliers (graphes à connexité bornée, arbres, graphes planaires...).

  • Isomorphisme de sous-graphe partiel (Le mot partiel peut être employé comme :)
Donnée : deux graphes G = (S,A) et G' = (S',A') tels que |S| \le |S'|
Question : Le graphe G est-il "inclus" dans le graphe G' à un renommage de ses sommets près? Ou, plus formellement, existe-t'il une fonction injective f : S \rightarrow S' telle que \forall (u,v) \in S^2, (u,v) \in A \Rightarrow (f(u),f(v)) \in A'

Ce problème est NP-complet dans le cas général. Il existe des algorithmes polynomiaux pour certains graphes particuliers, comme les arbres.

  • Isomorphisme de sous-graphe non partiel
Donnée : deux graphes G = (S,A) et G' = (S',A') tels que |S| \le |S'|
Question : Le graphe G est-il "identique" à un sous-graphe du graphe G' à un renommage de ses sommets près? Ou plus formellement, existe-t'il une fonction injective f : S \rightarrow S' telle que \forall (u,v) \in S^2, (u,v) \in A \Leftrightarrow (f(u),f(v)) \in A'. Ce problème est un cas particulier de l'isomorphisme de sous-graphe (partiel) où la contrainte suivante est ajoutée : un couple de sommets du graphe G ne formant (Dans l'intonation, les changements de fréquence fondamentale sont perçus comme des variations de...) pas un arc ne peut être mis en correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...) par la fonction f qu'avec un couple de sommets du graphe G ne formant pas un arc également.

Ce problème est NP-complet dans le cas général. Il existe des algorithmes polynomiaux pour certains graphes particuliers, comme les arbres.

  • Plus grand sous-graphe commun à deux graphes
Donnée : deux graphes G = (S,A) et G' = (S',A')
Question : Trouver la taille (généralement en terme de nombre de sommets) du plus grand graphe G'' tel que G'' soit un sous-graphe de G = (S,A) et de G' = (S',A').

Ce problème est NP-difficile.

Critiques

Alain Connes (Alain Connes est un mathématicien français, né le 1er avril 1947 à...) considère que les connaissances sur la théorie des graphes ne forment une théorie mais "un savoir, une série de faits"[1].

Types de représentation des graphes

  • Représentation statique (Le mot statique peut désigner ou qualifier ce qui est relatif à l'absence de mouvement. Il peut...) d'un graphe.
  • Représentation dynamique (Le mot dynamique est souvent employé désigner ou qualifier ce qui est relatif au mouvement. Il...) d'un graphe.
Page générée en 0.008 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise