Graphe acyclique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 est une forêt, c'est-à-dire un ensemble d'arbres.