Graphe
Terme lié
Concept parent de : Graphe documentaire
Définitions
Graphe. « Un graphe est un triplet Γ = (V ; E, N) où V est l'ensemble des sommets du graphe ; il sera commode d'utiliser la notion V(Γ) pour désigner l'ensemble des sommets du graphe ; N est un ensemble qui sert à étiqueter les arêtes (par exemple N = {1, 2, ..., p}, N = {bleu, rouge, vert, ..., violet}, N = ā...) ; E ⊂ Pā(V) × N est l'ensemble des arêtes ; notation E = E(Γ) »
(Bretto et al., 2012[1], p. 1).
Degré. « Le degré d'un sommet x ∈ V est le nombre d'arêtes incidentes à x »
(ibid.[1], p. 6).
Chaîne. « Soit un graphe Γ = (V ; E, N) et x, y ∈ V ; une chaîne C de x à y est une succession finie d’arêtes »
(ibid.[1], p. 7). La longueur de la chaîne k correspond à la somme des arrêtes reliant x à y. « Une chaîne est simple si elle ne contient pas deux fois une même arrête. elle est élémentaire si elle ne contient pas deux fois un même sommet »
(ibid.[1], p. 8).
Cycle. « Un cycle est une chaîne fermée simple »
(ibid.[1], p. 8).
Graphe connexe. « Un graphe est dit connexe si pour toute paire de sommets x, y ∈ V, il existe une chaîne entre x et y : on dit alors que les sommets x et y sont connectés »
(ibid.[1], p. 8).
Sous-graphes. « Un graphe Γ' = (V' ; E', N') est appelé sous-graphe de Γ si V' c V et E' ⊂ E »
(ibid.[1], p. 9).
Graphe orienté. « Un graphe orienté ou digraphe
(ibid.[1], p. 14). (ou simplement Γ) est un triplet
= (V ;
, N) défini de la manière suivante : V est l'ensemble des sommets ; notation V = V(
) ;
⊂ V × V × N est l'ensemble des arcs ; notation
=
(Γ) ; N est un ensemble servant à étiqueter les arcs. Un arc a ∈
sera noté ((x, y), n) : l'arc va de x vers y »
Chemin. « Un chemin C de x à y est une suite finie [d'arcs] ; l'entier k est la longueur du chemin. »
« Un chemin est simple s'il ne contient pas deux fois le même arc ; il est élémentaire s'il ne contient pas deux fois le même sommet »
(ibid.[1], p. 15).
Circuit. « Un circuit est un chemin simple dont les extrémités coïncident »
(ibid.[1], p. 15).
Références
Bretto A, Faisant A, Hennecart F. Éléments de théorie des graphes. Collection IRIS : Springer, 2012. ISBN : 978-2-8178-0280-0