Cycle (graphe)

Cycle (graphe)

Cycle (graphe)

Page d'aide sur l'homonymie 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é des sommets est deux.

Lorsque que le cycle contient un nombre impair (respectivement pair) d'arêtes on l'appelle un cycle impair (respectivement 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.

Le graphe cycle

Le terme de cycle désigne parfois le graphe cycle Cn constitué d'un cycle élémentaire de longueur n.

Ce document provient de « Cycle (graphe) ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

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

  • Graphe des cycles —  Ne doit pas être confondu avec Graphe cycle ni Cycle (théorie des graphes). En mathématiques, et plus particulièrement en théorie des groupes, le graphe des cycles d un groupe représente l ensemble des cycles de ce groupe, ce qui est… …   Wikipédia en Français

  • 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

  • Cycle hamiltonien — Graphe hamiltonien En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne… …   Wikipédia en Français

  • Graphe Hamiltonien — En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être… …   Wikipédia en Français

  • Graphe roue — Quelques exemples de graphe roue. Notation Wn Nombre de sommets n Nombre d arêtes 2(n …   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 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 triangle — Représentation du graphe triangle. Notation C3, K3 Nombre de sommets 3 Nombre d arêtes 3 Distribution des degrés 2 ré …   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

Share the article and excerpts

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