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Ă©).
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.