Graphe acyclique
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
Un graphe acyclique est un graphe ne contenant aucun cycle.
Ce terme concerne les graphes orientés puisque les graphes non-orienté sans cycle sont les forêts (chaque composante connexe est un arbre). Afin de distinguer les cycles non-orientés des cycles orientés, on utilise utilise le terme de circuit pour désigner ces derniers.
Notation : DAG pour "Directed Acyclique Graph".
Remarques.
- Un plus court chemin dans un DAG peut être déterminer en temps linéaire.
- Le terme circuit désigne aussi les dépendants minimaux dans la théorie des matroïdes, ainsi les cycles d'un graphes sont aussi les circuits du matroïde des forêts.
 |
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
