Définitions fondamentales

Il existe plusieurs manières de caractériser un graphe, nous allons en parcourir quelques unes. Notons immédiatement qu'il existe deux grands types de graphes : les graphes orientés et les graphes non orientés. Nous allons commencer notre étude par les graphes orientés puis nous traiterons des différences avec le cas non orienté dans une section spécifique.

Si la notation ensembliste des graphes est la seule qui soit rigoureuse, ces derniers valent surtout par leur représentation graphique. En effet, soit le graphe $G=(X,\,E)=$

$$\left\{ \begin{array}{lcl} X &=& \{ 1,\,2,\,3,\,4 \} \\ ... ...;\, (2,\,3)\,;\, (4,\,3)\,;\, (4,\,1)\} \end{array} \right.$$

Ce même graphe peut être associé aux deux représentations suivantes et même d'autres. Du coup, n'oubliez jamais la règle suivante :

Ne vous fiez pas à l'aspect visuel de deux graphes pour les comparer. Seule la comparaison des ensembles de sommets et d'arcs est fiable !

Figure 1.1: Deux représentations `` graphiques '' du même graphe

A cela, nous allons ajouter quelques définitions supplémentaires :

Par exemple, dans le graphe de la figure (1.1), l'arc $(2,\,2)$ est une boucle.

Par exemple, dans le graphe de la figure (1.1), les sommets $1$ et $4$ sont adjacents (grâce à l'arc $(4,\,1)$), alors que les sommets $2$ et $4$ ne le sont pas.

Par exemple, le graphe de la figure (1.1) n'est pas un graphe simple car il contient à la fois la boucle $(2,\,2)$ et 2 arcs $(2,\,3)$. Remarque : Il existe une bijection entre l'ensemble des graphes simples et l'ensembles des relations binaires sur $X$, les propriétés sur les relations s'étendant donc aux graphes.

Une fois de plus, il convient de ne pas oublier qu'il ne faut jamais se fier à la représentation visuelle d'un graphe. Par exemple, le graphe de la figure suivante n'apparaît pas planaire sur sa représentation de gauche. Toutefois, si vous modifiez sa représentation graphique comme montré à droite il est évident qu'il est bel et bien planaire.

Figure 1.2: Exemple de graphe planaire