Graphe acyclique
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 le terme de circuit pour désigner ces derniers.

Notation : DAG pour "Directed Acyclique Graph".

Remarques.

  1. Un plus court chemin dans un DAG peut être déterminer en temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) linéaire.
  2. Le terme circuit désigne aussi les dépendants minimaux dans la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative,...) des matroïdes, ainsi les cycles d'un graphes sont aussi les circuits du matroïde des forêts.
Page générée en 0.048 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique