Cycle (théorie des graphes)

thumb|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 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. 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. 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. Le problème du cycle hamiltonien consiste à trouver un cycle élémentaire passant par tous les sommets.