Les fractions rationnelles indexées par les graphes

Posets, diagrammes de Hasse et extensions linéaires

Ici nous détaillons les différentes notations se référant aux posets. Un ensemble partiellement ordonné (poset) P est un ensemble muni d’une opération binaire ≤ vérifiant : – pour tout élément x de P, x ≤ x (réflexivité), – si x ≤ y et y ≤ x alors x = y (antisymétrie), – si x ≤ y et y ≤ z, alors x ≤ z (transitivité). On appelle support d’un poset, l’ensemble des éléments du poset. De même, on appelle relation d’ordre tout couple (x,y) de P tel que x ≤ y. Dans un poset, on dit que deux éléments x et y sont comparables si et seulement si x ≤ y ou y ≤ x. Par exemple, 1 et 2 sont comparables dans le poset {1, 2, 3, 4} muni de la relation d’ordre {(1, 3),(1, 2),(3, 4),(2, 4),(1, 4)}. Toutefois, 2 et 3 ne sont pas comparables. Généralement, on représente les posets à l’aide de graphes orientés.

Les élements des posets sont alors les sommets des graphes orientés et les relations d’ordre sont leurs arêtes. Dans un souci de clarté, nous dessinons les posets de sorte que si x ≤ y alors x est à gauche de y dans le dessin. Ainsi, le poset de l’exemple précédent est dessiné dans la figure 2.1.

Posets, diagrammes de Hasse et extensions linéaires

On dit que y couvre x si x ≤ y et s’il n’existe pas d’élément z qui vérifie x ≤ z ≤ y avec z 6= x,y. On note la relation de couverture . Par exemple, dans le poset de la figure 2.1, 1 3 mais 1 6 4. Un ordre total est un poset dont tous les éléments sont comparables deux à deux. Un ordre total peut être représenté par un mot sans répétition de lettres.

En effet, les lettres de l’alphabet sont les éléments de P et, si a ≤ b alors a est à gauche de b dans le mot. Soient P1 et P2 deux posets ayant le même support et des relations d’ordre distinctes. On dit que P1 est compatible avec P2 si les relations d’ordre de P2 sont incluses dans celles de P1. Une extension linéaire d’un ensemble partiellement ordonné P est un ordre total compatible avec P. On note L(P) l’ensemble des extensions linéaires de P. Par exemple, les extensions linéaires du poset {1, 2, 3, 4, 5} muni de la relation d’ordre {(1, 3),(2, 3),(3, 4),(3, 5),(1, 4),(2, 5)} ( voir figure 2.2 ) sont les mots 12345, 21345, 12354, 21354.

Les graphes

Le livre [12] présente de nombreux types de graphes. Notre étude concerne uniquement les graphes orientés finis. Un graphe orienté est constitué par : – un ensemble fini de sommets VG, – un ensemble fini d’arêtes EG vérifiant EG ⊂ VG × VG. Si e est une arête de EG, on note par α(e) la première composante de e (appelée origine de e) et ω(e) la seconde composante (appelée fin de e). Dans cette définition, chaque arête possède une orientation. Soit e = (v1,v2) une arête de VG × VG. On note par e la paire (v2,v1). Il est pratique de définir quatre notions de parcours du graphe. Plus précisément, soit G un graphe et E un ensemble d’arêtes.

Une chaîne est une suite d’arêtes c = (e1,… ,ek) de G telle que ω(e1) = α(e2), ω(e2) = α(e3), … et ω(ek−1) = α(ek). Un circuit est une chaîne (e1,… ,ek) de G telle que ω(ek) = α(e1). Un chemin est une séquence (e1,… ,eh) d’éléments de E ∪ E telle que ω(e1) = α(e2), ω(e2) = α(e3), … et ω(ek−1) = α(ek). Un cycle C est un chemin tel que ω(ek) = α(e1). Si C est un cycle, alors nous notons par HE(C) l’ensemble C ∩ E. Cycles et circuits (resp. chemins et chaînes) constituent deux objets différents. Dans un circuit, toutes les arêtes se trouvent dans le graphe de départ ce qui n’est pas le cas pour un cycle quelconque.

Dans cette situation, un circuit est un cycle qui vérifie la propriété HE(C) = C. On appelle source (resp. puits) tout sommet du graphe qui n’est la fin (resp. le début ) d’aucune arête. Un sommet extrémal est une source ou un puits. L’ensemble des sommets extrémaux se note Extr(G). De même, un sommet intérieur est un sommet qui n’est ni une source, ni un puits du graphe. L’ensemble des sommets intérieurs du graphe est noté In(G).

Pour faciliter la lecture des figures, les sommets d’une arête e sont dessinés de façon à ce que α(e) soit toujours à gauche de ω(e). Une telle construction n’est pas possible si le graphe possède un circuit. Cependant, nous nous intéressons principalement aux graphes sans circuit. Un exemple de graphe est dessiné dans la figure 2.4. Dans le graphe de gauche, les arêtes qui ne sont pas en pointillés forment une chaîne c. Dans le graphe de droite, elles forment un cycle. HE(C) contient alors 3 arêtes : (1, 6), (6, 8) et (5, 7).