150
Recherche opérationnelle
La démonstration peut alors se faire en deux temps :
a) Nous allons d'abord démontrer la propriété suivante : Si un graphe G ne comporte pas
de cycles, on a
.
Pour cela, considérons un multigraphe
quelconque, et
le multigraphe obtenu en
ajoutant une arête entre deux sommets a
.
Deux cas se présentent :
1)
ne sont pas reliés dans par une chaîne (on ne crée pas de cycle en ajoutant
l'arête ).
Si
sont respectivement le nombre d'arêtes, le nombre de sommets et le nombre
de composantes connexes de , on a dans ce cas :
2)
sont reliés dans par une chaîne (on crée des cycles en ajoutant l'arête
).
Alors :
Considérons alors un graphe quelconque et le graphe partiel issu de G constitué par les
sommets isolés de (suppression de toutes les arêtes).
Pour ce graphe :
v(
Ajoutons progressivement les arêtes pour reconstituer .
D'après ce que l'on vient de voir, le nombre cyclomatique augmente d'une unité lorsque
l'on relie deux sommets déjà reliés entre eux par une chaîne, c'est-à-dire lorsque l'on crée
au moins un cycle. À la fin du processus, on a donc :
nombre de cycles de G.
et si G ne contient pas de cycles :
C.Q.F.D
Remarque 1 : on voit également que
Remarque 2 : si G contient un seul cycle, on voit que