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

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

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