Graphe acyclique

Un graphe acyclique est un graphe ne contenant aucun cycle.

Il y a deux notions différentes de graphes acycliques selon qu'on considère des graphes orientés ou non orientés.

• Graphes orientés : voir l'article détaillé, graphe orienté acyclique (on utilise ici cycle dans le sens de circuit).
• Graphes non orientés : un graphe non orienté acyclique connexe est un arbre. Une union d'arbres est une forêt.

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