Graphe sans cycle
- Graphe sans cycle
-
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 :
- Un plus court chemin dans un DAG peut être déterminé 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
Catégorie : Concept en théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe sans cycle de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe Planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… … Wikipédia en Français
Graphe planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… … Wikipédia en Français
Graphe diamant — Représentation du graphe diamant. Nombre de sommets 4 Nombre d arêtes 5 Distribution des degrés 2 (2 sommets) 3 (2 sommets) Rayon 1 … Wikipédia en Français
Graphe Petersen — Graphe de Petersen Graphe de Petersen Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier… … Wikipédia en Français
Graphe de Coxeter — Représentation du graphe de Coxeter. Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Rayon 4 … Wikipédia en Français
Graphe de Kneser — Le graphe de Kneser KG5,2, isomorphe au graphe de Petersen Notation KGn,k Nombre de sommets Distribution des degrés … Wikipédia en Français
Graphe De Coxeter — Le graphe de Coxeter Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Diamètre 4 Propriétés Hypohamilton … Wikipédia en Français
Graphe de coxeter — Le graphe de Coxeter Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Diamètre 4 Propriétés Hypohamilton … 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 partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A … Wikipédia en Français
