Chemin (graphe)
- Chemin (graphe)
-
Chemin (théorie des graphes)
Pour les articles homonymes, voir
Chemin.
Dans un graphe orienté, un chemin d'origine x et d'extrémité y est défini par une suite finie d'arcs consécutifs, reliant x à y.
La notion correspondante dans les graphes non orientés est celle de chaîne.
Un chemin élémentaire est un chemin ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts.
Un chemin simple est un chemin ne passant pas deux fois par un même arc, c'est-à-dire dont tous les arcs sont distincts.
Catégorie : Concept en théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Chemin (graphe) de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe chemin — à 6 sommets Nombre de sommets n Nombre d arêtes n − 1 Rayon … Wikipédia en Français
Chemin 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
chemin — [ ʃ(ə)mɛ̃ ] n. m. • 1080; du lat. pop. °camminus, mot gaulois I ♦ A ♦ (Concret) 1 ♦ Voie qui permet d aller d un lieu à un autre (⇒ route, voie); spécialt Bande déblayée assez étroite qui suit les accidents du terrain (opposé à route, allée).⇒… … Encyclopédie Universelle
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
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 Hamming — H(4,2) Notation H(d,q) Nombre de sommets qd Nombre d arêtes … 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
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
