Lexique de la théorie des graphes

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

Adjacence et voisinage

L'adjacence dans un graphe concerne soit une relation entre deux sommets, soit une relation entre deux arêtes (ou arcs).

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. Deux arêtes sont adjacentes si elles ont incidentes à un même sommet.

Arbre

Un arbre (orienté ou non) est un graphe sans cycle

Lorsque l'on parle d'arbre, on parle alors de feuilles et de nœud ainsi que de racine

Arbre couvrant

Un arbre couvrant d'un graphe

G

non orienté est un graphe

T

tel que :

$T$ couvre $G$ ;
$T$ est un arbre.

Tout graphe connexe admet un arbre couvrant.

Arbre recouvrant de poids minimum

Soit

G

un graphe non orienté et

p

une fonction de poids qui :

à toute arête de $G$ associe un nombre réel ;
à tout sous-graphe $G'$ de $G$ associe la somme des poids des arêtes de $G'$ .

Un arbre recouvrant de poids minimum est un arbre

T

recouvrant

G

tel que, pour tout arbre

T'

, si

T'

recouvre

G

alors $p(T')\leq p(T)$ .

Carré d'un graphe

Le carré d'un graphe

G

est le graphe

G'

qui a les mêmes sommets que

G

et dont deux sommets sont reliés s’ils sont reliés dans le graphe

G

d'origine ou s’ils ont un voisin en commun dans

G

Chaîne et chemin dans un graphe

Étant donné un graphe

G

non orienté (resp. orienté), une chaîne dans

G

est un sous-graphe de

G

qui appartient à la classe des chaînes (resp. chemins).

Chaîne hamiltonienne

Soit

G

un graphe non orienté et

C

un sous-graphe de

G

C

est une chaîne hamiltonienne de

G

si et seulement si

C

est une chaîne du même ordre que

G

Clique

Une clique est le complémentaire d'un stable, c'est-à-dire que c'est un ensemble de sommets deux-àdeux adjacent, ou autrement dit qui induit un sous-graphe complet. Une p-clique est une clique de cardinalité p.

Une clique de 3 sommets (en rouge) dans un graphe à 6 sommets

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

Coloration de graphe

Une k-coloration d'un graphe G=(S,A) est une application c de S dans {1, 2, ..., k} (avec k entier naturel non nul) telle que, pour tout couple (a, b) de sommets adjacents dans G, les couleurs c(a) et c(b) respectivement de a et b sont distinctes. Ainsi une coloration est une partition en stables.

Article détaillé : Coloration de graphe.

Cycle et circuit

Un cycle (resp. circuit) dans un graphe

G

est un sous-graphe de

G

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

G

un graphe et

C

un sous-graphe de

G

C

est un cycle hamiltonien de

G

C

est un cycle du même ordre que

G

Degré, degré entrant, degré sortant, degré maximum, degré minimum

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

s

le degré entrant et le degré sortant. Le premier correspond au nombre d'arcs dont l'extrémité finale est

s

. Le second est le nombre d'arcs dont l'extrémité initiale est

s

. Le degré d'un sommet

s

dans un graphe orienté est la somme du degré entrant et sortant de

s

Le degré maximum (resp. degré minimum) d'un graphe

G

, noté $\Delta (G)\,$ (resp. $\delta (G)\,$ ), est égal au degré maximum (resp. degré minimum) de l'ensemble des degrés de tous les sommets de

G

Ensemble dominant

Un ensemble dominant est un sous-ensemble de sommets du graphe tel que chaque sommet du graphe est soit dans l'ensemble dominant soit voisin d'un sommet de l'ensemble dominant. Remarquons qu'un stable maximal par-rapport à l'inclusion est nécessairement dominant (autrement il existe un sommet hors du stable que l'on pourrait lui ajouter).

Graphe acyclique

Un graphe acyclique est un graphe non orienté qui ne contient aucun cycle. (Notons qu'un arbre est un graphe sans cycle)

Si le graphe est orienté, on considère le graphe non-orienté associé.

Graphe inverse ou graphe complémentaire

Le graphe inverse ou graphe complémentaire 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.

A noter que, si on ne se place pas dans le cadre des graphes « généraux », alors on doit considérer les boucles (arêtes ou arcs ayant pour extrémités un même sommet). En pratique, lorsque le cadre n'est pas explicité, on travaille avec des graphes simples (c'est-à-dire : sans boucle ni arête multiple).

Incidence

On appelle incidence la relation qui relie une arête (ou un arc) et un sommet d'un même graphe.

La définition d'un graphe est donc entièrement contenue par sa fonction d'incidence (disons qu'une arête et un sommet sont incidents si l'arête "touche" le sommet, ou le "relie" à un autre sommet ; voir Théorie des graphes pour une définition formelle et une définition informelle des graphes).

Nombre chromatique

Le nombre chromatique d'un graphe G est le plus petit nombre de couleurs distinctes suffisant à colorer G.

Noyau

Un noyau est un sous-ensemble de sommets à la fois stable et dominant.

Ordre

L'ordre d'un graphe est le nombre de sommets de ce graphe.

Un graphe vide est d'ordre 0 (zéro). Un graphe à un (seul) sommet — avec une ou plusieurs arêtes (dans ce cas, appelées : boucles) — est d'ordre 1 ; c'est aussi une chaîne particulière. Un graphe à

n

sommets — où

n

est un entier naturel — est d'ordre

n

Partition

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

Parcours et parcours fermé

Un parcours de sommets (resp. d'arêtes, d'arcs) dans un graphe

G

est une liste ordonnée de sommets (resp. d'arêtes, d'arcs) de

G

telle que 2 sommets (resp. arêtes, arcs) consécutifs dans la liste sont adjacents (resp. incidents) dans le graphe. Un parcours est fermé si le premier élément de la liste est aussi le dernier.

Article détaillé : Parcours (graphe).

Parcours eulérien

Un parcours eulérien d'un graphe

G

non orienté est un parcours $(a_1, a_2, \ldots, a_m)$ des

m

arêtes de

G

tel que chaque arête de

G

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.

Puissance n^e d'un graphe

La puissance n^e d'un graphe permet d'identifier les sommets reliés par n-1 arcs.

Puits

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

Racine

Une racine, dans un graphe orienté, est un sommet

r

à partir duquel on peut atteindre tous les autres sommets du graphe orienté. On dit aussi que tout autre sommet du graphe orienté est à l’extrémité d’un chemin issu de

r

. Une racine se veut généralement le point d’origine d’une arborescence. Un circuit peut également posséder des racines.

Source

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

Sous-graphe

Soit

G = (S, A)

un graphe. Un sous-graphe de

G

est un graphe

G' = (S', A')

tel que :

$S' \subseteq S$
$A' \subseteq A$

S' = S

, G' est un sous-graphe couvrant (ou graphe partiel).

Si $A'=A\cap \big\{ \{ a,b\} | a,b \in S' \big\}$ (ou si $A'=A\cap (S'\times S')$ si

G

est orienté) alors

G'

est un sous-graphe induit.

Stable (ou ensemble indépendant)

Un stable est un sous-ensemble de sommets deux-à-deux non-adjacent. Autrement dit, un stable est un ensemble de sommets induisant un graphe 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 — le sous-graphe induit par l'ajout d'(au moins) un sommet du graphe à ce stable n'est pas stable. Mais ce stable n'est pas le plus grand en nombre de sommets puisque les sommets 3, 5 et 6 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.

Transversal (ou couverture nodale, ou support)

Un transversal d'un graphe est un sous-ensemble de sommet T tel que toute arête du graphe est incidente à au-moins un sommet de T.

Remarquons que le complémentaire d'un transversal est un stable du graphe (autrement il existerait une arête non-couverte par T). Ainsi déterminer un transversal minimum ou un stable maximum (ou même une clique maximum) sont des problèmes équivalent (dans un certain sens car cela n'est plus vrai du point de vue de l'approximabitilié de ces problèmes).

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 peut être le montant du péage à acquitter entre deux points, ou une mesure associée à toute autre ressource pour aller d'une ville à l'autre (consommation de carburant, coût, temps, etc.).

[modifier] Classes de graphes

Arbre

On nomme arbre un graphe non orienté, acyclique et connexe. 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.

Un arbre avec 4 feuilles et 3 nœuds internes.

D'autres définitions équivalentes sont possibles. Par exemple :

Pour une définition basée sur le nombre d'arêtes :

Un arbre est un graphe connexe à

n

sommets non orienté possédant

n - 1

arêtes.

Pour une définition inductive :

Un sommet est un arbre.

G = (S, A)

est un arbre, alors $(S\cup x, A \cup \big\{ \{ x,s \} \big\} )$ est un arbre

avec :

$x$ est un élément quelconque n'appartenant pas à $S$ et
$s$ un sommet de $S$ .

Aucun autre graphe n'est un arbre.

On peut démontrer qu'il y a

n (n - 2)

arbres numérotés à n sommets.

Arborescence

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îne

Une chaîne est un arbre possédant 2 feuilles. On peut 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 exemple :

pour une définition basée sur le degré :

Une chaîne est un graphe non orienté connexe de degré maximum inférieur ou égal à 2 et de degré minimum 1.

pour une définition inductive :

Un graphe réduit à un sommet est une chaîne.

G = (S, A)

est une chaîne, alors $(S \cup x, A \cup \big\{ \{ x,s \} \big\} )$ est une chaîne

avec :

$x$ un élément quelconque n'appartenant pas à $S$ et
$s$ un sommet de degré 1 de $S$ .

Aucun autre graphe n'est une chaîne.

Chemin

Un chemin est un graphe orienté connexe, réunissant les 3 conditions suivantes :

de degré entrant maximum 1,
de degré sortant maximum 1 et
de degré minimum 1.

Cycle et circuit

Un graphe

G

non orienté (resp. orienté) et connexe est un cycle (resp. circuit) 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 aléatoire

Un graphe est aléatoire s'il est généré par un processus aléatoire.

Article détaillé : Graphe aléatoire.

Graphe biparti

Un graphe est biparti s’il existe 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é :

K n

(en référence à Kuratowski).

Article détaillé : 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.

Quand on parle de connexité pour un graphe orienté, 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 cubique

Un graphe est dit cubique s'il est 3-régulier.

Graphe hamiltonien

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

Graphe d'intervalles

I est un ensemble d'intervalles sur les réels,

et qu'on peut associer à chaque sommet un intervalle

et que pour chaque sommet 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 tous 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.

Article détaillé : Graphe planaire.

Graphe k-régulier

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

Graphe réduit

Le graphe réduit du graphe G=(X,U) est le graphe G_r=(X_r,U_r) où les éléments de X_r sont les composantes fortement connexes de G et où les éléments de U_r sont des couples (A_i, A_j) d'éléments de X_r vérifiant la relation suivante : ∃ a_i ∈ A_i, ∃ a_j ∈ A_j / (a_i,a_j) ∈ U.

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.

Graphe triangulé

Un graphe est triangulé s'il ne contient pas un cycle de longueur quatre sans corde comme mineur. Les arbres, et les graphes d'intervalles notamment, sont triangulés.

Graphe k-partitionable

Un graphe G est k-partitionable s'il admet une S-partition.

Article détaillé : Graphe partitionable.

Graphe k-colorable

Un graphe G est k-colorable s'il admet une k-coloration.

Graphe parfait

Un graphe G est parfait si, pour tout sous-graphe induit H de G, le nombre chromatique de H est égal à la taille maximale d'une clique dans H.