Nombre cyclomatique

Définition :

Dans un graphe G=(X,U) un cycle est une séquence d ’arcs :m=(u1,u2,u3,…,uq) telle que :

1. Tout arc uk (1<k<q) il est relié par une de ses extrémités au précédent uk-1 et par l’autre au suivant uk (c’est une chaîne)
2. La séquence n’utilise pas deux fois le même arc (chaîne simple)
3. Le sommet initial et terminal de la chaîne coïncide Le cycle est élémentaire s’il vérifie de plus :
4. En parcourant le cycle on ne rencontre pas deux fois le même sommet sauf terminal et initial qui coïncident.
   

   

Les cycles se représentent aussi sous la forme de matrice.
Ici nous avons le cycle µ1=1,2=(1,-1,0,0,0,0,0)
Dans cette matrice « 1 » représente l’arc 1 parcouru dans le bon sens, « -1 » représente l’arc 2 parcourus dans le sens inverse. Les autres arcs sont à 0 car ils ne font pas partie du cycle.

Un cycle est une séquence d’arcs
Il suffit de suivre les arcs avec un stylo ou avec le doigt sans passer deux fois par le même arc.
Un cycle est une chaine. le point de départ est le point d’arrivée

Exemple :

Ici sont représentés 6 cycles.
Par exemple 1,6,2 est un cycle. Cela me fait passer par les sommets a, b , c, a.
On peut partir de n’importe quel sommet du cycle

Remarque : le sens n’a pas d’importance : b,c,d,b est le même cycle que d, b, c, d car on emprunte les mêmes arcs

Le nombre cyclomatique

Calcul du nombre cyclomatique : v(G) :
v(G)=m-n+p

n : nombre de sommets
m : nombre d’arcs
p : nombre de composantes connexes

Exemple :

Sur le graph de droite
m=6 car il y a 6 arcs
n=4 car on a 4 sommets
p=1 car on a 1 connexité

calcule de v(G)=m-n+p
v(G)=6-4+1=3
donc nous avons 3 cycles sur le graphe
Attention : a b c d a utilise deux cycles