Théorie des graphes
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article 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 un espace à trois dimensions, qui a une fonction précise, et qui peut être désigné par une étiquette...) représentant une relation binaire (Une relation binaire est un concept mathématique qui systématise des notions comme « ... est supérieur ou égal à ... » en arithmétique, ou « ... est élément de...), orientée ou non, entre des éléments d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) (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 acceptions :) concerne cette seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une mesure d'angle plan. La...) 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, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent...) des graphes est apparu dans les articles de Leonhard Euler 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 spatiales par des transformations continues (sans arrachages ni recollement des structures).).

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 électriques ou électroniques parcouru par un courant électrique.).

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 valeur l'étendue de cet espace, sa localisation relative par rapport aux espaces voisins, ainsi que la localisation des...) de telle façon que deux pays (Pays vient du latin pagus qui désignait une subdivision territoriale et tribale d'étendue restreinte (de l'ordre de quelques centaines de km²),...) qui présentent une frontière (Une frontière est une ligne imaginaire séparant deux territoires, en particulier deux États souverains. Le rôle que joue une frontière peut fortement varier suivant les...) commune soient de couleur (La couleur est la perception subjective qu'a l'œil d'une ou plusieurs fréquences d'ondes lumineuses, avec une (ou des) amplitude(s) donnée(s).) 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 signifiait race, génération. Il a ensuite indiqué la durée d'une...) 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 français.) 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 division entre les définitions réelles et les définitions...) 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 grammatical ».) total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme....) 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 informations. Par analogie avec un filet (un réseau est un...) routier à grande échelle : chaque ville (Une ville est une unité urbaine (un « établissement humain » pour l'ONU) étendue et fortement peuplée (dont les habitations doivent être à...) est un sommet, chaque route (Le mot « route » dérive du latin (via) rupta, littéralement « voie brisée », c'est-à-dire creusée dans la roche, pour ouvrir le chemin.) 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 l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du...) 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 d'activité économique. Elle met en relation et structure les différents quartiers, s'inscrivant de ce fait dans un réseau de voies...) 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 sociales reliés entre eux par des liens créés lors des interactions sociales. Il se représente par une structure ou une forme...).
  • 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 permettant de passer automatiquement (en pratique grâce à l'informatique) du document consulté à un...) 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 changement dans le monde.), par des sauts. Voir automate (Un automate est un dispositif se comportant de manière automatique, c'est-à-dire sans intervention d'un humain. Ce comportement peut être figé, le système fera toujours la même chose, ou bien peut s'adapter...) 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 (engrenages, poulies, courroies, vilebrequins, arbres de transmission, pistons, ...), bref, de tout ce qui produit ou transmet un...) 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 efficacité naturelle dans l'action. Cette augmentation se traduit par la simplification des actions entreprises, par...) d'aide à la modélisation cinématique (En physique, la cinématique est la discipline de la mécanique qui étudie le mouvement des corps, en faisant abstraction des causes du mouvement (celles-ci sont généralement...) 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 d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par...).

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 données qui repose sur des principes mathématiques inventés par E.F....) 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 (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 explication pour décrire l'action, le comportement, la méthode ou la tâche qui devra...) 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 codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) 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, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) 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 l'univers.) 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 Terre sur un corps massique en raison uniquement du voisinage de la Terre. Elle est égale à l'opposé de la...), un coût, une distance, ...). On parle de fonction de valuation 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é nommés ainsi par Claude Berge en 1960.) : 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 est l'ensemble de tous les couples, dont la première composante appartient à X et la seconde à Y. On généralise facilement...) 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 d'une information.). 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 Brisson (1723-1806) en 1760.) 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 variés comme le courrier électronique, la messagerie instantanée et le World...) 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 produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le...) 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 général au delà de sept mètres. Les arbres acquièrent une structure rigide composée d'un tronc...) 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 elle-même, puisque cette théorie est motivée, à l'origine, par le...) 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 soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie,...) 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 optimiser le bon déroulement d'un projet suffisamment complexe pour...) avec le réseau PERT (Le graphique PERT (PERT : initiales de Program (ou Project) Evaluation and Review Technique, litt. « technique d'évaluation et d'examen de programmes » ou « de projets » et jeu de mots avec l'adjectif anglais...).
  • 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 dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de...) et à la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique...).

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 période entre deux nuits, pendant laquelle les rayons du...), pas complètement (Le complètement ou complètement automatique, ou encore par anglicisme complétion ou autocomplétion, est une fonctionnalité informatique permettant...) é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 hauteur : plus la fréquence est élevée, plus la hauteur perçue est haute et inversement....) 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 terme désigne des échanges de courrier personnels...) 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 à Draguignan (Var).) 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 être employé comme :) d'un graphe.
  • Représentation dynamique (Le mot dynamique est souvent employé désigner ou qualifier ce qui est relatif au mouvement. Il peut être employé comme :) d'un graphe.
Page générée en 0.136 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique