110
Recherche opérationnelle
Maintenant, si l'on supprime dans certains sommets, ainsi que les arcs dont ils sont
soit l'extrémité terminale, soit l'extrémité initiale, on obtient un graphe
avec
et
, appelé sous-graphe de .
Ainsi le graphe :
Figure 3
est un graphe partiel du graphe de la figure 1 et le graphe :
Figure 4
est un sous-graphe du graphe de la figure 1, par suppression des sommets
.
6.2.4. Adjacence, incidence, demi-degrés
On appelle arcs adjacents, deux arcs distincts qui ont une extrémité commune.
Deux sommets distincts liés par un arc sont également appelés adjacents.
Un arc, dont les deux extrémités ne sont pas confondues, est incident vers l'intérieur au
sommet qui constitue son extrémité terminale, incident vers l'extérieur au sommet qui
constitue son extrémité initiale.
Le demi degré intérieur d'un sommet est le nombre d'arcs incidents vers l'intérieur à ce
sommet; on le note
Le demi degré extérieur d'un sommet est le nombre d'arcs incidents vers l'extérieur à
ce sommet; on note
Si
est appelé une sortie du graphe.