Conception des chaînes éditoriales

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 (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 » (ibid.^[1], p. 14).

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).

• Bretto A, Faisant A, Hennecart F. Éléments de théorie des graphes. Collection IRIS : Springer, 2012. ISBN : 978-2-8178-0280-0