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é).
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Graph_cycle.svg/320px-Graph_cycle.svg.png)
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
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.