Cycle (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Cycle.
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.

Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives (chaine) 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é).

Le terme de cycle désigne parfois aussi le graphe cycle C_n constitué d'un cycle élémentaire de longueur n.

Terminologie[modifier | modifier le code]

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, le degré de tous les sommets est égal à deux.

La longueur d'un cycle élémentaire est le nombre de ses sommets (ou de ses arêtes). É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[modifier | modifier le code]

Théorème — Un graphe simple de degré minimal \delta \ge 2 possède un cycle 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[modifier | modifier le code]

  • 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[modifier | modifier le code]