Cycle (théorie des graphes)

Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).

Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle.

Le terme de cycle désigne parfois aussi le graphe cycle $C_{n}$ constitué d'un cycle élémentaire de longueur n.

Terminologie

Si la chaine est élémentaire, c'est-à-dire ne passe pas deux fois par un même sommet, alors on parle de cycle élémentaire. Un cycle élémentaire ne contient pas d'autre cycle. Dans un cycle élémentaire, chaque sommet a un degré égal à deux.

La longueur d'un cycle élémentaire est le nombre de ses arêtes (ou de ses sommets). Étant donné un graphe $G$ , la longueur minimale de ses cycles s'appelle la maille de $G$ , tandis que la longueur maximale de ses cycles s'appelle la circonférence de $G$ .

Si, dans un graphe, deux sommets d'un cycle sont reliés par une arête qui n'appartient pas au cycle, cette arête est appelée corde du cycle. Un cycle de G est induit dans $G$ lorsqu'il n'a pas de cordes. Un graphe est dit cordal ou triangulé si chacun de ses cycles de quatre sommets ou plus possède une corde.

Lorsque le cycle contient un nombre impair (réciproquement pair) d'arêtes on l'appelle un cycle impair (réciproquement cycle pair).

Dans les graphes pondérés, le poids d'un cycle est la somme des poids des arêtes qu'il contient. Si ce poids est négatif, on parle de cycle absorbant.

Présence de cycles

Théorème — Un graphe simple de degré minimal $\delta \geq 2$ possède un cycle de longueur au moins égale à $(\delta +1)$ .

Démonstration

$G$ comporte au moins une chaine, puisque $\delta \geq 2$ . Soit $(v_{0},v_{1},\cdots ,v_{n})$ la plus longue de ces chaînes.

Considérons les voisins de $v_{n}$ . Ils font tous partie de cette chaine, car sinon on pourrait construire une chaine plus longue en concaténant un voisin n'appartenant pas à la chaine.

Soit $v_{m}$ le voisin dont l'indice $_{m}$ est minimal (c.à.d. le plus éloigné de $v_{n}$ ). Le long de la chaine, $v_{m}$ est situé à au moins $\deg(v_{n})$ sommets de $v_{n}$ car le graphe est simple. Comme $\deg(v_{n})\geq \delta$ , le sommet $v_{m}$ est au moins à $\delta$ sommets de $v_{n}$ via cette chaine.

Le cycle $(v_{m},v_{m+1},\cdots ,v_{n},v_{m})$ est ainsi de longueur au moins égale à $\delta +1$ .

Un graphe non orienté sans cycles s'appelle une forêt. Le théorème précédent a pour conséquence qu'une forêt comporte forcément des sommets de degré zéro (isolés) ou de degré un (feuilles). Cette condition n'est pas suffisante, un graphe de degré minimal zéro ou un peut quand même comporter des cycles.

Problèmes liés

Le problème du cycle hamiltonien consiste à trouver un cycle élémentaire passant par tous les sommets.
Le problème du cycle eulérien consiste à trouver un cycle passant exactement une fois par chaque arête.
Le problème du postier chinois consiste à trouver un plus court cycle passant au moins une fois par chaque arête.

Voir aussi

Graphe acyclique

Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.