Conception des chaînes éditoriales

L'histoire de la théorie des graphes débute avec les travaux d'Euler sur le problème devenu célèbre des ponts de Königsberg (Sachs, 1988^[1]). Euler cherchait à déterminer s'il existait un chemin empruntant les sept ponts Königsberg une seule fois. Pour résoudre son problème, Euler n'a pas réellement tracé un graphe, mais il a théorisé le problème de la même façon en nommant par une lettre les différentes terres séparées par les rivières et représenté les ponts par des séquences de lettres (AB relie ainsi la terre A à la terre B).^[2]

L'objectif de la théorie des graphes est de résoudre des problèmes en simplifiant leur représentation à une série de sommets et d’arêtes reliant ces sommets. La résolution du problème peut alors être traitée de façon logique en opérant des algorithmes particuliers cherchant à optimiser le graphe, ou à déterminer le plus court chemin, ou juste à caractériser la structure du graphe. Un des problèmes les plus connus adressé par la théorie des graphes est le problème du voyageur de commerce qui cherche à visiter un certain nombre de villes par le chemin le plus court (Kruskal, 1956^[3] ; Lin, 1965^[4])

La théorie des graphes est une discipline largement adressée tant par la recherche que dans la formation en logistique et informatique. Notre recherche mobilise des aspects rudimentaires de la discipline que nous définissons ci-après. Ces rudiments sont consensuels au sein de la discipline. La mobilisation de ces notions étant cependant novatrice dans l'analyse des chaînes éditoriales, nous rappelons ci-dessous leurs définitions (toutes issues de l'ouvrage « Éléments de théorie des graphes » (Bretto, Faisant & Hennecard, 2012^[5])).

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^[5], p. 1).

Degré. « Le degré d'un sommet x ∈ V est le nombre d'arêtes incidentes à x » (ibid.^[5], 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.^[5], 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.^[5], p. 8).

Cycle. « Un cycle est une chaîne fermée simple » (ibid.^[5], 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.^[5], p. 8).

Sous-graphes. « Un graphe Γ' = (V' ; E', N') est appelé sous-graphe de Γ si V' c V et E' ⊂ E » (ibid.^[5], 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.^[5], 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.^[5], p. 15).

Circuit. « Un circuit est un chemin simple dont les extrémités coïncident » (ibid.^[5], p. 15).