Acyclique

Graphe acyclique

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éterminé en temps linéaire.
  2. 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 Portail des mathématiques
Ce document provient de « Graphe acyclique ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Acyclique de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • acyclique — [ asiklik ] adj. • v. 1920; de 2.a et cyclique 1 ♦ Géol. Relief acyclique (ou modelé),qui ne s explique pas par un cycle d érosion. 2 ♦ Chim. organ. À chaîne ouverte. 3 ♦ Math. Se dit d une structure algébrique qui ne possède pas de cycle. ⊗… …   Encyclopédie Universelle

  • Graph acyclique — Graphe acyclique 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 …   Wikipédia en Français

  • Graphe Acyclique — 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 …   Wikipédia en Français

  • Graphe Acyclique Orienté — Un exemple de graphe acyclique orienté Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés. La notion est usuelle dans …   Wikipédia en Français

  • Graphe acyclique oriente — Graphe acyclique orienté Un exemple de graphe acyclique orienté Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés.… …   Wikipédia en Français

  • Graphe acyclique orienté — Un exemple de graphe acyclique orienté Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés. La notion est usuelle dans …   Wikipédia en Français

  • Graphe orienté acyclique — Un exemple de graphe orienté acyclique En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG) est un graphe orienté qui ne possède pas de cycle. La notion est usuelle dans plusieurs domaines de… …   Wikipédia en Français

  • 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é… …   Wikipédia en Français

  • Machine acyclique — ● Machine acyclique machine homopolaire à courant continu …   Encyclopédie Universelle

  • a- — 1. a ♦ Élément, du lat. ad, marquant la direction, le but à atteindre, ou le passage d un état à un autre (var. ad ; ac , af , ag , al , an , ar , as , at ) : amener, alunir, adoucir. ⇒ à. a 2. a ♦ Élément tiré du gr. exprimant la négation (« pas …   Encyclopédie Universelle

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”