Le mariage « classique » correspond à un couplage dans un graphe bipartite : la partition est, bien entendu, hommes vs femmes, et la présence d'une arête indique la « compatibilité », la possibilité d'un mariage.

Le problème de l'agence matrimoniale consiste donc à maximiser le nombre de mariages parmi ceux possibles ; plus généralement, l'on se donne une fonction de « bonheur » associant à chaque arête le bonheur qu'elle apporte, on peut vouloir maximiser le bonheur. Dans les deux cas, il existe des algorithmes assez simples et efficaces.

L'extension du mariage aux couples de même sexe (*) supprime la condition que le graphe doive être bipartite. Les structures obtenues restent toutefois simples.

Du point de vue de l'optimisation combinatoire, le problème devient plus compliqué et il faut recourir à l'algorithme d'Edmonds. Une question naturelle, dans le contexte de l'agence matrimoniale, est de savoir si l'on peut exploiter le fait que le graphe est très largement biparti, c'est-à-dire qu'il y a en proportion peu de personnes homosexuelles ou bisexuelles, et par ailleurs de degré limité (chaque personne a un entourage limité de personnes qu'elle connaît et avec qui elle pourrait vouloir contracter mariage). Mes connaissances en optimisation combinatoires sont trop limitées pour apporter une réponse.

Les opposants au mariage des couples de même sexe nous ont prévenu que cette évolution pourrait permettre, par la suite, d'autres extensions de la notion de mariage. Voyons donc celles-ci du point de vue de la théorie des graphes.

Une extension « naturelle » de la notion de couplage, c'est-à-dire de l'union de cliques disjointes de taille 2, est l'union de cliques disjointes de taille quelconque : autrement dit, un groupe de taille quelconque peut collectivement contracter mariage, mais une personne ne peut appartenir à plusieurs mariages.

Cette extension se heurte au problème suivant : la relation « aime » (ou du moins « apprécie » ou « peut supporter ») n'est pas transitive : les amis de mes amis ne sont pas forcément mes amis. Autrement dit, une personne pourrait vouloir contracter mariage avec deux autres, lesquelles en revanche ne voudraient pas contracter mariage ensemble.

On pourrait donc envisager une condition différente : chaque personne pourrait contracter un nombre limité de mariages simultanés (degré borné), mais sans condition de transitivité. Dans des graphes bipartites et avec une limitation du degré à deux, cela donnerait des chaînes « chabadabada » : Anne pourrait se marier avec Benoît, Benoît se marier également avec Cécile, Cécile également avec Denis... Mais que deviendrait alors la notion de vie commune ?

Nous pouvons toutefois proposer une extension différente : dans un graphe bipartite, avec limitation à 1 du degré pour une des catégories et à une borne d pour l'autre catégorie. Ceci correspond bien entendu à la polyandrie ou à la polygamie avec au maximum d conjoints. Ceci garantit que les foyers correspondent à au maximum d+1 adultes. Bien entendu, cette structure ne respecte pas la transitivité : Ahmed et Aïcha peuvent s'aimer, ainsi qu'Ahmed et Sophie, mais Sophie peut ne pas apprécier Aïcha.

Nous en concluons donc que l'extension du mariage au couple de même sexe ne représente qu'un changement modéré (du point de vue de la structure des graphes, bien entendu).

(*) Je ne désire pas ici rentrer dans les distinctions sexe vs genre.