Chaîne (graphe)

Chaîne (graphe)
Page d'aide sur l'homonymie Pour les articles homonymes, voir Chaîne.

Dans un graphe non orienté, une chaîne reliant x à y est définie par une suite finie d'arêtes consécutives, reliant x à y.

La notion correspondante dans les graphes orientés est celle de chemin.

Vocabulaire

Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts.

Une chaîne simple est une chaîne ne passant pas deux fois par un même arête, c'est-à-dire dont tous les arêtes sont distincts.

Un cycle est un chemin dont les deux extrémités sont identiques.

La longueur d'une chaîne est le nombre d'arêtes du chemin, ou bien, dans le cas d'un graphe pondéré, la somme des poids des arêtes. Dans ce dernier cas, on veillera à distinguer une plus courte chaîne (i.e. de poids minimal) d'une chaîne la moins longue (i.e. ayant un nombre minimum d'arêtes).


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Chaine (graphe) — Chaîne (graphe) Pour les articles homonymes, voir Chaîne. Dans un graphe non orienté, une chaîne reliant x à y est définie par une suite finie d arêtes consécutives, reliant x à y. La notion correspondante dans les graphes orientés est celle de… …   Wikipédia en Français

  • Chaîne (Graphe) — Pour les articles homonymes, voir Chaîne. Dans un graphe non orienté, une chaîne reliant x à y est définie par une suite finie d arêtes consécutives, reliant x à y. La notion correspondante dans les graphes orientés est celle de chemin. Ce… …   Wikipédia en Français

  • Graphe d'une chaîne de Markov — et classification des états Le graphe d une chaîne de Markov et la classification des états sont des notions de la théorie des graphes utilisées en calcul des probabilités. Sommaire 1 Graphe d une chaîne de Markov 2 Classification des états …   Wikipédia en Français

  • Chaine De Markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaine de Markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaine de markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaîne De Markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

  • Chaîne de Markov à espace d'états discret — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaîne de markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

  • Graphe d'Errera — Représentation du graphe d Errera Nombre de sommets 17 Nombre d arêtes 45 Distribution des degrés 5 (12 sommets) 6 (5 sommets) Rayon …   Wikipédia en Français

Share the article and excerpts

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