next up previous
suivant: Cliques, Stables, Coloration monter: Sous graphes, graphes partiels précédent: Sous graphes, graphes partiels

Définitions générales

Soit $ G=(X,\,E)$ un graphe. On va désormais définir les notions importantes de sous graphe et de graphe partiel. Afin d'illustrer notre propos, nous nous servirons du graphe suivant comme base :

Figure 1.7: Graphe de base pour l'illustration des graphes partiels et sous graphes
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=gpbase.eps}
\end{center}
\end{figure}


\begin{defi}[Graphe partiel]
Soit $E_p \: \subset \: E$\ un sous ensemble des a...
...\ de $G$,
$G_p\,=\,(X,\,E_p)$\ est un \emph{graphe partiel} de $G$.
\end{defi}
En résumé, on obtient un graphe partiel de $ G$ en supprimant certains arcs. Par exemple, dans la figure (1.8), et à partir du graphe de la figure (1.7), si l'on ne retient que les arcs marqués en gras sur la partie de gauche, l'on obtient le graphe partiel de la partie de droite. Les raisons de travailler sur des graphes partiels sont légion. Par exemple, l'on pourrait vouloir se limiter aux arcs présentant certaines caractéristiques importantes. Considérons un problème de recherche d'itinéraires où chaque axe routier est représenté par un arc. Si l'on ne désire emprunter que des autoroutes, on peut extraire le graphe partiel associé aux autoroutes.

Figure 1.8: Exemple d'extraction d'un graphe partiel
\begin{figure}
\leavevmode
\begin{center}
\begin{tabular}{cc}
\psfig{figure=...
...s (en gras) & Graphe partiel obtenu
\end{tabular}
\end{center}
\end{figure}


\begin{defi}[Sous graphe]
Soit $G\,=\,(X,\,E)$\ un graphe. Un \emph{sous graphe...
...displaymath}
E_p\,=\,E\,\Cap\,(X_p\,\times\,X_p)
\end{displaymath}
\end{defi}
De manière plus littéraire, on obtient un sous graphe en extrayant un sous ensemble des sommets de $ G$ et en ne retenant que les arcs qui relient ces sommets, tel qu'illustré sur la figure (1.8).

Figure 1.9: Exemple d'extraction d'un sous graphe
\begin{figure}
\leavevmode
\begin{center}
\begin{tabular}{cc}
\psfig{figure=...
...mets (en gras) & Sous graphe obtenu
\end{tabular}
\end{center}
\end{figure}


next up previous
suivant: Cliques, Stables, Coloration monter: Sous graphes, graphes partiels précédent: Sous graphes, graphes partiels
Bruno Garcia 2000-12-17