Définition 1 : Un cycle de longueur h est une succession de h arcs tous différents, chaque arc intermédiaire ayant une extrémité en commun avec l'arc précédent et l'autre avec l'arc suivant, l'arc initial et l'arc final ayant aussi leur extrémité libre en commun.
Le cycle sera dit "élémentaire" si en le parcourant, on ne rencontre pas plusieurs fois le même sommet.
|
|
 |
EXEMPLES
C1 = (1,5,4) est un cycle élémentaire de longueur 3
C2 = (1,2,7,9,8,3) est un cycle élémentaire de longueur 5
(1,5,6,2,5,4) n'est pas un cycle
C3 = (3, 4, 9, 7, 6. 8) est un cycle de longueur 7 qui n'est pas élémentaire |
Remarque : Dans un graphe simple, on peut aussi définir un cycle comme une succession de sommets.
Dans l'exemple, C1 = abea, C2 = abcfeda et C3 = daefced
|
|
Notation Vectorielle
Les arcs du graphe étant numérotés de 1 à m, on peut faire correspondre à tout cycle un m-uplet (un "vecteur") composé de -1, 1 et 0 de ma manière suivante :
Si l'arc n'appartient pas au cycle, on met un "0"
Si l'arc appartient au cycle et est parcouru dans le bon sens (on le qualifie alors de "direct"), on met un +1
Si l'arc appartient au cycle mais parcouru dans le mauvais sens (on le qualifie alors de "inverse"), on met un -1 Exemples : C1 = (1,0,0,-1,1,0,0,0,0), C2 = (1,1,1,0,0,0,1,1,1) et C3 = (0,0,1,1,0,-1,-1,1,-1) |
|
On peut donc assimiler un cycle à un vecteur et définir la somme (vectorielle) de 2 ou plusieurs cycles.
Exemple : C3 est la somme du cycle (3,4,8) et du cycle (9,7,6).
|
|
Propriété 1 : Tout cycle est la somme de cycles élémentaires sans arc commun.
Propriété 2 : Un cycle est élémentaire si et seulement s'il est minimal.
On peut donc définir une base de cycles (au sens vectoriel) comme étant une famille de cycles libre (tous les cycles indépendants, aucun ne peut se définir comme combinaison linéaire des autres) et génératrice (tout cycle peut s'écrire comme combinaison linéaire des cycles de la famille).
Le Cardinal (Nombre d'éléments) commun de toutes les bases de cycles sera appelé nombre cyclomatique et noté μ.
Propriété 3 : Soit un graphe G d'ordre n (n sommets) avec m arcs et p composantes connexes: μ(G) = m - n + p .
Définition 2 : Soit A un ensemble de sommets du graphe, on appellera cocycle associé à A, qu'on notera ω(A), l'ensemble des arcs incidents à A, ceux qui quittent A seront notés positivement et ceux qui pointent vers A seront notés négativement.
Un cocycle c'est donc l'ensemble des arcs qui relient A aux autres sommets du graphe; si on enlève les arcs du cocycle on "déconnecte" A.
Cycle et cocycle sont des notions duales.
Exemple : En réutilisant le graphe ci-dessus, si A = {b,e} ω(A) = {-1 , +2 , -4 , +6 , +8 , -9} On peut, bien sûr appliquer la notation vectorielle définie pour les cycles, aux cocycles; on obtiendrait pour l'exemple ci-dessus le vecteur : (-1,1,0,-1,0,1,0,1,-1).
Définition 3 : Un cocycle sera dit élémentaire quand il est composé d'arcs reliant deux sous-ensembles de sommets connexes qui partitionnent une composante connexe du graphe (donc tous les sommets en cas de graphe connexe). Le cocycle donné dans l'exemple ci-dessus n'est pas élémentaire parce qu 'il est compsé d'arcs reliant {b,e} à {a,c,d,f} et si {b,e} est connexe, ce n'est pas le cas de {a,c,d,f}. Le cocycle associé à {a,b,d}dont la notation vectorielle est (0,1,0,1,1,0,0,-1,0) est élémentaire.
Propriété 4 : Tout cocycle est la somme de cocycles élémentaires sans arc commun.
Propriété 5 : Un cocycle est élémentaire si et seulement s'il est minimal.
On peut donc définir une base de cocycles (au sens vectoriel) comme étant une famille de cocycles libre (tous les cocycles indépendants, aucun ne peut se définir comme combinaison linéaire des autres) et génératrice (tout cocycle peut s'écrire comme combinaison linéaire des cocycles de la famille).
Le Cardinal (Nombre d'éléments) commun de toutes les bases de cocycles sera appelé nombre cocyclomatique et noté λ
Propriété 6 : Soit un graphe G d'ordre n (n sommets) avec p composantes connexes: λ(G) = n - p.
Exercice 1 : Monter qu'un cycle et un cocycle sont toujours orthogonaux (produit scalaire nul) Indication : Démontrer la proposition avec un circuit. Généraliser.
Exercice 2 : |
|
 |
1) Déterminer tous les cycles élémentaires
2) Extrayez-en une base
3) Déterminer tous les cocycles élémentaires
4) Extrayez-en une base
|