# Glossaire de la théorie des graphes

* Haut – A
* B
* C
* D
* E
* F
* G
* H
* I
* J
* K
* L
* M
* N
* O
* P
* Q
* R
* S
* T
* U
* V
* W
* X
* Y
* Z

## A
### Acyclique

    graphe ne contenant pas de cycle.

### Adjacence

    une liste d'adjacence est une structure de données constituée d'un tableau dont le $i$-ème élément correspond à la liste des voisins du $i$-ème sommet.

### Adjacence

    une matrice d'adjacence est une matrice carrée usuellement notée $A$, de dimensions $|V|\times |V|$, dont chaque élément $A_{ij}$ est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices $i$ et $j$ (pour un graphe simple non pondéré, $A_{ij}\in \{0,1\}$). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

### Adjacence

    une relation d'adjacence propriété de deux sommets d'être connectés par la même arête (dits sommets adjacents) ou propriété de deux arêtes de présenter une extrémité commune (dites arêtes adjacentes). Également appelé relation de voisinage.

### Adjoint

    un graphe adjoint est synonyme de line graph.

### Admittance

    autre nom d'une matrice laplacienne.

### Aléatoire

    un graphe est aléatoire, ou non déterministe, dès que sa construction fait intervenir des probabilités.

### Arbre

    graphe connexe et acyclique. Équivalent à un graphe connexe à $n$ sommets et $n-1$ arêtes.

### Arbre enraciné ou arborescence

    graphe acyclique orienté où on distingue une racine de degré entrant nul, et où tous les autres sommets sont de degré entrant 1.

### Arc

    arête dans un graphe orienté. Autre formulation : couple (ensemble ordonné de deux éléments) de sommets reliés par une arête dans un graphe non orienté.

### Arc-transitif

    un graphe G est arc-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arcs. Étant donné deux arêtes $e_{1}=u_{1}v_{1},e_{2}=u_{2}v_{2}\in G$, il existe deux automorphismes $(f_{V},f_{E}):G\rightarrow G$ et $(g_{V},g_{E}):G\rightarrow G$ tels que $f_{E}(e_{1})=e_{2}$, $g_{E}(e_{1})=e_{2}$, et $f_{V}(u_{1})=u_{2}$, $f_{V}(v_{1})=v_{2}$, $g_{V}(u_{1})=v_{2}$, $g_{V}(v_{1})=u_{2}$.

### Arête

    connexion entre deux sommets $A$ et $B$. Dans le cas des graphes orientés on parle d'arc. Le terme « arête » est alors utilisé pour désigner l'ensemble des deux arcs $(A,B)$, c'est-à-dire de $A$ vers $B$, et $(B,A)$, c'est-à-dire de $B$ vers $A$. Ne pas confondre avec arête en géométrie.

### Arête multiple

    ensemble d'arêtes parallèles relatif à un couple de sommets.

### Arête parallèle

    arête ayant pour extrémités les mêmes sommets qu'une autre arête. On parle d'arêtes parallèles.

### Arête-transitif

    un graphe est arête-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arêtes. Autre formulation de la condition : pour tout couple d'arêtes, au moins un automorphisme envoie la première composante sur la seconde. Toutes les arêtes jouent exactement le même rôle à l'intérieur du graphe. Exemple : un graphe complet.

### Automorphisme

    isomorphisme d'un graphe sur lui-même. Chaque graphe possède au moins un automorphisme : l'identité. L'ensemble des automorphismes d'un graphe forme un groupe.

## B
### Biconnexe

    un graphe non orienté est dit biconnexe si, en retirant n'importe lequel de ses sommets, il reste connexe. Cela revient à dire que le graphe n'a pas de point d'articulation.

### Biparti

    un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux sous-ensembles $U$ et $V$ telle que deux sommets adjacents soient dans deux parties différentes. Cela revient à dire que le graphe est 2-colorable.

### Biparti complet

    un graphe est dit biparti complet s'il est biparti et qu'il existe une arête entre chaque sommet de $U$ et de $V$. On note $K_{m,n}$ le graphe biparti complet tel que $|U|=m$ et $|V|=n$.

### Birégulier

    un graphe est dit birégulier s'il est biparti et si chacune de ses parties $U$ et $V$ n'a que des sommets de même degré. On le dit $(a,b)$-régulier si $deg(U)=a$ et $deg(V)=b$.

### Blob

    bridgeless component en anglais, ensemble de sommets ne contenant pas d'isthme.

### Bloc

    ensemble de sommets ne contenant pas de point d'articulation.

### Boucle

    arête partant d'un sommet et arrivant sur lui-même.

## C
### Cactus

    un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun.

### Centralité

    un indicateur de centralité est une mesure censée capturer la notion d'importance dans un graphe, en identifiant les sommets les plus significatifs.

### Chaîne

    dans un graphe non orienté, une chaîne est une suite finie non vide de sommets telle que chaque paire de sommets consécutifs de la suite soit une arête du graphe ; la suite (un moins en longueur) d'arêtes ainsi obtenue caractérise aussi la chaîne. La notion correspondante dans un graphe orienté est celle d'un chemin. La longueur d'une chaîne est celle de sa suite d'arêtes (un moins que la longueur sa suite de sommets). La source de la chaîne est son premier sommet, et son but est son dernier sommet. Une chaîne est dite élémentaire si aucun sommet ne figure plus d'une fois dans la suite, à l'exception de la source et le but de la chaîne qui peuvent coïncider.

### Chemin

    dans un graphe orienté, un chemin est une suite finie non vide de sommets telle que chaque couple de sommets consécutifs de la suite est un arc du graphe ; la suite d'arcs ainsi obtenue caractérise aussi le chemin. La notion correspondante dans un graphe non orienté est celle d'une chaîne. La longueur d'un chemin est celle de sa suite d'arcs (un moins que la longueur sa suite de sommets). La source du chemin est son premier sommet, et son but est son dernier sommet. Un chemin est dit élémentaire si aucun des sommets ne figure plus d'une fois comme source, ni plus d'une fois comme but d'un arc du chemin (mais source et but du chemin peuvent coïncider).

### Chenille

    c'est un arbre dans lequel tous les sommets sont à distance au plus 1 d'un chemin central.

### Circonférence

    longueur du plus grand cycle.

### Nombre chromatique

    nombre minimal de couleurs pour colorier un graphes sans sommets adjacents de même couleur.

### Nombre chromatique non répétitif

    nombre minimal de couleurs pour colorier un graphes dont les chaînes sont sans facteurs de couleurs répétées.

### Clique

    sous-graphe induit complet, c'est-à-dire un sous-ensemble des sommets tels que chacun est connecté à tous les autres. Une clique est un ensemble indépendant (ou stable) du graphe complémentaire.

### Coloration

    fonction associant à tout sommet une couleur, tels que deux sommets adjacents aient une couleur différente (c'est-à-dire partitionne les sommets en ensembles indépendants).

### k-coloration

    coloration d'un graphe en k couleurs distinctes.

### Complémentaire

    le complémentaire (ou inverse, ou complément) ${\bar {G}}$ d'un graphe simple $G=(V,E)$ est un graphe simple qui a les mêmes sommets que G, reliés si et seulement s’ils ne sont pas reliés dans le graphe d'origine, soit ${\bar {G}}=(V,[V]^{2}\backslash E)$.

### Complet

    dans un graphe complet chaque sommet est relié à tous les autres par une arête ou un arc. On note $K_{n}$ le graphe complet à n sommets.

### Composante

    une composante d'un graphe est un sous-graphe connexe maximal.

### Connexe

    un graphe est connexe s'il existe un chemin entre tout couple de sommets. Quand on parle de connexité pour un graphe orienté, on considère non pas ce graphe mais le graphe non-orienté correspondant. On peut déterminer ceci par exemple avec un algorithme de parcours en profondeur. 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.

### k-arête-connexe

    un graphe est k-arête-connexe s'il cesse d'être connexe uniquement quand on supprime k arêtes ; ceci peut se vérifier par la présence de k chaînes disjointes (ne partageant aucune arête) entre chaque sommet.

### k-sommet-connexe (ou k-connexe)

    un graphe est k-sommet-connexe s'il cesse d'être connexe uniquement quand on supprime k sommets.

### Contenir

    un graphe $G$ contient $H$ si $H$ est un sous-graphe induit de $G$.

### Contraction

    supprime une arête d'un graphe en fusionnant ses deux extrémités. Autrement dit, la contraction $G/e$ d'une arête $e_{xy}$ à un sommet $x$ rend le sommet $x$ adjacent à tous les voisins précédents de $y$.

### Corde

    arête reliant deux sommets non-adjacents d'un cycle.

### Cospectral

    deux graphes sont cospectraux s'ils ont le même spectre. Ce spectre pouvant être basé sur plusieurs matrices, on peut préciser A-cospectraux pour le spectre de la matrice d'adjacence et L-cospectraux pour le spectre de la matrice laplacienne.

### Coupe

    partition des sommets en deux sous-ensembles. Peut aussi désigner l’ensemble des arêtes ayant une extrémité dans chaque sous-ensemble.

### Couverture par sommets

    Une couverture par sommets ou transversale d'un graphe G est un ensemble C de sommets de G tel que chaque arête du graphe est incidente à au moins un sommet de C.

### Couvrant

    un sous-graphe $H$ d'un graphe $G$ couvre $G$ (on dit aussi qu'il est un sous-graphe couvrant ou un graphe partiel de $G$) si tous les sommets de $G$ sont dans $H$ ($V_{H}=V_{G}$).

### Creux

    un graphe creux possède un nombre d'arêtes (ou d'arcs) faible par rapport au nombre de sommets.

### Cubique

    graphe 3-régulier.

### Cycle

    chaîne dont les sommets de départ et de fin sont les mêmes. Autrement dit, soit un chemin dont les arêtes sont $E=\{s_{0}s_{1},...,s_{k-2}s_{k-1}\}$ : le cycle est alors défini par $E\cup \{s_{k-1}s_{0}\}$. Dans un graphe orienté, on parlera d'un circuit plutôt que d'un cycle, même si la terminologie n'est pas tout à fait stabilisée.

### Cyclomatique

    le nombre cyclomatique d'un graphe $G=(V,E)$ est $M=|E|-|V|+P$, où $P$ est le nombre de composantes connexes. C'est également la dimension de l'espace des cycles.

## D
### Degré

    dans le cas non-orienté et non pondéré, le degré $d(s)$ du sommet $s$ est le nombre d'arêtes de $s$. Dans le cas d'un graphe orienté, le degré entrant $d^{-}(s)$ est le nombre d'arcs vers $s$ tandis que le degré sortant $d^{+}(s)$ est le nombre d'arcs sortant de $s$. Le degré maximum est noté $\Delta (G)$, et le degré minimal $\delta (G)$. Dans le cas pondéré, le degré d'un sommet est la somme du poids des arêtes incidentes à ce sommet.

### Demi-carré

    le sous-graphe induit sur l'un des deux sous-ensembles de sommets du carré d'un graphe biparti. Se dit aussi moitié bipartie.

### Demi-graphe

    un graphe biparti qui possède environ la moitié des arêtes d'un graphe biparti complet sur ses sommets.

### Degrés (matrice)

    la matrice des degrés d'un graphe $G$ est une matrice carrée de taille $|V|\times |V|$ telle que $\forall i,D_{ii}=deg(i)$ et $\forall i,j,i\neq j,D_{ij}=0$.

### Dense

    un graphe dense possède un nombre d'arêtes (ou d'arcs) proche du nombre maximal.

### Densité

    la densité d'un graphe est le rapport entre le nombre d'arêtes (ou d'arcs) divisé par le nombre d'arêtes (ou d'arcs) possibles. Dans le cas d'un graphe non orienté, simple et fini $G=(V,E)$, c'est le rapport ${\frac {2|E|}{|V|\cdot (|V|-1)}}$.

### Diamètre

    excentricité maximale des sommets, notée $D$.

### Dilatation

    dans un plongement où $f$ associe des sommets d'un graphe $G$ à ceux d'un graphe $H$, la dilatation est la distance maximale entre les images par $f$ de deux sommets adjacents dans $G$. Autrement dit, si deux sommets sont voisins dans un graphe, leurs images peuvent être séparées par un chemin qui augmente donc la distance entre eux, et la plus grande augmentation est la dilatation.

### Dimension

    la dimension minimale d'un espace euclidien afin qu'un graphe puisse y être représenté avec des arêtes qui soient toutes de longueur 1.

### Dimension euclidienne ou dimension fidèle

    la dimension minimale d'un espace euclidien afin qu'un graphe puisse y être représenté de telle sorte que des sommets soient à distance 1 si et seulement s'ils sont reliés.

### Dimension bipartie

    le nombre minimal de sous-graphes bipartis complets nécessaires pour couvrir toutes les arêtes d'un graphe.

### Dimension métrique

    le nombre minimal de sommets d'un sous-graphe $S$ de $G$ tel que tous les autres sommets sont déterminés de façon unique par leur distance aux sommets de $S$.

### Distance

    la distance $d_{G}(x,y)$ entre $x$ et $y$ est la longueur du plus court chemin entre ces sommets ; aussi appelée distance géodésique.

### Distance (matrice de)

    matrice d'éléments a$_{ij}$ correspondant a la longueur du plus court chemin (la distance) entre les sommets d'indices i et j.

### Distance-régulier

    un graphe est distance-régulier si pour tous sommets $u,v\in V$, le nombre de sommets voisins de $u$ à distance $i$ et le nombre de sommets voisins de $v$ à distance $j$ ne dépendent que de $i,j$ et de la distance $d(u,v)$ entre $u$ et $v$. Formellement, $\exists b_{i},c_{i}\in N,i=0...d$ tels que $c_{0}=0$ et $\forall i\geq 1,c_{i}=|N(v)\cap N_{i-1}(u)|,b_{i}=|N(v)\cap N_{i+1}(u)|$

### Dominant (ou absorbant)

    un ensemble de sommet est dominant si tout sommet en fait partie ou est voisin d'un sommet en faisant partie.

### Dureté

    la dureté (« toughness » en anglais) est une mesure de la connexité d'un graphe. Un graphe $G$ est dit $t$-dur pour un nombre réel donné $t$ si, pour tout entier $k>1$, $G$ ne peut pas être divisé en $k$ composantes connexes par la suppression de moins de $tk$ sommets.

## E
### Espace

    soit un graphe $G=(V,E)$. L'espace des sommets est l'espace vectoriel sur $\{0,1\}$ avec comme base $\{v_{1},...,v_{n}\}$, soit un espace de dimension $n$. De même, l'espace des arêtes est l'espace vectoriel sur $\{0,1\}$ avec comme base $\{e_{1},...,e_{m}\}$, soit un espace de dimension $m$. Le principe du 0 et du 1 est qu'on obtient 1 pour un sommet (ou arête) appartenant à l'espace et 0 sinon.

### Étiquetage

    fonction associant chaque sommet à une étiquette, pouvant être dans n'importe quel ensemble (réels, mots, couleurs...).

### Eulérien

    un chemin eulérien est un chemin qui passe par toutes les arêtes exactement une fois. Un cycle eulérien est un chemin eulérien où les sommets de départ et d'arrivée sont les mêmes. Un graphe où l'on peut construire un cycle eulérien est appelé graphe eulérien ; si l'on ne peut construire que des chemins eulériens, alors le graphe est semi-eulérien. Un graphe est eulérien si chaque sommet est de degré pair.

### Excentricité

    l'excentricité d'un sommet est sa distance maximale à tous les autres sommets.

### Expanseur (graphe)

    expander graph en anglais. Soit G = (V, E) un graphe à n sommets. Pour un sous-ensemble de sommets W ⊆ V, on appelle frontière de W et on note ∂(W) l’ensemble des arêtes de G partant d'un sommet de W et n'aboutissant pas à un sommet de W. G est un graphe expanseur dans le rapport γ si, pour tout sous-ensemble de sommets W de cardinal |W| ≤ n/2, on a |∂(W)| ≥ γ |W|.

### Expansion

    si $H$ est un mineur de $G$ (c. à d. $H$ résulte d'une série de contractions) alors $G$ est une expansion de $H$. Une opération d'expansion remplace un sommet $s$ par deux sommets $s_{1},s_{2}$ connectés par une arête, et $s_{1}$ et $s_{2}$ sont connectés à tous les voisins de $s$. Dans le cas d'un plongement d'un graphe $G_{1}=(V_{1},E_{1})$ dans $G_{2}=(V_{2},E_{2})$, une expansion a une autre signification : il s'agit du rapport entre la taille des deux graphes, soit ${\frac {|V_{2}|}{|V_{1}|}}$.

## F
### Facteur

    un $k$-facteur est un sous-graphe couvrant $k$-régulier.

### Feuille

    sommet de degré 1 dans un arbre.

### Fini

    un graphe est fini si le nombre de ses arêtes et de ses sommets est fini. Un graphe infini dont chaque sommet a un degré fini est dit localement fini.

### Force

    d'un graphe, l’analogue de la dureté pour les arêtes.

### Forêt

    graphe non-orienté acyclique. Chaque composante connexe d'une forêt forme un arbre.

### Frontière des arêtes

    les arêtes menant d'une partie d'un graphe au reste du graphe.

### Frontière intérieure des sommets

    les sommets d'une partie d'un graphe reliés au reste du graphe.

### Frontière extérieure des sommets

    les sommets du reste d'un graphe reliés à une partie du graphe.

## G
### Graphe

    structure composée d'abstractions mathématiques appelées objets (ou sommets ou nœuds ou points) dans laquelle certaines paires d'objets sont en relation par des arêtes (ou liens ou lignes).

### Grille

    graphe en forme de grille

## H
### Hamiltonien

    un graphe est hamiltonien s'il a au moins un cycle passant par tous les sommets exactement une fois, et ce cycle est appelé cycle hamiltonien. Un cycle hamiltonien est aussi un cycle élémentaire de même ordre que le graphe.

### Homéomorphes (graphes)

    deux graphes G et H sont dits homéomorphes si l'on peut arriver au même graphe I en subdivisant certaines de leurs arêtes (à ne pas confondre avec la notion d'homomorphisme).

### Hypergraphe

    généralise la notion de graphe en autorisant une arête à relier plus de deux sommets.

## I
### Incidence

    la matrice d'incidence d'un graphe $G=(V,E)$ est la matrice de dimensions $|V|\times |E|$ dans laquelle l'entrée $b_{ij}$ vaut 1 si le sommet $v_{i}$ est une extrémité de l'arête $x_{j}$, 2 si $x_{j}$ est une boucle sur $v_{i}$ et 0 sinon. Dans le cas orienté, on a $b_{ij}=-1$ si $x_{j}$ sort de $v_{i}$ et 1 si elle y rentre.

### Indépendant

    deux sommets sont indépendants s'ils ne sont pas connectés, c'est-à-dire pas adjacents. Un ensemble de sommets est indépendant (ou stable) s'il n'y a pas deux de ses sommets adjacents.

### Indice chromatique (nombre chromatique des arêtes)

    le nombre minimal de couleurs nécessaire pour colorer les arêtes d'un graphe ne pas confondre avec le nombre chromatique (des sommets).

### Indice de Hosoya ou indice Z

    nombre de couplages d'un graphe.

### Induit

    un sous-graphe $H$ d'un graphe $G$ est dit induit lorsque, pour tout couple $(x,y)$ de sommets de $H$, $x$ est connecté à $y$ dans $H$ si et seulement si $x$ est connecté à $y$ dans $G$. Autre formulation de la condition : l'ensemble des arêtes de $H$ correspond à l'ensemble des arêtes de $G$ incidentes à deux sommets de $H$.

### Infini

    contraire de fini.

### Intervalle

    un graphe d'intervalle est un graphe G tel que l'on puisse associer à chacun de ses sommets un intervalle sur l'ensemble des réels et tel que pour chaque sommet u et v de G 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,

### Invariant

    propriété du graphe dépendant uniquement de sa structure (i.e. indépendante de son étiquetage). Par exemple, le degré moyen du graphe ou son spectre.

### Isolé

    sommet de degré 0, c'est-à-dire n'ayant pas de voisin.

### Isomorphisme

    un isomorphisme de graphes est un morphisme de graphes bijectif (ou inversible).

### Isomorphe

    deux graphes sont isomorphes s'il existe un isomorphisme de graphes de l'un vers l'autre. C'est-à-dire s'ils ont exactement la même structure. Il suffit de remplacer les étiquettes des sommets pour qu'un graphe soit la copie conforme de l'autre.

### Isospectral

    voir cospectral.

### Isthme

    arête d'un graphe dont l'élimination augmente le nombre de composantes connexes du graphe.

## J
### Jumeau

    deux sommets sont jumeaux s'ils ont le même voisinage. Des vrais jumeaux respectent en plus la contrainte d'être voisins l'un de l'autre, et si cette contrainte n'est pas respectée alors on parle de faux jumeaux. La notion de voisinage peut être généralisée pour une distance supérieure à 1 : on définit le voisinage de $s\in V$ jusqu'à distance $r$ par $N_{r}=\{u\in V|d(u,s)\leq r\}$, et deux jumeaux $s_{1},s_{2}\in V$ ont alors $N_{s_{1}}=N_{s_{2}}$.

## L
### Laplacienne

    une matrice laplacienne est une matrice $L=D-A$ où $D$ est la matrice des degrés et $A$ la matrice d'adjacence ; on obtient sa forme normalisée $L'$ par $L'=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$, où $I$ dénote la matrice identité. Est utilisée dans la théorie spectrale des graphes.

### Libre d'échelle

    un graphe est libre d'échelle si la distribution de ses degrés est proche d'une loi de puissance. Cette notion provient de la physique, et les divergences locales ou l'écart de la distribution par rapport à une loi de puissance ne sont pas spécifiés.

### Line graph

    le line graph d'un graphe $G$ est le graphe $L(G)$ où on inverse sommets et arêtes, c'est-à-dire que deux sommets adjacents dans le line graph correspondent à deux arêtes incidentes à un même sommet dans G.

## M
### Maille

    girth en anglais, longueur du plus court cycle. Si un graphe est acyclique, sa maille est considérée comme infinie. La maille paire (respectivement maille impaire) est la longueur du plus court cycle de longueur paire (respectivement impaire).

### Mineur

    un graphe $H$ est un mineur de $G$ s'il est isomorphe à un graphe pouvant être obtenu en contractant zéro ou plus arêtes de $G$.

### Morphisme

    application entre deux graphes qui respecte la structure de ces graphes.

### Moulin

    un graphe moulin est une somme de graphes complets se partageant un sommet central.

### Multigraphe

    graphe doté d'une ou plusieurs arêtes multiples ou de boucles.

## N
### Nœud

    sommet dans un réseau. Un nœud interne est un sommet dans un arbre de degré supérieur à 1, c'est-à-dire n'étant pas une feuille.

### Nombre chromatique

    nombre minimum de couleurs pour colorer un graphe. Le nombre chromatique d'un graphe $G$ est noté $\chi (G)$.

### Noyau

    sous-ensemble de sommets à la fois stable et dominant.

### Nul

    un graphe nul est soit un graphe ne contenant aucun sommet, soit un graphe dont tous les sommets sont isolés (i.e. sans arêtes ni arcs).

## O
### Ordre

    nombre de sommets du graphe.

### Orienté

    un graphe est orienté si les arêtes ont un sens, par exemple $e_{uv}$ indique qu'il y a un arc de $u$ à $v$. Un graphe est non orienté si ses arêtes n'ont pas de sens : $e_{uv}$ indique qu'il y a une arête entre $u$ et $v$.

### Outer-planar

    voir planaire extérieur.

## P
### Parfait

    un graphe est parfait si le nombre chromatique de chacun de ses sous-graphes induits $H$ est égal à la taille de la clique maximale de $H$.

### Partiel

    Un graphe $(V,F)$ est un graphe partiel de $(V,E)$ si $F\subseteq E$. Un sous-graphe partiel de $(V,E)$ est un graphe $(W,F)$, avec $W\subseteq V$ et $F\subseteq E$.

### Partition

    séparation des sommets du graphe en des ensembles de sommets disjoints deux à deux et non vides dont l'union permet de retrouver tous les sommets. Formellement, une partition d'un graphe $G$ en $k$ parties sépare l'ensemble des sommets $V$ en un ensemble $P_{k}=\{V_{1},...,V_{k}\}$ qui vérifie les trois propriétés suivantes : $\forall V_{i}\in P_{k},V_{i}\neq \emptyset$ et $V_{i}\subset V$ ; $\cup _{i=1..k}V_{i}=V$ ; et $\forall (V_{i},V_{j})\in P_{k}^{2},i\neq j\Rightarrow V_{i}\cap V_{j}=\emptyset$.

### Petit monde

    un graphe a le phénomène du petit-monde si son coefficient de clustering est élevé et la distance moyenne entre deux sommets faible. Cette notion provient de la physique, et il n'y a pas de définition exacte quant à ce qui est élevé et ce qui est faible ; on considère la distance moyenne comme faible tant qu'elle n'excède pas le logarithme du nombre de sommets.

### Planaire

    un graphe est planaire si on peut le dessiner dans un plan sans croiser deux arêtes. Un graphe est planaire s'il ne contient pas $K_{5}$ et $K_{3,3}$ comme mineurs.

### Planaire extérieur

    dans un graphe planaire, on considère les régions (ou faces) entourées par des arêtes comme internes. L'ensemble du graphe est donc entouré par une région externe. Si tous les sommets sont sur la face externe, alors le graphe est planaire extérieur.

### Plongement

    soient deux graphes $G_{1}=(V_{1},E_{1})$ et $G_{2}=(V_{2},E_{2})$, un plongement est une fonction injective de $V_{2}$ dans $V_{1}$ tel que chaque arête de $V_{2}$ corresponde à un chemin disjoint de $G_{1}$. Un plongement permet de dire qu'on peut utiliser un graphe pour simuler les capacités de l'autre en termes de connexion : s'il y a une arête (i.e. un chemin dédié) entre deux sommets, alors on la retrouvera dans le graphe simulant sous la forme d'un chemin dédié (mais pouvant être plus long).

### Point d'articulation

    dans un graphe connexe, un sommet est dit d’articulation si le sous-graphe obtenu en le supprimant a plus de composantes connexes .

### Polynôme caractéristique

    le polynôme $|\lambda I-A|$ de la matrice d'adjacence $A$ d'un graphe G est son polynôme caractéristique, et on le note $P_{G}(\lambda )$.

### Pondéré

    un graphe pondéré est un graphe auquel on adjoint une fonction de valuation. Autrement dit, on associe des nombres (qu'on désigne ici par le terme « poids ») à ses arêtes, à ses sommets ou aux deux. On note $p(v)$ (resp. $p(i)$) le poids d'un sommet $v$ (resp. $i$) et $p(v,v')$ (resp. $p(i,j)$) le poids d'une arête $(v,v')$ (resp. $(i,j)$). La fonction $p$ est la fonction de valuation.

### Pont

    dans un graphe connexe, un pont est une arête dont la suppression déconnecte le graphe.

### Produit

    le produit de deux graphes $G$ et $H$ (remplissant éventuellement certaines conditions) est un troisième graphe obtenu à partir de $G$ et de $H$ en appliquant certaines règles. On distingue le produit cartésien, le produit tensoriel, le produit lexicographique (en), le produit fort, le produit conormal, le produit modulaire (en), le produit enraciné (en) et le produit zig-zag de graphes.

### Promenade

    également appelé parcours ; voir chemin (considéré en général comme non-élémentaire). Une promenade close (ou parcours fermé) est un circuit.

### Puits

    dans un problème de flot, sommet consommant le flot. Généralement de degré sortant nul, mais pas nécessairement.

## R
### Racine

    sommet particulier d'une arborescence à partir duquel il existe un chemin unique vers tous les autres sommets du graphe.

### Rayon

    excentricité minimale des sommets, notée $R$.

### Rayon

    dans un graphe infini, une chaîne simple $(s_{0},s_{1},\ldots )$ infinie ; une telle chaîne existe si le graphe est connexe et localement fini.

### Régulier

    un graphe est $k$-régulier si chacun de ses sommets est de degré $k$.

### Relation de Djokovìc-Winkler

    deux arêtes $e_{xy}$ et $e_{uv}$ sont en relation de Djokovìc-Winkler, et on le note $e_{xy}\Theta e_{uv}$ si on a l'inégalité $d_{G}(x,u)+d_{G}(y,v)\neq d_{G}(x,v)+d_{G}(y,u)$. Cette relation est réflexive et symétrique.

### Réseau de flot ou réseau de transport

    un graphe valué aux arcs modélisant un problème de transport.

### Roncier

    Un roncier est une collection de sous-graphes connexes où deux sous-graphes quelconques ont un sommet en commun ou chacun comprend une extrémité d'une arête. L'ordre d'un roncier est la plus petite taille d'un ensemble de sommets qui a une intersection non vide avec tous les sous-graphes. La largeur d'arbre d'un graphe est l'ordre maximum de l'un de ses ronciers.

## S
### Scindé

    un graphe est scindé (split graph en anglais) si ses sommets peuvent être partitionnés en une clique et un stable.

### Seuil

    Un graphe est à seuil s'il existe un nombre réel $S$ et, pour chaque sommet $v$, un poids (nombre réel) $p(v)$ tel que pour deux sommets $u,v$ la paire $(u,v)$ est une arête si et seulement si $p(u)+p(v)>S$.

### Séparateur

    C'est un sous-ensemble $X$ de l'ensemble $V$ des sommets d'un graphe tel que le sous-graphe induit par $G\setminus X$ n’est pas connexe.

### Simple

    également appelé Schlicht), graphe fini, non orienté, sans boucles ni arêtes multiples.

### Sommet

    un graphe est composé de sommets reliés par des arcs ou des arêtes. Également appelé nœud ou plus rarement point.

### Sommet-transitif

    un graphe est sommet-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses sommets. Autre formulation de la condition : pour tout couple de sommets, au moins un automorphisme envoie la première composante sur la seconde. Tous les sommets jouent exactement le même rôle à l'intérieur du graphe. Un graphe sommet-transitif est ainsi nécessairement régulier.

### Source

    dans un problème de flot, sommet produisant le flot. Un tel sommet est généralement de degré entrant nul, mais pas nécessairement.

### Split

    un graphe $G=(V,E)$ est split s'il y a une partition de V en deux sous-ensembles S et C tel que S est un ensemble de G et C est une clique de G. On note $G=(S,C,E)$.

### Sous-graphe

    graphe contenu dans un autre graphe. Formellement, avec des notations intuitives, un graphe $H=(V_{H},E_{H})$ est un sous-graphe de $G=(V_{G},E_{G})$ si $V_{H}\subset V_{G}$ et $E_{H}\subset E_{G}$. Il est induit si $E_{H}=E_{G}\cap V_{H}\times V_{H}$.

### Spanner

    sous-graphe couvrant dont on essaye de minimiser le nombre d'arêtes (i.e. la densité) tout en conservant des bonnes propriétés de distance. Dans un spanner additif (respectivement multiplicatif), la distance entre deux sommets peut être augmentée (respectivement multipliée) jusqu'à un certain facteur appelé le délai (respectivement la dilatation).

### Spectre

    ensemble des valeurs propres d'une matrice représentant le graphe. La matrice peut être de Laplace ou d'adjacence. Les relations entre le spectre du graphe et ses propriétés font l'objet de la théorie spectrale des graphes.

### Stable

    un ensemble stable est un ensemble de sommets 2 à 2 indépendants. Synonyme : ensemble indépendant.

### Subdivision

    la subdivision d'un graphe consiste à ajouter des sommets sur les arêtes, c'est-à-dire à remplacer des arêtes par des chemins.

### Subdivision barycentrique

    la subdivision d'un graphe $G$ où chaque arête de $G$ a été remplacée par un chemin de longueur deux par insertion d'un sommet dans chaque arête.

### Symétrique

    un graphe est symétrique s'il est à la fois arête-transitif et sommet-transitif. Cela revient à vérifier que toutes ses arêtes et tous ses sommets sont indistinguables en termes d'isomorphisme de graphe. Exemple : graphe de Petersen.

## T
### Taille

    nombre d'arêtes (ou d'arcs) du graphe.

### Technique spectrale

    technique faisant intervenir le spectre du graphe.

### Tournoi

    un graphe orienté obtenu en orientant chaque arête d'un graphe complet.

### Transposé

    le transposé d'un graphe orienté est le même graphe, mais dont les arêtes ont été inversées.

### Transversal

    un transversal (ou couverture nodale, ou support) 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. Le complémentaire d'un transversal est un stable.

### Triangle

    cycle de longueur trois.

### 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.

### Triconnexe

    un graphe non orienté est dit triconnexe si, en retirant deux quelconques de ses sommets, il reste connexe. Cela revient à dire que le graphe n'a pas de point d'articulation.

### Trivial

    un graphe est trivial s'il a un seul (graphe singleton) ou aucun sommet (graphe nul). On peut utiliser un graphe trivial pour commencer une preuve par récurrence, mais ils sont implicitement exclus des théorèmes dont ils constitueraient parfois des contre-exemples inintéressants.

## V
### Valuation

    fonction associant un poids à chaque arête et/ou sommet du graphe. On parle alors de graphe valué. Voir la définition de graphe pondéré plus haut dans cette page.

### Vecteur d'intersection

    séquence $\{b_{0},b_{1},...b_{D},c_{1},c_{2},...,c_{D}\}$ d'un graphe distance-régulier.

### Vide

    un graphe vide est un graphe sans arêtes, voir graphe nul.

### Voisinage

    le voisinage d'un sommet v est l'ensemble des sommets adjacents à v (et éventuellement le sous-graphe induit)