Graphe orienté et non-orienté
Un graphe $G$ est un couple $(V, E)$ où $V$ est un ensemble (fini ou infini) et $E$ un ensemble constitué de paires $\{u,v\}$ ou de singletons $\{u\} $ d'éléments de $V.$ Les éléments de $V$ sont appelés les sommets ou nœuds de $G$, et les éléments de $E$ les arcs ou arêtes de $G$. On dit aussi que $G$ est un graphe non orienté ou non dirigé.
Les graphes sont usuellement représentés graphiquement à l'aide de cercles pour les sommets et de lignes pour les arêtes. Un même graphe peut avoir plusieurs représentations graphiques.
Si $V$ est fini, on parle de graphe fini. Le nombre de sommets est alors appelé ordre de $G$.
Si $\{u,v\}$ est une arête, alors $u$ et $v$ sont les extrémités de l'arête. Une arête constituée par un singleton $\{u\}$ s'appelle une boucle. Un graphe qui ne contient pas de boucle s'appelle un graphe simple. Parfois, la définition d'un graphe non orienté exclue l'existence de boucle.
Deux arcs sont adjacents s'ils ont au moins une extrémité en commun. Si deux sommets $u$ et $v$ sont reliés par un arc, on dit que $u$ et $v$ sont des sommets voisins ou adjacents.
Le degré d'un sommet $u$ désigne le nombre d'arcs dont ce sommet est une extrémité (une boucle comptant pour deux dans le calcul du degré). Le degré du graphe est la somme des degrés des sommets. Un sommet dont le degré est nul est appelé isolé.
Un graphe orienté (ou graphe dirigé ou digraphe) est un couple $(V, E)$ où $V$ est un ensemble (fini ou infini) et $E$ est une partie de $V\times V.$ Les éléments de $V$ sont les sommets et les éléments de $E$ sont les arêtes. Cette fois, l'ordre au sein des couples de $E$ est important. Si $a = (u, v) \in E$, alors $u$ et $v$ sont respectivement l'origine et la destination de $a$. Ce sont les extrémités de l'arc $a$ qui relie $u$ à $v$. Dans ce cas, $a$ est un arc sortant de $u$ ou arc incident à $u$ vers l'extérieur (resp. un arc entrant dans $v$ ou arc incident à $v$ vers l'intérieur).
Le vocabulaire des graphes non orientés s'étend aux graphes orientés, avec quelques spécifications supplémentaires lorsque l'ordre est important. Ainsi, le demi-degré sortant (resp. demi-degré entrant) de $v$ est le nombre d'arcs sortant de $v$ (resp. d'arcs entrant dans $v$).
Il est souvent commode d'associer certaines valeurs aux arcs ou aux sommets d'un graphe pour modéliser certaines situations.
Un graphe $G = (V, E)$ (orienté ou non) est étiqueté (par $f$) s'il existe une fonction : $$ f: E \longrightarrow \Sigma $$ où $\Sigma$ est un ensemble quelconque (par exemple un ensemble de mots ou de nombres).
Si $\Sigma \subseteq \mathbb{R}^+$ on parle généralement de graphe pondéré et $f$ est appelée fonction de poids.
Si $a$ est un arc, $f(a)$ est l'étiquette, le label ou encore le poids de $a$. On peut de la même manière définir un étiquetage des sommets au moyen d'une fonction $g: V \longrightarrow \Sigma$.
Le mot graphe a été utilisé dans ce sens pour la première fois
par James Sylverster en 1878. Les lettres $V$ et $E$ utilisées ici viennent de l'anglais vertex (sommet) et edge (arête).