Graphe chemin

Graphe chemin
Graphe chemin
Path-graph.svg
Graphe chemin à 6 sommets
Nombre de sommets n
Nombre d'arêtes n − 1
Rayon \lfloor n/2 \rfloor
Diamètre n − 1
Automorphismes 2
Nombre chromatique 2
Indice chromatique 2
Propriétés distance-unité

En théorie des graphes, un graphe chemin (en anglais path graph) est un arbre où chaque nœud est de degré au plus deux.

Voir aussi

  • Chemin
  • Graphe cycle, le seul autre type de graphe connexe dont tous les sommets sont de degré au plus deux.

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • 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 …   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

Share the article and excerpts

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