Cycle (théorie des graphes)
- Cycle (théorie des graphes)
-
Pour les articles homonymes, voir
Cycle.
Dans un graphe non-orienté, un cycle est une suite d'arêtes consécutives (chaîne) dont les deux sommets extrémités sont identiques. Si la chaîne est élémentaire, c'est-à-dire ne passe pas deux fois par un même sommet, alors on parle de cycle élémentaire. Un cycle élémentaire ne contient pas d'autre cycle. Dans un cycle élémentaire, le degré de tous les sommets est égal à deux.
Lorsque le cycle contient un nombre impair (réciproquement pair) d'arêtes on l'appelle un cycle impair (réciproquement cycle pair).
Dans les graphes pondérés, le poids d'un cycle est la somme des poids des arêtes qu'il contient. Si ce poids est négatif, on parle de cycle absorbant.
Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).
Le graphe cycle
Le terme de cycle désigne parfois le graphe cycle Cn constitué d'un cycle élémentaire de longueur n.
Problèmes liés
- Le problème du cycle hamiltonien consiste à trouver un cycle élémentaire passant par tous les sommets.
- Le problème du cycle eulérien consiste à trouver un cycle passant exactement une fois par chaque arête.
- Le problème du postier chinois consiste à trouver un plus court cycle passant au moins une fois par chaque arête.
Voir aussi
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Cycle (théorie des graphes) de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Theorie des graphes — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français
Théorie des graphes — Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette… … Wikipédia en Français
Graphe (théorie des graphes) — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français
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
Lexique de la theorie des graphes — 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
Lexique en théorie des graphes — 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
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 Acyclique (grap … Wikipédia en Français
GRAPHES (THÉORIE DES) — On appelle théorie des graphes une classe de problèmes plus ou moins bien résolus. Leur résolution suscite chez les mathématiciens, en particulier à l’étranger, un engouement sans cesse croissant. Claude Berge, dans le discours inaugural des… … Encyclopédie Universelle
Arbre (théorie des graphes) — Arbre (informatique) Pour les articles homonymes, voir Arbre (homonymie) . Un arbre binaire En informatique, un arbre est une … Wikipédia en Français
Théorie spectrale des graphes — La théorie spectrale des graphes s intéresse aux rapports entre le spectre d un graphe et ses propriétés, et fait partie de la théorie algébrique des graphes. Un graphe peut être représenté par plusieurs matrices, et les valeurs propres d une… … Wikipédia en Français
