Domaine de la théorie des ensembles concernant les relations binaires d’un ensemble dénombrable avec lui-même.

Dans le produit cartésien E × E d’un ensemble dénombrable E, c’est-à-dire dans l’ensemble des couples ordonnés (x, y) où x et y appartiennent à l’ensemble E, un graphe est constitué d’une partie de ces couples possédant une certaine propriété c’est l’image d’une relation binaire dans un ensemble. Ainsi, dans l’ensemble E = {1, 2, 3, 4}, le sous-ensemble G de E × E tel que
G = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
est constitué des couples (x, y) de E × E tels que x divise y.

Modes de représentation

Un graphe peut être représenté par l’énumération des couples qui le constituent.

On peut aussi utiliser une représentation matricielle telle que le chiffre 1 à l’intersection de la ligne α et de la colonne β (α, β = 1, 2, 3, 4) indique que α divise β ; le chiffre 0 indique que α ne divise pas β (fig. 1).

On peut utiliser un diagramme cartésien où les couples ordonnés formant G sont représentés par des points (fig. 2).

On peut enfin utiliser une représentation sagittale où l’on joint par une flèche l’élément x de E avec l’élément y de E tels que le couple (x, y) possède la propriété étudiée : x divise y (fig. 3).

Mais on peut simplifier ce dernier diagramme de façon que les éléments de E ne figurent qu’une fois : les flèches ont la même signification que sur le diagramme précédent. Une telle figure est appelée un graphe orienté (fig. 4).

Graphe orienté

On peut noter un graphe par G = (E, U), E désignant l’ensemble de ses sommets et U l’ensemble de ses arcs ; on peut aussi noter G = (E, Γ), Γ désignant la relation définie dans E. Ainsi, pour la figure a,
U = {(1,2), (1,5), (2,2), ..., (6,6)}
ou bien
Γ (1) = {2,5}, Γ (2) = {2,3}, Γ (6) = {6}.

Fonction ordinale d’un graphe sans circuit. Application

Les huit sommets du graphe de la figure 5 peuvent représenter huit opérations intervenant, par exemple, dans une chaîne de fabrication. Les arcs indiquent l’ordre dans lequel on doit effectuer les opérations, représentées par l’origine et l’extrémité de ces arcs ; les opérations sont classées deux par deux. Le problème consiste à trouver au moins un ordre total pour construire une chaîne. On utilise alors une représentation matricielle du graphe sur laquelle on effectue certains calculs.

Les chiffres 1 inscrits dans la matrice (fig. 6) indiquent, comme le graphe de la figure 5, l’ordre des sommets pris deux à deux : 1, situé à l’intersection de la ligne α et de la colonne β, indique que le sommet α précède le sommet β. À droite de la double barre sont inscrites les coordonnées de vecteurs : V_A est la somme des vecteurs colonnes 1, 2, ..., 8 ; ses composantes s’obtiennent en sommant les 1, par ligne ; le chiffre 0, correspondant à la ligne 8, signifie que 8 n’est suivi d’aucun sommet, ou est de niveau 0. On calcule alors V_B = V_A – V₈, V_B étant le vecteur colonne 8 ; V_B montre un zéro sur la ligne 7 (en dehors de celui de la ligne 8, inutile et remplacé par une croix) ; ce qui signifie que 7 précède immédiatement 8, ou que 7 est de niveau 1. On recommence en formant V_C = V_B – V₇, ce qui fait apparaître deux zéros, sur les lignes 4 et 5, ce qui indique que 4 et 5 sont de niveau 2. On forme alors V_D = V_C – V₄ – V₅, etc. On arrive finalement à V_H = 0. D’où la suite des opérations. Au niveau 2, les opérations 4 et 5 sont à prendre dans un ordre quelconque ; en revanche, l’ordre est imposé pour toutes les autres opérations.

Le diagramme de la figure 7 définit la fonction ordinale du graphe initial.

Lorsque l’on part de graphes plus complexes, on aboutit à une fonction ordinale dont plusieurs niveaux peuvent comporter plus d’une opération.