AccueilđŸ‡«đŸ‡·Chercher

Cycle (théorie des graphes)

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

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

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

  • 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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.