next up previous
suivant: Les graphes non orientés monter: Introduction précédent: Introduction

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.
\begin{defi}[Graphe]
Un graphe est caractérisé par 2 ensembles nommés $X$\ et $...
...l'\emph{origine} et la \emph{destination} de l'arc $\overline{e}$.
\end{defi}
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)=$

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

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
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=graphe1.eps, width=15.0cm}
\end{center}
\end{figure}

A cela, nous allons ajouter quelques définitions supplémentaires :
\begin{defi}[Boucle]
On appelle boucle un arc $(i,\,i)$
\end{defi}
Par exemple, dans le graphe de la figure (1.1), l'arc $ (2,\,2)$ est une boucle.
\begin{defi}[Sommets adjacents]
Les sommets $i$\ et $j$\ du graphe $G=(X,\,E)$\...
..., l'arc $(i,\,j)$\ \textbf{ou} l'arc $(j,\,i)$\ appartiennent à $E$.
\end{defi}
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.
\begin{defi}[Graphe simple]
Un graphe $G=(X,\,E)$\ est dit simple si et seuleme...
...est un graphe sans boucle ni
arcs multiples entre les même sommets.
\end{defi}
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.
\begin{defi}[Graphe planaire]
On qualifie de \emph{planaire} tout graphe pouvant être dessiné sans que ses
arcs ne se croisent.
\end{defi}
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
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=planaire.eps}
\end{center}
\end{figure}


next up previous
suivant: Les graphes non orientés monter: Introduction précédent: Introduction
Bruno Garcia 2000-12-17