Théorie des graphes

Un article de Freepedia.

Image:6n-graf.png

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

Définition formelle

On peut distinguer deux types de graphes : les graphes orientés et les graphes non orientés. Dans les deux cas, un graphe <math>G</math> est un couple de deux ensembles <math>(S,A)</math> où <math>S</math>, a priori non vide, est appelé ensemble des sommets de <math>G</math> :

  • si G est un graphe orienté alors A est une partie de <math>S \times S</math> (produit cartésien d'ensembles). L'ensemble <math>A</math> est appelé l'ensemble des arcs de <math>G</math>.
  • si G est un graphe non orienté alors A est un ensemble de parties à 1 ou 2 éléments de l'ensemble <math>S</math>. L'ensemble <math>A</math> est appelé l'ensemble des arêtes de <math>G</math>. Un graphe non orienté est un hypergraphe dont toutes les arêtes contiennent 1 ou 2 sommets.

Deux sommets <math>a</math> et <math>b</math> d'un graphe orienté (resp. non orienté) <math>G=(S,A)</math> sont dits reliés s'il existe un arc <math>(a,b)</math> ou <math>(b,a)</math> (resp. une arête <math>\{ a,b\} </math>) dans <math>A</math>.

Il faut remarquer qu'ainsi défini, un graphe ne peut posséder deux sommets reliés par plusieurs arcs ou arêtes. On parlerait dans ce cas de multigraphe dont la définition formelle doit être différente.

Dans un graphe orienté (respectivement non orienté) une boucle est un arc <math>(a,b)</math> avec <math>a=b</math> (resp. une arête à un seul sommet). Un graphe sans boucle est un graphe simple.

Les auteurs utilisent souvent les lettres <math>S</math> (comme «Sommet»), V (comme «Vertex») et <math>X</math> pour désigner l'ensemble des sommets d'un graphe et les lettres <math>E</math> (comme «Edge») et <math>A</math> (comme «Arcs, Arêtes») pour l'ensemble de ses arcs ou de ses arêtes. La notation fonctionnelle est aussi rencontrée : étant donné un graphe <math>G</math>, <math>S(G)</math>, <math>V(G)</math> et <math>X(G)</math> désignent l'ensemble des sommets de <math>G</math> tandis que <math>E(G)</math> et <math>A(G)</math> désignent l'ensemble de ses arcs ou arêtes.

Étant donné un graphe orienté, il est parfois commode de considérer son graphe non orienté associé qui est le graphe possédant les mêmes sommets mais où chaque arc <math>(a,b)</math> a été remplacé par l'arête <math>\{ a,b\} </math>.

Graphiquement, une relation entre deux sommets d'un graphe orienté peut se représenter à l'aide d'une flèche entre ceux-ci. Dans le cas d'un graphe non orienté, un trait peut symboliser cette relation.

Exemples de représentation par des graphes

  • le graphe du web peut être modélisé par un graphe <math>(V,E)</math> de la manière suivante:
les sommets sont des pages web
étant données 2 pages web <math>a</math> et <math>b</math>, il existe un arc <math>(a,b)</math> dans <math>E</math> si et seulement s'il existe un lien hypertexte dans la page <math>a</math> qui pointe vers la page <math>b</math>.
  • Un réseau routier peut se représenter comme un graphe (non orienté, sauf si l'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.

Champ d'utilisation

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

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

Définitions

Adjacence et Voisinage

Deux sommets sont dits adjacents lorsqu'ils sont reliés par un arc (ou une arête). On dit aussi que ces sommets sont voisins. Le voisinage d'un sommet dans un graphe est l'ensemble de ses voisins.

Arbre recouvrant de poids minimum

Soit <math>G</math> un graphe non orienté et une fonction de poids <math>p</math> qui à toute arête de <math>G</math> associe un nombre réel et à tout sous-graphe <math>G'</math> de <math>G</math> associe la somme des poids des arêtes de <math>G'</math>.
Un arbre recouvrant de poids minimum est un arbre <math>A</math> recouvrant <math>G</math> tel que pour tout arbre <math>A'</math>, si <math>A'</math> recouvre <math>G</math> alors <math>p(A')\leq p(A)</math>.

Carré d'un graphe

Le carré d'un graphe est le graphe qui a les mêmes sommets et dont deux sommets sont reliés s’ils sont reliés dans le graphe d'origine ou s’ils ont un voisin en commun dans le graphe d'origine.

Chaînes et Chemins dans un graphe

Étant donné un graphe <math>G</math> non orienté (resp. orienté), une chaîne dans <math>G</math> est un sous-graphe de <math>G</math> qui appartient à la classe des chaînes (resp. chemins).

Parcours et parcours fermé

Un parcours de sommets (resp. d'arêtes, d'arcs) dans un graphe <math>G</math> est une liste ordonnée de sommets (resp. d'arêtes, d'arcs) de <math>G</math> telle que 2 sommets (resp. arêtes, arcs) consécutifs dans la liste sont adjacents (resp. incident) dans le graphe. Un parcours est fermé si le premier élément de la liste est aussi le dernier.
On parle souvent de parcours sans en préciser le type. Le contexte détermine en général duquel il s'agit, le plus souvent étant sans doute le parcours de sommet.

Parcours eulérien

Un parcours eulérien d'un graphe <math>G</math> non orienté est un parcours <math>(e_1,e_2,...e_m)</math> des <math>m</math> arêtes de <math>G</math> tel que chaque arête de <math>G</math> apparaît exactement une fois dans le parcours.
Un graphe non orienté connexe possède un parcours eulérien si et seulement si tous ses sommets sont de degré pair à l'exception d'au plus 2 d'entre eux.

Chaîne hamiltonienne

Soit <math>G</math> un graphe non orienté et <math>C</math> un sous-graphe de <math>G</math>: <math>C</math> est une chaîne hamiltonienne de <math>G</math> si et seulement si <math>C</math> est une chaîne du même ordre que <math>G</math>.

Cycles et circuits

Un cycle (resp. circuits) dans un graphe <math>G</math> est un sous-graphe de <math>G</math> qui appartient à la classe des cycles (resp. circuits).

Cycle eulérien

Un cycle eulérien est une chaîne eulérienne dont les extrémités sont confondues.
Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

Cycle hamiltonien

Soient <math>G</math> un graphe et <math>C</math> un sous-graphe de <math>G</math>: <math>C</math> est un cycle hamiltonien de <math>G</math> si <math>C</math> est un cycle du même ordre que <math>G</math>.

Degré

Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes auxquelles ce sommet appartient. La somme des degrés de chaque sommet est égale au double du nombre total d'arêtes.
Dans un graphe orienté, on distingue pour un sommet <math>v</math> le degré entrant et le degré sortant. Le premier correspond au nombre d'arcs dont l'extrémité finale est <math>v</math>. Le second est le nombre d'arcs dont l'extrémité initiale est <math>v</math>. Le degré d'un sommet <math>v</math> dans un graphe orienté est la somme du degré entrant et sortant de <math>v</math>.
Le degré maximum (resp. minimum) d'un graphe <math>G</math>, noté <math>\Delta (G)\,</math> (resp. <math>\delta (G)\,</math>) est égal au degré maximum dans l'ensemble des degrés de tous les sommets de <math>G</math>.

Puits

Un Puits est un sommet d'un graphe orienté dont le degré sortant est égal à 0.

Source

Une Source est un sommet d'un graphe orienté dont le degré entrant est égal à 0.


Ensemble dominant

Un ensemble dominant est un sous-ensemble de sommets du graphe tels que chaque sommet du graphe est soit dans l'ensemble dominant, soit est voisin d'un sommet de l'ensemble dominant

Graphe acyclique

Un graphe acyclique est un graphe non orienté qui ne contient aucun cycle.
Si le graphe est orienté on considère le graphe non-orienté associé.

Graphe inverse

Le graphe inverse d'un graphe est un graphe qui a les mêmes sommets, reliés si et seulement s’ils ne sont pas reliés dans le graphe d'origine.

Partition

Une partition des sommets d'un graphe est une famille disjointe d'ensembles de sommets telle que leur union est l'ensemble de tous les sommets.

Sous graphe

Soit <math>G=(X,E)</math> un graphe. Un sous-graphe de <math>G</math> est un graphe <math>G'=(X',E')</math> tel que:
  • <math>X' \subseteq X</math>
  • <math>E' \subseteq E</math>
Si <math>X' = X</math>, G' est un sous-graphe couvrant.
Si <math>E'=E\cap \big\{ \{ a,b\} | a,b \in X' \big\}</math> (ou si <math>E'=E\cap (X'\cap X')</math> si <math>G</math> est orienté) alors <math>G'</math> est un sous-graphe induit.

Arbre couvrant

Un arbre couvrant d'un graphe <math>G</math> non orienté est un graphe <math>A</math> tel que
  • <math>A</math> couvre <math>G</math>;
  • <math>A</math> est un arbre.
Tout graphe connexe admet un arbre couvrant.

Sous-graphe complet ou clique

Une clique dans un graphe <math>G</math> est un sous-graphe de <math>G</math> qui est complet. Une p-clique est une clique de p sommets.

Image:6n-graf-clique.png

Cette notion est utile pour constituer des groupes en classification automatique.


Stable

Un stable est un graphe sans arête. Un stable dans un graphe <math>G</math> est un sous-graphe induit de <math>G</math> qui est sans arête.
Dans le graphe de la figure de droite, les sommets 2 et 4 forment un stable, maximal au sens de l'inclusion (si nous ajoutons un seul sommet du graphe à ce stable, le sous-graphe induit obtenu n'est plus un stable). Mais ce stable n'est pas le plus grand en nombre de sommets puisque les sommets 6, 5 et 3 forment aussi un stable qui est, lui, maximum, au sens de la taille. En effet, il n'existe pas de stable dans ce graphe qui comporte plus de sommets. On parle aussi d'ensemble stable et on définit des problèmes comme celui de l'Ensemble stable de poids maximal ou de cardinal maximal, qui en est un cas particulier, dans un graphe.

Valuation d'un graphe

Une valuation d'un graphe est une fonction qui, à chaque arête, associe un poids (nombre réel).
Exemples : Une valuation possible d'un réseau routier est la longueur de la route. Une autre, le montant du péage à acquitter entre deux points, ou celle de toute autre ressource pour aller d'une ville à l'autre (consommation de carburant, coût, temps, etc.).

Classes de graphes

Arbres

On nomme arbre un graphe connexe non orienté et acyclique (sa forme évoque en effet la ramification des branches d'un arbre). On distingue deux types de sommets dans un arbre
  • les feuilles dont le degré est 1 ;
  • les nœuds internes dont le degré est supérieur à 1.
D'autres définitions équivalentes sont possibles. Par exemple:
  • basée sur le nombre d'arêtes: Un arbre est un graphe connexe non orienté possédant <math>n-1</math> arêtes.
  • inductive: Un sommet est un arbre, si <math>A</math> est un arbre alors <math>(V(A)\cup v,\{ v,a \})</math> (où <math>v</math> est un élément quelconque n'appartenant pas à <math>V(A)</math> et <math>a</math> un sommet de <math>V(A)</math>) est un arbre. Aucun autre graphe n'est un arbre.
Image:Puu graafiteoria.png


Arborescences

Une arborescence est un graphe orienté acyclique connexe où chaque sommet est de degré entrant au plus 1. Dans ce cas un seul sommet est de degré entrant 0, il est appelé racine de l'arborescence.

Chaînes

Les chaînes sont des arbres possédant 2 feuilles. On peut aussi considérer dans certains cas particuliers que les graphes d'ordre 1 sont aussi des chaînes.
D'autres définitions équivalentes sont possibles. Par exemples:
  • basée sur le degré : graphe non orienté connexe de degré maximum inférieur ou égal à 2 et de degré minimum 1.
  • inductive: un sommet est une chaîne, si <math>C</math> est une chaîne alors <math>(V(C)\cup v,\{ v,a \})</math> (où <math>v</math> est un élément quelconque n'appartenant pas à <math>V(C)</math> et <math>a</math> un sommet de degré 1 de <math>V(C)</math>) est une chaîne. Aucun autre graphe n'est une chaîne.

Chemins

Graphe orienté connexe de degré entrant maximum 1, de degré sortant maximum 1 et de degré minimum 1.

Cycles et circuits

Un graphe <math>G</math> non orienté (resp. orienté) et connexe est un cycle (resp. circuits) si et seulement si tous les sommets sont de degré 2 (resp. de degré entrant 1 et de degré sortant 1).

Forêt

Une forêt est un graphe acyclique. Chacune de ses composantes connexes est donc un arbre.

Graphe biparti

Un graphe est biparti s’il y a une partition des sommets du graphe en deux sous ensembles A et B telle que toutes les arêtes du graphe ont un sommet dans A et un sommet dans B.

Graphe complet

Un graphe complet est un graphe dont tous les sommets sont reliés deux à deux. Le graphe complet à n sommets est noté: <math>K_{n}</math>.
voir l'article Graphe complet.

Graphe connexe

Un graphe non orienté est connexe, si et seulement si pour toute paire de sommets [a,b] il existe une chaîne entre les sommets a et b.
Si on parle de connexité pour un graphe orienté, c'est que l'on considère non pas ce graphe, mais le graphe non-orienté correspondant.

Graphe k-connexe

Un graphe non orienté est k-connexe s'il reste connexe après suppression d'un ensemble quelconque de k-1 arêtes et s'il existe un ensemble de k arêtes qui déconnecte le graphe. Autrement dit, un graphe est k-connexe si et seulement s’il existe au moins k chaînes indépendantes (arcs-disjointes) entre chaque couple de sommets. Cette notion est utilisée en électronique, en calcul de la fiabilité, et dans l'étude de jeux de stratégie comme le cut and connect.

Graphe fortement connexe

Un graphe orienté est dit fortement connexe, si pour tout couple de sommets (u,v) du graphe il existe un chemin de u à v et de v à u. Les travaux de Pitts et McCullough suggèrent que le cerveau des mammifères est fortement connexe.

Graphe hamiltonien

Graphe qui contient un cycle hamiltonien. Le graphe est nommé hypohamiltonien s'il suffit d'en retirer un sommet quelconque pour qu'il devienne hamiltonien. Utile dans le problème du voyageur de commerce.

Graphe d'intervalles

Si I est un ensemble d'intervalles sur les réels et qu'on peut associer à chaque sommet un intervalle et que pour chaque sommets u et v il y a une arête entre u et v si et seulement si l'intersection entre leurs intervalles associés n'est pas nulle, alors le graphe défini par ces sommets et ces arêtes est un graphe d'intervalles.

Graphe de permutation

Soit P une permutation de la séquence 1,...,n. Le graphe d'inversion associé à P est le graphe dont les sommets sont les entiers 1,...,n et dont pour tout sommets u et v il y a une arête entre u et v si et seulement si u et v sont inversés dans P.
Un graphe est un graphe de permutation s’il existe une permutation dont le graphe est son graphe d'inversion.

Graphe planaire

Un graphe est planaire s'il existe au moins une façon de le dessiner dans le plan sans que deux arêtes se croisent. Cette propriété est importante pour les circuits imprimés monocouche. Voir l'article complet Graphe planaire.

Graphe k-régulier

Un graphe régulier est un graphe où chaque sommet est de degré k.

Graphe split

Un graphe est split s’il existe une partition des sommets du graphe en deux sous-ensembles S et C telle que S est un ensemble stable et C est une clique.

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

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

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 <math>G=(V,E)</math> et <math>G'=(V',E')</math> tels que <math>|V| \le |V'|</math>
Question : Le graphe <math>G</math> est-il "inclus" dans le graphe <math>G'</math> à un renommage de ses sommets prèes? Ou, plus formellement, existe-t'il une fonction <math>f : V \rightarrow V'</math> telle que <math>\forall (u,v) \in V^2, (u,v) \in E \Rightarrow (f(u),f(v)) \in E'</math>

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

  • Isomorphisme de sous-graphe (non partiel)
Donnée : deux graphes <math>G=(V,E)</math> et <math>G'=(V',E')</math> tels que <math>|V| \le |V'|</math>
Question : Le graphe <math>G</math> est-il "identique" à un sous-graphe du graphe <math>G'</math> à un renommage de ses sommets près? Ou plus formellement, existe-t'il une fonction <math>f : V \rightarrow V'</math> telle que <math>\forall (u,v) \in V^2, (u,v) \in E \Leftrightarrow (f(u),f(v)) \in E'</math>. 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 <math>G</math> ne formant pas un arc ne peut être mis en correspondance par la fonction <math>f</math> qu'avec un couple de sommets du graphe <math>G</math> ne formant pas un arc également.

Ce problème est NP-complet dans le cas général. Il existe des algorithme polynomiaux pour certains graphes particuliers (e.g. les arbres).


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

Ce problème est NP-difficile.

Algorithmes importants de la théorie des graphes

Algorithmes de parcours d'un graphe

Algorithmes de Plus Courts Chemins (PCC)

Algorithmes d'arbres couvrants de poids minimum

Algorithmes pour les flots maximums

Algorithmes de coloration

(voir coloration de graphe)

Algorithmes divers

Liens externes

Récupérée de « http://fr.freepedia.org/Th%C3%A9orie_des_graphes.html »


Views
Outils personels
Boîte à outils
Autres langues
Autres Liens