Introduction

Mettre en relation des entités de toute nature est une opération commune et universelle. Le dé­ve­lop­pe­ment rapide des techniques (rebaptisées technologies par tropisme anglophile) n'a-t-il pas trans­for­mé notre planète en monde connecté ? Connecter, associer, relier, joindre, etc. sont des opérations incontournables, fon­da­men­ta­les et om­ni­pré­sen­tes en informatique et en ma­thé­ma­ti­ques.

Les relations permettent de modéliser des systèmes complexes, de résoudre des problèmes pratiques et de concevoir des algorithmes efficaces. Ce concept est au cœur même des bases de données relationnelles, dans lesquelles les données sont organisées en tables codant des relations entres ensembles de données. Les requêtes sont alors fondées sur des opérations permettant de combiner ces différentes relations. Les réseaux de télécommunication sont modélisés par des graphes dans lesquels les relations entre objets connectés jouent un rôle clef, les algorithmes de routage s'appuyent sur ces relations pour déterminer des chemins optimaux entre deux nœuds selon les débits et/ou la latence d'une connection, etc. Les fonctions constituent souvent des objets élémentaires des langages de programmation et sont à la base de l'apprentissage automatique, etc.

Encore une fois, nous allons commencer par exposer un problème ludique dont l'analyse et la résolution mettrons en évidence l'utilité, la versatilité et la force des concepts introduits dans ce chapitre :

Deux joueurs doivent à tour de rôle, retirer une, deux ou trois allumettes d'un tas jusqu'à ce qu'il soit vide. Le joueur qui ne peut plus retirer d'allumettes car le tas est vide a perdu.

Existe-t-il une stratégie gagnante à ce jeu ?

Relations, correspondances

Définitions

On généralise aisément la notion de graphe défini sur le produit cartésien de deux ensembles \(X\) et \(Y\) au produit cartésien d'un nombre arbitraire d'ensembles \(X_i\) :

On parle de relation unaire quand \(q=1\), de relation binaire quand \(q=2\) — auquel cas on retrouve naturellement le vocable usuel de graphe plutôt que \(2\)-graphe — et de relation ternaire quand \(q=3\), etc.

Exemples :

1. Les couples* au sens propre et au sens de la théorie des ensembles \((h,f)\in H\times F\) formés par un homme et une femme, définissent une re­la­tion binaire entre des éléments particuliers de l'ensemble \(H\) des hommes et de l'ensemble \(F\) des femmes.
2. Pour définir une relation de couple moins hétéronormée, il suffit de la considérer sur le produit cartésien \(E\times E\) d'un même ensemble \(E\) d'êtres humains.
3. Pour filer la métaphore familiale, la re­la­tion de pa­ren­ta­li­té est un exemple de re­la­tion ternaire entre hommes (ensemble \(H\)), femmes (ensemble \(F\)) et enfants (ensemble \(E\)), donc sur le produit cartésien \(H\times F\times E\), etc.
4. La pos­si­bi­li­té ou non d'as­sem­bler deux pièces d'un puzzle définit une re­la­tion binaire entre les pièces du puzzle sur le produit cartésien \(P \times P\) où \(P\) désigne l'ensemble des pièces du jeu.
5. Le jumelage entre communes françaises et étrangères constitue une re­la­tion binaire. Ainsi la ville de La Garde est jumelée avec la ville de Montesarchio en Italie ainsi que la ville de Spa en Belgique.

Parmi tous les types de relations, les relations binaires sont les plus utilisées et font l'objet d'une attention toute particulière. On note gé­né­ra­le­ment une re­la­tion binaire de manière infixe \(x{\rel}y\), plutôt que préfixe \(\rel(x,y)\), mimant ainsi plus fidèlement l'ex­pres­sion \(x\) est en re­la­tion avec \(y\). Une section spé­ci­fi­que de ce chapitre sera consacrée aux re­la­tions binaires entre éléments d'un même ensemble, i.e. \(Y=X\).

On représente une cor­res­pon­dan­ce à l'aide d'un diagramme sagittal * En forme de flèche. qui en fournit une in­ter­pré­ta­tion concrète. Les ensembles de départ \(X\) et d'arrivée \(Y\) sont matérialisés par des patates et chaque couple \({\color{#FF8}(x,y)}\) du graphe \({\color{#FF8}G}\) par une flèche reliant \(x\) à \(y\) : \[x\,{\color{#FF8}\rg}\,y.\] La flèche a pour premier mérite de mettre en évi­dence l'asymétrie de la construction puisque \((x,y)\not=(y,x).\)

Le diagramme sagittal ci-dessus illustre le jumelage de quelques villes. On constate que les villes de Mazaugues et Signes ne sont pas jumelées avec des villes étrangères et que les villes étran­gères de Liski et Vegen ne correspondent à aucun jumelage.

En inversant le sens des flèches du diagramme sagittal d'une cor­res­pon­dan­ce \(c=(X,G,Y)\) et en in­ver­sant les rôles des ensembles de départ \(X\) et d'arrivée \(Y\), on obtient une nouvelle cor­res­pon­dan­ce ap­pe­lée cor­res­pon­dan­ce réciproque de \(c\) et on la note \(c^{-1}\).

Images directes et réciproques

Si \(c=(X,G,Y)\) est une cor­res­pon­dan­ce, l'image directe par \(c\) d'une partie \(A\subseteq X\) de l'ensemble de départ, notée \(c(A)\), est le sous-ensemble des éléments de l'ensemble d'arrivée \(Y\) atteints par les éléments de \(A\). Ainsi pour la partie \(A:=\{La\ Garde,\ Nice\}\) de l'exemple introductif, on a

Réciproquement, l'image réciproque par \(c\) d'une partie \(B\subset Y\), notée \(c^{-1}(B)\), est l'image directe de \(B\) pour la cor­res­pon­dan­ce réciproque \(c^{-1}\). Toujours avec l'exemple introductif et en considérant \(B:=\{Spa,\ Kronstad\}\), on a

Plus formellement :

D'après cette définition, on a donc \(\text{Im}(c)=c(X)\). Notons qu'il est bien plus efficace de garder une image mentale d'une cor­res­pon­dan­ce sous forme de diagramme sagittal pour retrouver aisément toutes ces définitions que de les apprendre par cœur. Pour reprendre la métaphore musicale de l'introduction de ce cours, il est beaucoup plus simple de retenir et fredonner la mélodie d'une chanson pour en retrouver la partition plutôt que d'apprendre cette partition.

Composition des cor­res­pon­dan­ces

Le terme de cor­res­pon­dan­ce est familier du lecteur qui a voyagé et a dû changer de train durant son périple. Pour illustrer le propos, on modélise une fiche horaire entre deux villes par une cor­res­pon­dan­ce \(g=(X,{\color{#FF8}G},Y)\) où les ensembles \(X\) et \(Y\) contiennent respectivement les heures de départ et d'arrivée des différents trains reliant les deux villes \(X\) et \(Y\). Si l'on dispose d'une deuxième cor­res­pon­dan­ce \(h=(Y,{\color{#08F}H},Z)\) reliant les villes \(Y\) et \(Z\), on définit implicitement une fiche horaire entre les villes \(X\) et \(Z\) en passant par \(Y\) dont la modélisation mathématique n'est autre que la composition des cor­res­pon­dan­ces \(h\) et \(g\). Il suffit de rabouter les flèches qui arrivent en \(Y\) avec celles qui en partent et d'observer pour chaque élément de \(X\) quels sont les éléments correspondants dans \(Z\) :

Pour filer la métaphore ferrovaire, on observe dans le diagramme ci-dessus qu'il y a deux trains qui partent à \(4\)h de la ville \(X\) et permettent d'arriver à destination à la ville \(Z\) à \(7\)h ou \(10\)h en passant par la ville \(Y\). Il s'agit bien d'une cor­res­pon­dan­ce entre les villes \(X\) et \(Z.\) Il ne reste qu'à la définir for­mel­le­ment.

Avec l'exemple du diagramme sagittal ci-dessus, on a : \begin{align*} {\color{#08F}h}\circ {\color{#FF8}g}\,(\{3\})&=\{7\} & {\color{#08F}h}\circ {\color{#FF8}g}\,(\{7\})&=\{10\} & {\color{#08F}h}\circ {\color{#FF8}g}\,(\{4\})&=\{7,10\} & {\color{#08F}h}\circ {\color{#FF8}g}\,(\{8\})&=\varnothing\\ {\color{#08F}h}\circ {\color{#FF8}g}\,(\{5\})&=\{4\} & {\color{#08F}h}\circ {\color{#FF8}g}\,(\{0\})&=\varnothing & {\color{#08F}h}\circ {\color{#FF8}g}\,(\{1\})&=\{10\} \end{align*}

Fonctions, applications

Fonctions

Une fonction désigne un type de cor­res­pon­dan­ce particulière telle qu'il y a au plus une flèche qui part d'un élément \(x\in X\). C'est la transposition mathématique du terme largement employé dans le langage courant. Le montant à régler au parcmètre est fonction de la durée de stationnement, votre note au contrôle continu de l'ecue de Mathématiques pour l'Informatique est fonction du nombre de bonnes réponses, etc. Dans ce contexte, il ne peut y avoir qu'un seul montant à régler qui cor­res­pond avec la durée de stationnement et qu'une seule note associée au nombre de bonnes ré­pon­ses.

Ainsi, l'exemple de la figure 1 n'est pas une fonction car, entre autres, la ville de La Garde est en cor­res­pon­dan­ce avec deux villes étrangères. La condition à respecter pour qu'une cor­res­pon­dan­ce définisse une fonction s'exprime for­mel­le­ment de la manière suivante :

La façon d'exprimer mathématiquement au plus dans l'expression formelle \((\ref{eq:corrfon})\) ci-dessus peut sembler sur­pre­nante, mais elle répond bien à la contrainte : si deux couples avec la même première projection \(x\) appartiennent au graphe de la cor­res­pon­dance, alors leurs deuxièmes projections sont né­ces­sai­re­ment éga­les, autrement dit ces deux couples sont égaux.

Nous n'avons pas encore étudié formellement le cardinal \(\#X\) d'un ensemble fini \(X\), mais nous aurions pu définir alors une fonction à l'aide de la propriété suivante plus simple à in­ter­pré­ter : \[ \forall x\in X\ \ f(\{x\})\text{ est fini et}\ \#f(\{x\})\leqslant 1. \]

La définition d'une fonction via l'assertion \((\ref{eq:corrfon})\) est préférable car elle ne nécessite pas l'outillage des entiers naturels et de la cardinalité.

Dans le diagramme ci-dessous nous représentons la fonction qui associe le taux de tva à une activité ou une vente (si elle est assujettie à cette taxe).

Comme on peut le constater par l'absence d'une flèche, les soins d'une carrie dentaire ne sont pas assujetis à la tva (les actes médicaux ne sont pas soumis à cette taxe). On aurait pu rajouter un taux de \(0\%\) dans l'ensemble d'arrivée et inclure le couple \((\text{carrie},0\%)\) au graphe \( G\), mais il est plus cohérent de le modéliser sans cet arc puisque la tva ne s'applique pas aux actes médicaux. On note également que certains taux de tva ne correspondent à aucune activité/vente.

Soit \(x\in X\), d'après la caractérisation d'une fonction \((\ref{eq:corrfon})\), soit l'image directe \(f(\{x\})\) du singleton \(\{x\}\) est l'ensemble vide \(\varnothing\), soit c'est un singleton \(\{y\}\). Ceci justifie la définition suivante :

L'ensemble de définition de la fonction dont le diagramme sagittal est donné en figure 3 est :

Dans l'autre sens, si l'on se donne \(y\in Y\) et que la partie \(f^{-1}(\{y\})\) n'est pas vide, elle n'est pas nécessairement réduite à un unique élément, \(y\) peut donc posséder plusieurs antécédents.

La fonction \(f\) associée au diagramme de la figure 2 n'est pas définie en carrie. L'image de cinéma est \(2,1\%\), ce que l'on écrit \(f(cinema)=2,1\%\). Il est important de réaliser que la notation \(f(x)\) n'a de sens que si la fonction \(f\) est définie en \(x\), en revanche \(f(\{x\})\) a toujours un sens, c'est l'image directe du singleton \(\{x\}\) par la cor­res­pon­dan­ce \(f\) qui serait égale à l'ensemble vide \(\varnothing\) dans le cas où la fonction n'est pas définie en \(x\). Par définition un élément \(x\in X\) admet au plus une image par la fonction \(f\), mais un élément \(y\in Y\) peut avoir plusieurs antécédents. Par exemple smartphone et alcool sont deux antécédents de \(20\%\). Les valeurs \(15\%\), \(30\%\) et \(75\%\) n'admettent pas d'antécédents.

On utilise souvent l'écriture \(f:X\rightarrow Y\) pour définir une fonction \(f=(X,G,Y)\) même si son graphe \(G\) n'est pas spécifié. Cette omission est justifiée par le fait que \(f\) étant une fonction, elle est définie en tout élément \(x\) de son domaine de définition \({\mathscr D}(f)\) et son graphe \(G\) est par conséquent \[G:=\left\{(x,y)\in X\times Y\such (x\in {\mathscr D}(f))\wedge (y=f(x))\right\}.\]

Parfois l'image \(f(x)\) d'un élément \(x\) de \(X\) par une fonction \(f\) peut être calculée. En effet, nous verrons dans un prochain chapitre que les ensembles peu­vent être équipés de lois de composition internes, comme l'addition ou la multiplication sur \(\R\) par exemple. Dans ce cas, cela induit une vision dynamique de la fonction* l'utilisation mas­sive de flèches renforce éga­le­ment cet­te dynamique., comme s'il s'agissait d'une machine qui traitait la matière première \(\color{#FF8}x\) en entrée et qui fournissait le produit fini \(\color{#BBF}y\) en sortie :

Par exemple la fonction \(f\) qui calcule la circonférence d'un cercle en fonction de son rayon \(r\) est définie par \(f:\R\,\rg\,\R\), dont le graphe est l'ensemble des couples \((r,f(r))\) tels que \(f(r)=2\,\pi\,r\). Dans de tels cas, on complète souvent l'expression \(f:X\,\rg\,Y\) avec l'expression du calcul qu'elle effectue : \begin{align} \label{fonc:circonf} f:{\R}&\longrightarrow {\R}\\ \notag r&\longmapsto 2\pi r \end{align}

Il faut noter la différence entre la flèche qui relie les ensembles de départ et d'arrivée et celle munie d'un talon qui relie un élément de l'ensemble de départ à son image (quand elle existe) dans l'en­sem­ble d'arrivée.

Applications

La fonction définie en \((\ref{fonc:circonf})\) est bien une application, elle est en effet définie en tout nombre réel \(r\). En revanche, la fonction \begin{align} \label{fonc:inverse} f:{\R}&\longrightarrow {\R}\\ \notag x&\longmapsto 1/x \end{align} n'est pas une application puisqu'elle n'est pas définie en \(0\). Son domaine de définition est l'ensemble \({\mathscr D}(f)={\R}\setminus\{0\}\). Notons que si cette fonction n'est pas définie en \(0\), ce n'est pas pour un quelconque interdit, mais parce qu'elle est définie via son graphe qui est constitué des couples \((x,y)\in{\R}\times{\R}\) satisfaisant l'équation \(xy=1.\) Ce graphe ne contient donc aucun couple \((x,y)\) tel que \(x=0\) ou \(y=0\).

On dit que deux applications \(f:X\,\rg\,Y\) et \(g:X'\rg Y'\) coïncident sur une partie \(A\subseteq X\cap X'\) si elles sont égales en tout élément de \(A\) : \begin{equation} \forall x\in A\quad f(x)=g(x). \end{equation}

Soit \(f:X\,\rg\,Y\) une application et \(A\) une partie de \(X\). L'application de \(A\rightarrow Y\) qui coïncide avec \(f\) sur \(A\) est ap­pe­lée restriction de \(f\) à \(A\) et notée \(f{/}_A\).

Il est très facile d'obtenir une application à partir d'une fonction qui n'est pas définie en tout point de son ensemble de départ \(X\). Il suffit de remplacer \(X\) par le domaine de définition \({\mathscr D}(f)\) de cette fonc­tion, autrement dit de considérer sa restriction \(f/_{{\mathscr D}(f)}\). Dans le cas de la fonction de la figure 2, il suffit d'éliminer carrie de l'en­sem­ble \(X\), i.e. le nouvel ensemble de départ est \(X':={\mathscr D}(f)\) :

Quant à la fonction \(f\) définie en \((\ref{fonc:inverse})\), il suffit d'éliminer \(0\) pour en faire une application, il s'agit de la fonction \(g:{\R}^*\rg{\R}\) définie par \(g(x):=\frac{1}{x}.\) Attention, \(g\not=f\). En effet, une fonction est avant tout une cor­res­pon­dan­ce, c'est-à-dire un triplet, or deux triplets sont égaux si et seulement si leurs trois projections sont égales respectivement. Autrement dit deux cor­res­pon­dan­ces sont égales si et seu­le­ment si elles ont même en­sem­ble de départ, même ensemble d'arrivée et même graphe

La confusion entre fonction et application dans les textes mathématiques est courante et distinguer les deux peut sembler superfétatoire. En effet, quel est l'intérêt de considérer comme ensemble de départ un autre ensemble que l'ensemble de définition d'une fonction puisqu'elle n'est pas définie ailleurs ? Le premier est d'attirer l'attention sur cet ensemble de définition qu'il ne faut surtout pas négliger, et l'autre est que les questions qui vont suivre sur les propriétés remarquables des applications se justifient naturellement en considérant la correspondance réciproque qui peut être ou non une fonction, une application. Quoi qu'il en soit, il est très facile de transformer une fonction en application, il suffit de considérer que son ensemble de départ est son ensemble de définition.

Si la cor­res­pon­dan­ce réciproque \(f^{-1}\) d'une fonction \(f\) est elle-même une fonction, elle est appelée fonction réciproque. La section suivante est consacrée à l'étude des cor­res­pon­dan­ces ré­ci­pro­ques et de leur statut.

Injections, surjections, bijections

Quand on se donne une cor­res­pon­dan­ce, il est naturel de s'intéresser à la cor­res­pon­dan­ce réciproque (voir exercice), ne serait-ce que parce que sa construction est extrêmement simple, il suffit d'inverser le sens des flèches et d'échanger le rôle de l'ensemble de départ et de l'ensemble d'arrivée. L'étude de la réversibilité du processus est intéressante, en particulier quand il s'agit d'une fonction calculable.

On réalise immédiatement en construisant la cor­res­pon­dan­ce réciproque de l'application de ce dia­gram­me que celle-ci n'est plus une application, (ni \(30\%\), ni \(75\%\) n'ont d'image), ni mê­me une fonction (deux flè­ches partent de la valeur \(20\%\)). Quelles sont les conditions que doit satisfaire une application pour que sa cor­res­pon­dan­ce réciproque soit une fonction, ou mieux une application ?

Pour que la cor­res­pon­dan­ce réciproque soit une fonction, il ne faut pas que deux éléments distincts \(x_1\) et \(x_2\) de l'ensemble de départ aient la même image \(y\) (comme smart­phone et alcool qui ont la même tva à \(20\%\)), sans quoi la cor­res­pon­dan­ce inverse aurait deux flèches partant de \(y\), l'une vers \(x_1\) et l'autre vers \(x_2\) ce qui est interdit pour une fonction.

Injections

La contraposée de la proposition logique \((\ref{eq:injection})\) est très souvent utilisée pour démontrer qu'une ap­pli­ca­tion est injective, à savoir \begin{equation} \forall (x_1,x_2)\in X\times X\quad (f(x_1)=f(x_2))\Rightarrow (x_1=x_2). \end{equation} Il est en effet plus aisé de faire des déductions en partant d'une égalité que de la négation d'une égalité.

Indépendamment de l'étude des cor­res­pon­dan­ces réciproques, l'in­jec­ti­vi­té est une propriété fort in­té­res­sante et souvent nécessaire pour modéliser certaines contraintes. Pour établir une communication té­lé­pho­ni­que, on cherche a priori à exclure la possiblité que deux numéros de téléphone soient as­so­ciés à la même carte sim* Subscriber Identity Mo­du­le, la table de cor­res­pon­dan­ce dont disposent les opérateurs n'est ni plus ni moins qu'une application in­jec­ti­ve. De la même manière, deux numéros de sécurité sociale dis­tincts sont associés à des in­di­vi­dus dis­tinc­ts, etc.

Soit \(X\) et \(Y\) deux ensembles tels que \(X\subseteq Y\). L'application \(f:X\,\rg\,Y\) définie par \(f(x):=x\) est une injection appelée injection canonique. Si \(Y=X\), cette application est appelée application iden­ti­té de \(X\) et on la note \(\text{Id}_X\).

La cor­res­pon­dan­ce réciproque \(f^{-1}\) d'une injection \(f\) est donc une fonction. Si elle est définie en \(y\in Y\), autrement dit s'il existe \(x\in X\) tel que \(f^{-1}(\{y\})=\{x\}\), alors \(x\) est l'image de \(y\) par \(f^{-1}\) et on la note \(f^{-1}(y)\).

Si l'on veut que cette fonction réciproque soit également une application, il faut que tous les éléments de l'ensemble d'arrivée soient atteints par une flèche de manière à ce que tous les éléments de l'ensemble \(Y\) aient une image pour la cor­res­pon­dan­ce réciproque.

Surjections

Cette propriété peut être satisfaite sans que l'application soit injective, tout élément de l'ensemble d'arrivée peut donc avoir plusieurs antécédents. C'est le cas de l'application à gauche dans la figure ci-dessous, elle est surjective mais pas injective. Celle de droite n'est ni injective ni surjective.

Bijections

On aurait tout aussi bien pu donner la définition suivante : une application \(f\) est bijective si et seu­le­ment si sa cor­res­pon­dan­ce réciproque \(f^{-1}\) est une application.

Une bijection associe de manière unique chaque élément d'un ensemble à un autre et ré­ci­pro­que­ment. Si les ensembles de départ et d'arrivée sont par exemple constitués respectivement par des étu­diant⋅e⋅s de sciences et de lettres, disposer d'une bi­jec­tion revient à créer des couples monogames où chacun⋅e a exactement un⋅e petit⋅e ami⋅e :

Les trois notions, injection, surjection et bijection sont absolument fondamentales en mathématiques et en informatique. Ces objets servent non seulement à la modélisation mais également à compter. L'existence d'une solution à une équation du type \(f(x)=y\) d'inconnue \(x\) est liée à la surjectivité de \(f\) et l'unicité d'une solution à l'injectivité de \(f\). Avant même d'avoir défini ce qu'est un ensemble fini* la compréhension in­tui­ti­ve du concept est suf­fi­san­te ici., il semble évident que si les ensembles de départ et d'arrivée sont finis et en bijection, ils ont le même nombre d'éléments. Il n'est pas rare que l'on dénombre les éléments d'un ensemble en établissant une bijection avec un autre en­sem­ble dont on connaît le cardinal. Dans le même ordre d'idées et intuitivement, disposer d'une injection (resp. une surjection) entre un ensemble \(X\) et un ensemble \(Y\) impose que l'ensemble \(Y\) est plus grand que \(X\) (resp. plus petit que \(X\)).

Un premier résultat important sur les bijections est lié à la composition des ap­pli­ca­tions.

Soit \(f:X\,\rg\,X\) une application. On peut donc composer \(f\) avec elle même puisque les ensembles de départ et d'arrivée sont confondus. Par convention, on note \(f^n:=f\circ f^{n-1}\) avec \(f^0:=\text{Id}_X\). L'ap­pli­ca­tion \(f^n\) est ap­pe­lée \(n\)-ème itérée de \(f\).

Une application bijective \(f:X\,\rg\,X\) telle que \(f^2=\text{Id}_X\) est appelée in­vo­lu­tion ou dite involutive, autrement dit elle est sa propre bijection réciproque. Par exemple l'ap­pli­ca­tion \(f:\R^*\rg\R^*\) définie par \(x\mapsto\frac{1}{x}\).

Une application \(f:X\,\rg\,X\) telle que \(f^2=f\) est dite idem­po­ten­te. Par exemple la valeur absolue dans \(\R\), en effet \(|\!|x|\!|=|x|\).

Revenons aux images directes et réciproques dans le cas où la cor­res­pon­dan­ce est une fonction \(f:X\,\rg\,Y\). Alors l'égalité \((\ref{eq:imdir})\) devient :

On rappelle que \({\mathscr P}(X)\) désigne l'ensemble des parties d'un ensemble \(X\). Soit \({\color{#F88}A:=\{g,b,e\}}\in{\mathscr P}(X)\) et \({\color{#88F}B:=\{0,7,8\}}\in{\mathscr P}(Y)\) pour l'application \(f:X\,\rg\,Y\) définie par le diagramme sagittal ci-dessous. On a \(f({\color{#F88}A})=\{5,1\}\) et \(f^{-1}({\color{#88F}B})=\{a,c,d\}\).

De la même ma­niè­re que l'on transforme facilement une fonction \(f:X\,\rg\,Y\) en application en remplaçant son en­semb­le de départ \(X\) par le domaine de définition \({\mathscr D}(f)\), on transforme une application quelconque en surjection en remplaçant son ensemble d'arrivée \(Y\) par son image \(\text{Im}(f)\).

Dans cette définition, rien ne distingue une famille d'une application, si l'on excepte l'usage des lettres \(I\) et \(X\) pour dé­si­gner respectivement l'ensemble de départ et d'arrivée en lieu et place des usuels \(X\) et \(Y\). Il s'agit ici de formaliser l'écriture mathématique indicielle \(x_i\) pour désigner un élément d'un ensemble \(X\). For­mel­lement on définit la famille \(x:I\,\rg\,X\) et on écrit simp­le­ment \(x_i\) au lieu de \(x(i)\).

Nous n'avons pas encore étudié l'ensemble des entiers naturels \(\N\), mais il est plus pertinent de ne pas différer les définitions suivantes :

Ce qui importe dans ces trois notions est l'ordre dans lequel les éléments de ces trois types de familles sont rangés. C'est explicite pour une séquence ou une suite et pour un système dont l'ensemble d'indexation est totalement ordonné. C'est implicite pour un système dont l'ensemble d'indexation n'est pas ordonné, puisque étant fini, il est en bijection avec \(\{i\in\N\mid 1\leqslant i\leqslant n\}\), ses éléments peuvent donc être ordonnés via cette bijection.

Exemple : Considérons le système \((x_i)_{i\in I}\) muni de l'ensemble d'indexation \(I=\{\textsf{a},\textsf{b},\textsf{c},\ldots,\textsf{z}\}\) équipé de l'ordre alphabétique. On peut donc écrire \(x_{\textsf{a}}\), \(x_{\textsf{b}}\), etc.

Nous avons vu au chapitre dédié à la logique des prédicats et la théorie zf, comment était construit le produit cartésien de deux ensembles \(X\) et \(Y\) et comment on pouvait le généraliser au produit cartésien de \(q > 2\) ensembles \(X_1,X_2,\ldots,X_q\). On peut désormais procéder autrement avec une construction à la fois plus simple et plus générale. C'est tout simplement le produit fini de la séquence \((X_i)_{i\in I}\) d'ensemble d'indexation \(I:=\{1,2,\ldots,q\}\).

Opérations sur les ensembles

Réunion, intersection.

Soit \((X_i)_{i\in I}\) une famille d'ensembles. On montre que les deux ensembles suivant existent : \begin{align*} \bigcup_{i\in I}X_i:=&\{x\mid\exists i\in I\ x\in X_i\} &\bigcap_{i\in I}X_i:=&\{x\mid\forall i\in I\ x\in X_i\}. \end{align*} Il s'agit respectivement de la réunion de la famille \((X_i)_{i\in I}\) et de l'intersection de la famille \((X_i)_{i\in I}\).

Réindexation.

Si l'on se donne une application surjective \(\varphi:J\rg I\), on peut faire une réindexation de la famille \((X_i)_{i\in I},\) i.e.

Autres opérations.

Soit \((X_i)_{i\in I}\) et \((Y_j)_{j\in J}\) deux familles d'ensembles. On a

Soit \((X_i)_{i\in I}\) et \((Y_j)_{j\in I}\) deux familles d'ensembles de même ensemble d'indexation \(I\) telles que \(\forall i\in I\ \ X_i\subseteq Y_i\). Alors

Soit \((X_i)_{i\in I}\) une famille de parties d'un ensemble \(X\). Alors

Images et images réciproques d'une réunion et d'une intersection.

Soit \(f:X\,\rg\,Y\) une application, \((X_i)_{i\in I}\) une famille de parties de l'ensemble \(X\) et \((Y_i)_{i\in I}\) une famille de parties de l'ensemble \(Y\). On a

L'image réciproque d'une réunion (ou d'une intersection) est donc toujours la réunion (ou l'intersection) des images réciproques. En revanche, si l'image d'une réunion est bien la réunion des images, l'image d'une intersection n'est pas l'intersection des images.

Partition d'un ensemble

Étudier un ensemble \(X\) en le découpant en parties cohérentes est très utile. On peut par exemple partitionner la population mondiale selon les pays, partitionner les instruments de musique selon qu'ils sont à vent, à corde ou à percussion, etc. Les trois propriétés ma­thé­ma­ti­ques exigées pour ce découpage sont très naturelles : les parties ne doivent pas être vides, deux parties différentes ne doivent pas contenir d'éléments communs et la réunion de toutes ces parties est l'ensemble \(X\) tout entier :

Une famille d'ensembles \((X_i)_{i\in I}\) dont la réunion contient un ensemble \(X\) s'appelle un recouvrement de \(X\) (à la manière des tuiles d'un toit qui le recouvrent et se chevauchent par endroit). Une partition est donc un cas particulier de recouvrement.

Re­la­tions binaires sur un ensemble

Définition et propriétés remarquables

Comme nous l'avions annoncé dans la première section, une re­la­tion binaire sur un ensemble \(X\) est tout simplement une re­la­tion binaire qui met en re­la­tion des éléments d'un même ensemble \(X\). Ce modèle est si versatile et fécond, qu'il a engendré à lui seul une théorie, la théorie des graphes. Cette théorie connaît des développements permanents, elle est enseignée dans toutes les formations d'in­for­ma­ti­que et à tous niveaux. C'est l'un des modèles les plus utisés dans cette discipline scien­ti­fi­que, il est donc très important de le comprendre et le maîtriser. Son rôle universel justifie d'en donner une définition spécifique, même s'il s'agit d'un cas particulier de la définition d'une re­la­tion \(q\)-aire.

On rappelle que l'on note souvent une relation binaire de manière infixe, i.e. \(x{\rel}y\) au lieu de \(\rel(x,y)\). Les re­la­tions binaires ne sont que des cas particuliers de cor­res­pon­dan­ces, on les représente également par leurs diagrammes sagittaux, en se contentant cette fois des flèches qui relient les éléments entre eux, autrement dit du graphe. Le schéma de la patate pour représenter l'ensemble de référence \(X\) devient superflu. Un couple \((x,x)\) dans ce diagramme est alors représenté par une boucle.

Par exemple :

Comme nous l'avions déjà noté dans la section consacrée aux relations \(q\)-aires générales, une relation définit un graphe et réciproquement, ce sont deux façons équivalentes de considérer le même concept mathématique. Dans le cadre de la théorie des graphes, on préfère définir la relation a posteriori et mettre l'accent sur le graphe, d'où la définition suivante employée dans ce cadre.

Il faut noter dans cette définition que \(G\) ne désigne plus l'ensemble des couples définis sur un produit cartésien, rôle dévolu à \(U\), mais le couple constitué de l'ensemble des sommets \(X\) et de l'ensemble des arcs \(U\). Le graphe est dit fini ou infini suivant la cardinalité de l'ensemble de ses sommets.

La relation \(\rel\) associée au graphe \(G\) au sens de cette définition est alors caractérisée par la pro­po­si­tion suivante : \begin{equation} \forall (x,y)\in X^2\quad x{\rel}y\ssi (x,y)\in U. \end{equation} Les re­la­tions binaires, et par conséquent les graphes au sens de la définition ci-dessus, peuvent posséder des propriétés re­mar­qua­bles.

On parlera donc de relation réflexive ou de graphe réflexif, de relation symétrique ou de graphe symétrique, etc.

L'asymétrie est plus contraignante que l'antisymétrie, elle est parfois qualifiée d'antisymétrie forte (par opposition l'antisymétrie est alors qualifiée d'antisymétrie faible). Dans un graphe asymétrique, il ne peut y avoir de boucle \((x,x)\) alors que c'est possible dans un graphe antisymétrique.

Il est courant quand on dispose d'une relation binaire \(\rel\) sur un ensemble de considérer sa fermeture transitive. L'idée est simple et naturelle, l'expression les amis de mes amis sont mes amis l'illustre parfaitement. On construit à partir d'une relation \(\rel\) sa fermeture transitive \(\overline{\rel}\) en rajoutant* La construction ef­fec­ti­ve de cette nou­vel­le re­la­tion né­ces­si­te d'éla­bo­rer un al­go­ri­thme. au graphe de la relation \(\rel\) les couples \((x,y)\) nécessaires pour que cette nouvelle relation soit transitive.

La définition suivante nous sera utile dans les chapitres à venir, lorsque nous munirons les ensembles de nouveaux outils. Elle dit simplement qu'une application est compatible avec une relation binaire si deux éléments en relation ont la même image (Le prix \(f(x)\) payé par des personnes \(x\) du même âge est le même).

Re­la­tions d'équivalence

La notion de re­la­tion d'équivalence est déjà parfaitement intégrée par tous et en dehors de tout contexte mathématique. Dans les phrases Mettez un chapeau, , les termes tournevis, chapeau et homme ne font pas référence à un tournevis, un chapeau ou une voiture en particulier, mais à une classe dont les éléments ont des caractéristiques communes. Le formalisme mathématique tente de saisir l'es­sen­ce de ce concept :

On peut définir aisément une re­la­tion sur l'ensemble des voitures, on dira par exemple que deux voitures sont en re­la­tion s'il s'agit du même modèle. La re­la­tion est évidemment réflexive, une voiture est bien du même modèle qu'elle même. La re­la­tion est également symétrique, si la voiture \(x\) est du même modèle que la voiture \(y\), la voiture \(y\) est bien du même modèle que \(x\). Elle est aussi transitive, puisque si la voiture \(x\) est du même modèle que la voiture \(y\), qui elle même est du même modèle que la voiture \(z\), alors la voiture \(x\) est du même modèle que la voiture \(z\). Le lecteur perspicace aura deviné qu'en définissant une re­la­tion binaire à partir de caractéristiques communes entre objets, elle sera toujours une re­la­tion d'équivalence.

L'application \(\varphi:X\,\rg\,X/{\rel}\) définie par \(\varphi(x):=\overline{x}\) qui à un élément \(x\) de \(X\) associe sa classe d'équi­va­len­ce \(\overline{x}\) est évidemment surjective puisque l'ensemble d'arrivée est constitué de ses images, elle est appelée surjection canonique.

Que doit satisfaire une application \(f:X\,\rg\,Y\) pour être compatible avec une relation d'équivalence \(\rel\) (deux éléments de \(X\) en relation doivent posséder la même image) ?

Malgré les apparences, ce théorème n'a rien de bien compliqué. On a fait des paquets de tous les individus qui ont la même image par \(f\), et l'application \(g\) n'est rien d'autre qu'une version de \(f\) définie sur ces paquets.

Dans la section consacrée aux fonctions et aux applications, nous avons étudié comment transformer une fonction \(f:X\,\rg\,Y\) quelconque en application, il suffit de remplacer l'ensemble de départ par le domaine de définition \({\mathscr D}(f)\) de la fonction, puis comment transformer cette application en surjection, il suffit de remplacer l'ensemble d'arrivée par l'image \(f(X)\) de \(f\). Mais comment transformer cette dernière application en injection afin d'obtenir une bijection ?

L'étude que nous venons de mener nous donne la solution, il suffit de regrouper tous les éléments qui ont la même image par \(f\), autrement dit de remplacer les éléments de l'ensemble de départ par leur classe d'équivalence pour la relation d'équivalence \({\color{#88F}x{\rel}y}\iff f(x)=f(y)\) (par construction \(f\) est com­pa­tib­le avec \(\rel\)). Le diagramme sagittal ci-dessous explicite cette construction. Les éléments \(h\) et \(i\) sont écartés de l'ensemble de départ \(X\) pour faire de \(f\) une fonction et \(3\) et \(6\) sont écartés de l'ensemble d'arrivée \(Y\) pour faire de \(f\) une surjection. On obtient les \(3\) classes d'équivalence \(\color{#88F}\{b,g,e\}\), \(\color{#88F}\{c\}\) et \(\color{#88F}\{a,d\}.\)

L'application bijective ainsi construite est notée \({\color{#FF8}\overline{f}}\) et appelée application décomposition canonique · de \(f\). Les ap­pli­ca­tions qui relient les quatre ensembles \(X\), \(Y\), \(\color{#88F}{X/\rel}\) et \(f(X)\) sont souvent représentées dans un dia­gram­me appelé diagramme commutatif :

Dans un diagramme commutatif, plusieurs chemins peuvent relier deux ensembles et les différentes compositions d'applications suivant ces chemins différents sont égales. Ici deux chemins relient \(X\) à \(Y\), le premier est constitué d'une seule flèche, celle étiquetée \(f\), et l'autre est constitué de trois flèches étiquetées \(\varphi\), \(\color{#FF8}\overline{f}\) et \(j\) l'injection canonique. On a donc \(f=j\circ{\color{#FF8}\overline{f}}\circ \varphi.\)

Relations d'ordre

Trier des objets est une opération très courante, même pour un être humain, mais de toutes les opérations réalisées par les ordinateurs, c'est celle qui occupe de loin la plus grande part du temps cpu mondial. Trier des objets n'est possible que si l'on dispose d'un critère pour les comparer.

Si \(\preccurlyeq\) est une relation d'ordre, la relation \(\succcurlyeq\) définie par \(x\succcurlyeq y\iff y\preccurlyeq x\) est appelée ordre opposé de \(\preccurlyeq\), et si \(x\succcurlyeq y\) on dit que \(x\) est supérieur ou égal à \(y\). La re­la­tion binaire \(\prec\) définie sur \(X\) par \(x\prec y\) si et seulement si \(x\preccurlyeq y\) et \(x\not=y\) est appelée ordre strict associé à \(\preccurlyeq\). On emploie également la terminologie plus petit que/plus grand que pour inférieur/supérieur.

L'ordre strict associé à une relation d'ordre est une relation binaire antiréflexive par construction, ce n'est plus une re­la­tion d'ordre. La terminologie mathématique s'avère ici particulièrement ma­la­droi­te.

De par l'importance de certaines relations d'ordre dans le discours mathématiques, et de l'existence de multiples relations d'ordres définies et utilisées simultanément sur un même ensemble, on leur attribue souvent un symbole et une terminologie spécifiques afin d'éviter toute confusion.

Exemples :

1. La plus connue est sans conteste la relation d'or­dre naturel notée spécifiquement*C'est précisément par analogie avec l'ordre naturel que le symbole générique \(\preccurlyeq \) a été choisi pour représenter une relation d'ordre en général. \(\leq\) ou \(\leqslant\) et définie sur l'ensemble \({\N}\) des entiers naturels. C'est une relation d'ordre total dont l'ordre strict associé est noté \(\lt\). De par son importance, l'ordre naturel sera étudié plus en détail au chapitre suivant.
2. On vérifie aisément que la relation d'inclusion \(\subseteq\) définie sur l'ensemble \({\mathscr P}(X)\) des parties d'un ensemble \(X\) est une re­la­tion d'ordre partiel dont l'ordre strict associé est noté \(\subset\). La terminologie héritée de l'ordre naturel ne prête pas à confusion ici puisqu'il est commun de dire que l'ensemble \(A\) est plus petit que l'en­sem­ble \(B\) plutôt que \(A\) est inclus ou égal à \(B\).
3. La relation préfixe \(\preceq\) définie sur l'ensemble des mots sur un alphabet fixé est une relation d'ordre : informellement, un mot \(u\) est un préfixe de \(v\) s'il est au début de \(v,\) par exemple lit est un préfixe de littéral et tout mot est préfixe de lui-même.

Il faut prendre garde au vocabulaire générique quand on manipule des relations d'ordre différentes définies sur un même ensemble. La relation de divisibilité dans \(\N\) est une relation d'ordre partielle (cf. exercice). Ainsi comme \(4\mid 0\), on peut tout à fait affirmer que \(4\) est plus petit que \(0\) pour la relation de divisibilité \(\mid\), ce qui peut dérouter car l'acception de ces termes est généralement associée à la relation d'ordre naturel \(\leqslant\). On utilisera donc préférablement le vocabulaire idoine pour chaque relation, ici \(4\) divise \(0\).

Soit \(a\) et \(b\) deux éléments d'un ensemble totalement ordonné \((X,\preccurlyeq)\) tels que \(a\preccurlyeq b\). On définit les intervalles suivants :

Ces intervalles sont dits respectivement fermé, semi-ouvert à gauche, semi-ouvert à droite et ouvert. On définit également les demi-droites :

La relation d'inclusion définie sur des ensembles est une relation d'ordre partiel. Considérons par exemple l'ensemble \(X:=\{a,b,c\}\). L'ensemble de ses parties est

On ne peut pas comparer les parties \(\{a,b\}\) et \(\{c\}\) avec la relation d'inclusion par exemple, aucun des deux n'est inclus dans l'autre. Quand on dispose d'une relation d'ordre sur un ensemble fini comme ici, on représente le graphe de la relation à l'aide d'un dia­gram­me appelé diagramme de Hasse^# Helmut Hasse est un mathématicien allemand. de la relation :

Le diagramme de Hasse d'une relation d'ordre est construit de bas en haut. Si l'on a \(x\preccurlyeq y\), on dessine un arc reliant le sommet \(x\) vers le sommet \(y\) qui est placé au dessus de \(x\). On ne représente aucune des relations que l'on peut déduire par transitivité. Dans l'exemple ci-dessus, l'ensemble vide \(\varnothing\) est inclus dans toutes les parties de \(X\), mais on ne trace que les trois arcs le reliant aux trois singletons, puisque les autres arcs peuvent être déduits par transitivité. Ce diagramme permet dans une certaine mesure de visualiser la relation étudiée et mettre en évidence quelques éléments re­mar­qua­bles que nous allons étudier dans la suite.

Cette représentation n'a d'intérêt que pour une relation d'ordre partielle. En effet si la relation d'or­dre est totale, le diagramme sera constitué de tronçons verticaux reliant les différents éléments de l'ensemble \(X\). Par exemple pour l'ensemble \(X:=\{0,1,2,3\}\) muni de l'ordre naturel :

Quand on dispose d'une relation d'ordre \(\preccurlyeq\) sur un ensemble \(X\), certains éléments de l'ensemble peu­vent posséder des propriétés remarquables.

Une partie \(A\) à la fois minorée et majorée, est appelée partie bornée. Il n'existe pas nécessairement de minorant ou de majorant à une partie d'un ensemble, par exemple la demi-droite \([0,\rightarrow[\) de \(\R\) n'admet pas de majorant, et \(\Z\) n'admet pas de minorant.

Dans l'exemple de la figure 13, le plus petit élément et le plus grand élément de \({\mathscr P}(X)\) pour l'inc­lu­sion existent, il s'agit respectivement de \(\text{min}\ {\mathscr P}(X)=\varnothing\) et \(\text{max}\ {\mathscr P}(X)=X\). L'ensemble des en­tiers naturels \({\N}\) admet un plus petit élément pour l'ordre naturel, il s'agit de \(0\). En revanche \({\N}\) n'admet pas de plus grand élément par essence, c'est l'une des trois propriétés qui le caractérisent comme nous le verrons au chapitre suivant.

La borne inférieure de \(A\) appartient à \(A\) si et seu­le­ment si \(A\) admet un plus petit élément et dans ce cas \(\text{inf}\;A = \text{min}\;A\). De même, la borne supérieure de \(A\) appartient à \(A\) si et seu­le­ment si \(A\) admet un plus grand élément et dans ce cas \(\text{sup}\;A = \text{max}\;A\).

Nous avons vu qu'un ensemble ordonné n'admet pas néessairement de plus petit ou de plus grand élément, a fortiori si la relation d'ordre est partielle puisque tous les éléments ne sont pas comparables. Cependant, on peut se demander s'il existe des éléments qui soient plus petits ou plus grands que tous ceux avec qui la comparaison est possible ?

Il existe des moyens conventionnels de définir de nouvelles relations d'ordre à partir d'une ou plu­sieurs relations d'ordre prédéfinies. Quand on se donne une relation d'ordre \(\preccurlyeq\) sur un ensemble \(X\), la relation d'ordre notée \(\succcurlyeq\) définie par \(x\succcurlyeq y\iff y\preccurlyeq x\) est appelée l'ordre opposé de l'ordre \(\preccurlyeq\). Quand on restreint une relation d'ordre définie sur un ensemble \(X\) à une partie \(Y\subseteq X\), la relation ainsi crée s'appelle l'ordre induit par l'ordre \(\preccurlyeq\) sur \(Y\). Si l'on se donne une famille \((X_i,\preccurlyeq_i)_{i\in I}\) d'ensembles ordonnés, la relation \(\preccurlyeq\) définie sur l'ensemble produit \(X:=\prod_{i\in I}X_i\) par

est une relation d'ordre appelée l'ordre produit des relations \(\preccurlyeq_i\). Les relations d'ordre \(\preccurlyeq_i\) peuvent être totales sans que l'ordre produit \(\preccurlyeq\) le soit. Considérons par exemple l'ordre produit sur l'ensemble des couples d'entiers naturels munis chacun de l'ordre naturel : \[(x,y)\preccurlyeq (x',y')\iff (x\leqslant x')\wedge (y\leqslant y').\] Les couples \((1,2)\) et \((2,1)\) ne sont pas comparables. Pour obtenir une relation d'ordre total sur ce produit cartésien il faut fournir un peu plus d'efforts.

Limitons nous au cas fini où l'ensemble d'indexation est \(I:=\llbracket 1,\,n\rrbracket\) avec \(n\) un entier naturel non-nul. On définit une relation binaire \(\preccurlyeq\) entre deux \(n\)-uplets \((x_i)_{i\in I}\) et \((y_i)_{i\in I}\) par \((x_i)_{i\in I}\preccurlyeq (y_i)_{i\in I}\) si et seulement s'il existe un rang \(k\in\llbracket 1,\,n-1\rrbracket\) tel que leurs \(i\)-èmes projections coïncident pour tout \(i\in \llbracket 1,\,k-1\rrbracket\) et que \(x_k\prec_k y_k\) ou que leurs \(i\)-èmes projections sont toutes égales sauf pour \(i=n\) où \(x_n\preccurlyeq_n y_n\). Il s'agit d'une relation d'ordre total appelée ordre lexicographique.

Malgré une définition alambiquée, cette relation est bien connue du lecteur. Si les en­sem­bles \(X_i\) désignent tous le même alphabet latin muni de l'ordre alphabétique, il s'agit de l'ordre du dictionnaire. C'est également l'ordre qui est utilisé pour ranger les nombres réels quand ils sont re­pré­sen­tés sous forme décimale.

Si l'on remplace dans la définition les relations d'ordre \(\preccurlyeq_X\) et \(\preccurlyeq_Y\) par leurs ordres stricts \(\prec_X\) et \(\prec_Y\) on parle d'application strictement croissante et strictement décroissante. Une application qui est croissante ou décroissante (resp. strictement croissante ou décroissante) est dite application monotone (resp. application strictement monotone).

Re­la­tions de précédence

Dans les systèmes multiprocesseurs multiprogrammés, on modélise le fonctionnement des processus par un ensemble \(\mathscr T\) de tâches à réaliser. Ces tâches sont re­pré­sen­tées par des couples \(T=(d,f)\) dont la première projection \(d\) est l'instant où la tâche \(T\) débute son exécution et la seconde projection \(f\) est l'instant où elle finit son exécution. Certaines tâches ne peuvent débuter leur exécution qu'une fois que d'autres tâches ont fini la leur. Ces différentes contraintes temporelles sont modélisées par une relation binaire \(\propto\) définie sur l'ensemble \(\mathscr T\) des tâches à réaliser. Si \(T\) et \(T'\) sont deux tâches, on interprète \(T\propto T'\) par la tâche \(T\) termine son exécution avant que la tâche \(T'=(d',f')\) ne débute la sienne, i.e.

On dit alors que la tâche \(T\) précède la tâche \(T'\) ou que la tâche \(T'\) succède la tâche \(T\).

Si deux tâches \(T\) et \(T'\) sont telles que l'exécution de l'une ne nécessite pas l'exécution de l'autre au préalable, i.e. telles que \(\neg (T\propto T')\wedge\neg(T'\propto T)\), on dit que ce sont des tâches parallèles et on écrit \(T\;\Vert\;T',\) sinon elles sont en série. La relation \(\propto\) est antiréflexive, en effet une tâche \(T\) ne peut pas terminer son exécution avant même d'avoir com­men­cé, elle est antisymétrique et bien sûr transitive.

Le graphe d'une relation de précédence est représenté par un diagramme qui omet tous les arcs que l'on peut déduire par transitivité. Deux questions classiques sont étudiées dans les cours de systèmes d'exploitation des formations en informatique :

1. Trouver un ordonnancement séquentiel de l'ensemble des tâches compatible avec la relation de précédence ;
2. Trouver un ordonnancement parallèle de l'ensemble des tâches compatible avec la relation de précédence.

Le premier cas correspond à la situation où les différentes tâches sont exécutées par un unique pro­ces­seur, le deuxième cas si le système alloue plusieurs processeurs pour exécuter des tâches en pa­ral­lè­le. Considérons par exemple la relation de précédence définie sur l'ensemble \({\mathscr T}:=\{T_1,T_2,\ldots,T_9\}\) par la fermeture transitive \(\overline{G}\) du graphe

Son diagramme de précédence est représenté ci-dessous. Seuls les numéros des tâches sont indiqués :

Pour organiser un séquencement de ces \(9\) tâches, que ce soit de manière séquentielle ou parallèle, il faut bien sûr commencer par des tâches \(T\) qui n'ont aucun arc incident vers le sommet correspondant dans le diagramme, c'est-à-dire telles qu'il n'existe aucune tâche \(T'\) telle que \(T'\propto T\). Il n'y a que les tâches \(\color{#88F}T_7\) et \(\color{#88F}T_8\) qui ne sont précédées par aucune tâche.

Un ordonnancement séquentiel possible (il n'y pas nécessairement unicité) comme solution du pre­mier problème est :

Nous verrons au chapitre consacré à la combinatoire qu'une telle solution constitue une permutation de l'ensemble \(\{1,2,\ldots,9\}\). L'ordonnancement parallèle solution du second problème est :

Ces solutions sont faciles à trouver à la main sur une instance aussi petite que celle de cet exemple, mais dans toute leur généralité ces problèmes nécessitent d'élaborer des algorithmes pour les résoudre et on souhaite qu'ils soient efficaces.

D'autres questions sont soulevées par les relations de précédences. Il ne faut pas que dans un graphe de précédence apparaisse un circuit, c'est-à-dire une séquence \(T_{i_1},T_{i_2},\ldots,T_{i_k}\) de tâches telle que

Plus simplement, la condition \((\ref{circuit})\) exprime qu'il ne faut jamais être en mesure de partir d'une tâche \(T\) du graphe et d'y revenir en suivant des flèches. La raison est simple, si un tel circuit existe, alors par transitivité de la relation \(\propto\), on a \(T\propto T\) ce qui contredit l'antiréflexivité.

Comment savoir s'il existe des circuits dans un graphe ? Est-on capable de les trouver rapidement ? C'est ce genre de questions qui sont étudiées en théorie des graphes et on en saisit bien l'utilité.

Résolution du problème introductif

Modélisation avec les graphes

La modélisation de ce problème, appelé Jeu de Nim, se fait dans le cadre de la théorie des graphes.

Notons \(n\) le nombre d'allumettes sur le tas au début de la partie et considérons le graphe \(G:=(X,U)\) d'ensemble de sommets \(X:=\ab{0}{n}\) et d'arcs \[U:=\{(k,\ell)\in X\times X\such 1\leqslant k-\ell\leqslant 3\}.\] Autrement dit, \(X\) contient toutes les valeurs possibles du nombre d'allumettes sur le tas entre le début et la fin d'une partie et chaque arc de \(U\) code un coup possible :

Chaque sommet \(k\) de ce graphe codant une position du jeu, le joueur dans cette position doit choisir parmi les \(3\) coups possibles \((k,k+1)\), \((k,k+2)\) et \((k,k+3)\), celui ou ceux qui peuvent l'amener à une victoire, si un tel coup existe.

Il n'est pas difficile de constater que si un joueur \(A\) est en position \(\color{lightgreen}3\), \(\color{lightgreen}2\) ou \(\color{lightgreen}1\), il peut toujours amener le joueur adverse \(B\) dans la position perdante \(\color{red}0\) en retirant \(3\), \(2\) ou \(1\) allumette respectivement et si le joueur \(B\) est en position \(4\), aucun des trois coups qu'il peut jouer ne lui permet d'éviter d'être perdant. On peut réitérer le raisonnement de proche en proche.

Cette analyse empirique montre qu'un joueur dans l'une des positions en vert peut toujours amener le joueur adverse sur l'une des positions perdantes en rouge. Par conséquent, le joueur qui connaît cette stratégie et qui commence cette partie est sûr de gagner, sinon il faut qu'il compte sur l'ignorance du joueur adverse pour pouvoir se retrouver sur une position gagnante avant que toutes les allumettes soient retirées.

Le graphe \(G=(X,U)\) définit indirectement la correspondance \((X,U,X)\) que nous noterons encore \(G\) par abus de langage. Observons les propriétés de la partie \(A:=\color{red}\{0,4,8\}\). Aucune flèche ne permet de relier deux sommets de \(A\), on dit dans ce cas que \(A\) est indépendante du graphe \(G\) : \begin{equation} \forall (x,y)\in A^2\ \ (x,y)\not\in U. \end{equation} D'autre part, tout sommet hors de \(A\) est relié à un sommet de \(A\), et on dit alors que \(A\) est une absorbante du graphe \(G\) : \begin{equation} \forall y\not\in A\ \exists x\in A\ \ (y,x)\in U \end{equation} Une partie \(A\) de \(X\) à la fois indépendante et absorbante est appelée noyau du graphe \(G\)

Notons qu'un graphe n'admet pas nécessairement de noyau, mais s'il en admet un celui-ci est unique, ce qui permet de parler du noyau d'un graphe. Le cas échéant, on dispose d'une stratégie générale pour gagner à tous les jeux similaires. Par exemple, deux personnes veulent cueillir des fleurs à tour de rôle sur une rangée de \(n\) fleurs, mais ils ne peuvent qu'en couper une à chaque fois et il est interdit de cueillir une fleur à côté d'une fleur qui a été coupée. La cueillette s'arrête quand il n'est plus possible de cueillir de fleur. Quel stratégie faut-il adopter pour être le dernier à cueillir une fleur ? Autre exemple : deux joueurs sont faces à plusieurs tas de pièces et peuvent retirer chacun leur tour un nombre arbitraire de pièces mais d'un seul tas, qui peut en revanche être différent à chaque tour de jeu. Comment éviter d'être celui qui ne pourra plus retirer de pièce ?

La question qui se pose à présent est de déterminer comment calculer le noyau d'un tel graphe autrement que de manière empirique ?

Fonctions de Grundy

Le mathématicien britannique Patrick Grundy s'est intéressé à ce type de problèmes et a développé l'outillage nécessaire en théorie des graphes pour les analyser et identifier les positions gagnantes et perdantes. Dans le graphe modélisant les différentes configurations du jeu des allumettes et les transitions qui les relient, on constate aisément que l'on peut regrouper les sommets suivant leur statut dans le déroulement du jeu : les sommets \(0\), \(4\) et \(8\) qui sont les positions perdantes, les sommets \(1\), \(5\) et \(9\) qui permettent de les atteindre en retirant \(1\) allumette, les sommets \(2\), \(6\) en retirant \(2\) allumettes et les sommets \(3\) et \(7\) en retirant \(3\) allumettes. Il y a donc \(4\) groupes de positions différents dans le graphe.

On comprend aisément l'intérêt d'une telle fonction, les positions gagantes/perdantes sont déterminées par la valeur de leur fonction de Grundy. Reste à déterminer les conditions qu'un graphe doit satisfaire pour qu'il admette une fonction de Grundy et, le cas échéant, comment construire cette fonction.

On rappelle que l'on peut découper une chaîne de caractères chaine suivant un séparateur sep (une chaîne de caractère également, par défaut un espace) grâce à la méthode split(sep) qui renvoie la liste des sous-chaînes séparées par la chaîne sep. Ici on obtient la liste constitué des deux termes du couple en utilisant le symbole > comme séparateur :

 couple = chaine.rstrip().split(">")

def Formater(X):
    return str(X).replace("'",'')

def Afficher(names, c):
    print(names[0],":")
    for i in range(3):
        print("\t"+names[i+1]+" = ",Formater(c[i]))
    print()

Compléments hors séance