Théorie des graphes

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

Vous avez de nouveaux messages (diff^?).

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 représentant une relation binaire, orientée ou non, entre des éléments d'un ensemble.

La théorie des graphes concerne cette seconde acception.

Sommaire

1 Repères historiques
- 1.1 Jalons théoriques
- 1.2 Fondements contemporains
2 Présentation informelle
3 Définitions élémentaires
4 Exemples de représentation par des graphes
5 Champ d'utilisation
6 Quelques problèmes algorithmiques importants de la théorie des graphes
7 Types de représentation des graphes
8 Liens internes
- 8.1 Logiciels
9 Liens externes

[modifier] Repères historiques

[modifier] Jalons théoriques

Un des premiers résultats de la théorie 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.

En 1835, Gustav Kirchhoff a publié ses lois des circuits pour calculer la tension et le courant dans un circuit é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 de telle façon que deux pays qui présentent une frontière commune soient de couleur distincte. Ce problème a été résolu par Kenneth Appel et Wolfgang Haken en 1976, soit un siècle après son énonciation ; il peut être considéré comme le point 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.

[modifier] Fondements contemporains

Plus récemment (années 1960), Claude Berge a posé les bases de la théorie moderne des graphes.

La première définition formelle d'un graphe 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 total 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.

[modifier] Présentation informelle

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 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é, ...
Un réseau social.
Le web : chaque page est un sommet, chaque lien hypertexte 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, 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 (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.

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] 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 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 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}$ .
L' hypergraphe : 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\,$ où $S i$ désigne le produit cartésien 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. 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.

[modifier] 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 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 est un graphe dont les sommets sont les serveurs et les utilisateurs, et les arêtes les différentes interconnexions.

Graphes complets à 1, 2, 3, 4 et 5 sommets.

[modifier] Champ 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 de cycles eulériens.
La connexité : existe-t-il un chemin reliant deux sommets ?
L'arbre couvrant de poids minimal.
Le plus court (respectivement : le plus long) chemin entre deux sommets d'un graphe valué.
La coloration de graphe 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 d'un graphe en niveaux.
La gestion de projet avec le réseau PERT.
Les graphes hamiltoniens et hypo-hamiltoniens.

Cette théorie est fortement liée à l'algorithmique et à la complexité.

[modifier] 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

b

G

sont adjacents alors $col(a)\neq col(b)$ ?

Isomorphisme de graphes

Donnée : deux graphes

G = (S, A)

G' = (S', A')

Question : Les graphes

G

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, pas complètement é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

Donnée : deux graphes

G = (S, A)

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)

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 pas un arc ne peut être mis en correspondance 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)

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.

[modifier] Types de représentation des graphes

[modifier] Liens internes

Lexique de la théorie des graphes.
Liste des algorithmes de la théorie des graphes.
Automate.
Graphe d'Hoffman-Singleton.
Programmation dynamique.
RDF : modèle de graphe pour décrire les (méta-)données.

[modifier] Logiciels

Graphviz : suite logicielle de manipulation et visualisation de graphes.

[modifier] Liens externes

Théorie des Graphes Cours de théorie des graphes
Théorie des Graphes Un autre cours
Diestel Un cours gratuit (pdf) assez poussé et en anglais.

Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques.

Récupérée de « http://fr.wikipedia.org../../../t/h/%C3%A9/Th%C3%A9orie_des_graphes.html »

Catégorie : Théorie des graphes

Théorie des graphes

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

Sommaire

[modifier] Repères historiques

[modifier] Jalons théoriques

[modifier] Fondements contemporains

[modifier] Présentation informelle

[modifier] Définitions élémentaires

[modifier] Exemples de représentation par des graphes

[modifier] Champ d'utilisation

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

[modifier] Types de représentation des graphes

[modifier] Liens internes

[modifier] Logiciels

[modifier] Liens externes

Views

Navigation

Contribuer

Recherche

Autres langues