Cycle (théorie des graphes)

suite de sommets d'un graphe débutant et finissant au même sommet

Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (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 constitué d'un cycle élémentaire de longueur n.

Terminologie

modifier

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  , la longueur minimale de ses cycles s'appelle la maille de  , tandis que la longueur maximale de ses cycles s'appelle la circonférence de  .

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   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

Théorème — Un graphe simple de degré minimal   possède un cycle de longueur au moins égale à  .

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
  • 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