Gallaï Tibor

Entre 1912 et 1992, le mathématicien hongrois Tibor Gallai étudie des réseaux faits de points reliés par des arêtes. Dans l'étoile à quatre sommets utilisée ici, le centre touche les trois feuilles. On peut choisir les trois feuilles sans en prendre deux qui soient reliées : elles forment un ensemble stable.

À l'inverse, choisir le seul centre suffit pour toucher toutes les arêtes. Gallai a mis en relation ces deux manières complémentaires de sélectionner des sommets. Ses travaux portent aussi sur les couplages, qui sélectionnent des arêtes sans extrémité commune.

Tibor Gallai, né Tibor Grünwald en 1912 et mort en 1992, est un mathématicien hongrois dont les recherches se concentrent sur la combinatoire, particulièrement la théorie des graphes. Un graphe fini se décrit par des sommets et des arêtes reliant certaines paires de sommets. Un ensemble stable est un ensemble de sommets dont aucun couple n'est relié par une arête. Le nombre de stabilité, noté α(G), est la plus grande taille d'un tel ensemble dans le graphe G.

Une couverture par sommets est un ensemble de sommets qui contient au moins une extrémité de chaque arête. Son nombre minimal, noté τ(G), est le nombre de couverture par sommets. Pour tout graphe fini G ayant un ensemble de sommets V, la relation de Gallai s'écrit :

Cette égalité vient d'une complémentarité exacte : le complémentaire d'un ensemble stable est une couverture par sommets, et le complémentaire d'une couverture par sommets est stable. Gallai travaille également sur les recouvrements et les couplages. Un couplage est un ensemble d'arêtes sans extrémité commune. En lien avec les travaux de Jack Edmonds, le théorème de Gallai-Edmonds décrit la structure des graphes au regard de leurs couplages maximum. Gallai collabore étroitement avec Paul Erdős autour de problèmes combinatoires et de conjectures ouvertes.

Considérons l'étoile G représentée par quatre sommets : un centre c et trois feuilles a, b et d. Ses seules arêtes relient c à chacune des feuilles. Le schéma matérialise les deux sélections complémentaires qui vont être comparées.

Données.
Sommets : V = {a, b, c, d}.
Arêtes : {a–c, b–c, c–d}.
Nombre total de sommets : |V| = 4.

Étape 1. Les trois feuilles a, b et d ne sont reliées entre elles par aucune arête. Elles forment donc un ensemble stable de taille 3. On ne peut pas ajouter c, car c est relié à chacune d'elles : α(G) = 3.

Étape 2. Le seul sommet c touche les trois arêtes. L'ensemble {c} est donc une couverture par sommets. Une couverture ne peut pas être vide puisque le graphe possède des arêtes : τ(G) = 1.

Étape 3. La relation de Gallai donne $\alpha (G)+\tau (G)=3+1=4=\mathrm{\mid }V\mathrm{\mid }\backslash alpha(G)+\backslash tau(G)=3+1=4=|V|$. Le résultat est exact.

Contrôle. Le complémentaire de l'ensemble stable {a, b, d} est précisément {c}, la couverture minimale trouvée. Réciproquement, retirer {c} de V redonne les trois feuilles indépendantes.

Pour vérifier une relation attribuée à Gallai, on commence par identifier les objets concernés. La relation α(G) + τ(G) = |V| compare deux sélections de sommets ; elle ne demande pas de choisir des arêtes.

Pour trouver une couverture par sommets à partir d'un ensemble stable, on prend tous les sommets qui ne figurent pas dans cet ensemble. Si le stable est maximum, la couverture complémentaire est minimale. Cette conversion est préférable à une nouvelle recherche indépendante lorsqu'un des deux ensembles est déjà connu.

Pour étudier des arêtes deux à deux disjointes, on emploie plutôt la notion de couplage. Dans l'étoile de l'exemple, deux arêtes quelconques partagent le centre c ; un couplage ne peut donc en retenir qu'une.

Ensemble stable et couplage. Un ensemble stable sélectionne des sommets sans arête entre eux ; un couplage sélectionne des arêtes sans extrémité commune. Dans l'étoile, {a, b, d} est un stable de taille 3, tandis qu'un couplage contient au plus une arête.

Couverture par sommets et recouvrement d'arêtes. Une couverture par sommets choisit des sommets qui touchent toutes les arêtes. Un recouvrement d'arêtes choisit des arêtes afin que chaque sommet soit incident à l'une d'elles. Le type d'éléments sélectionnés permet de les distinguer.

Couplage maximal et couplage maximum. Un couplage maximal ne peut plus recevoir d'arête, tandis qu'un couplage maximum possède la plus grande taille possible. Tout maximum est maximal, mais le critère « impossible à agrandir » ne garantit pas à lui seul la plus grande taille.

La relation porte sur des optimums. Additionner la taille de n'importe quel ensemble stable à celle de n'importe quelle couverture ne donne pas nécessairement |V|. Il faut employer un stable maximum et une couverture minimale, ou une paire complémentaire qui réalise ces optimums.

Un sommet isolé sépare deux situations. Il n'est incident à aucune arête : une couverture par sommets n'a pas besoin de le contenir, tandis qu'un stable peut l'accueillir. En revanche, aucun recouvrement d'arêtes ne peut couvrir ce sommet. Il faut alors signaler que ce recouvrement n'existe pas ou retirer d'abord les sommets isolés du problème considéré.

« Maximal » ne signifie pas « maximum ». Le premier mot décrit l'impossibilité d'ajouter localement un élément ; le second désigne la plus grande cardinalité globale. Pour appliquer un résultat sur les couplages maximaux au sens de taille maximale, il faut vérifier la convention du texte consulté.

Une attribution générale ne remplace pas l'énoncé précis. L'expression « théorème de Gallai » peut désigner plusieurs résultats. Il faut regarder si le texte traite de stabilité, de couverture, de recouvrement ou de couplage avant d'appliquer une formule.

La relation entre stabilité et couverture illustre une méthode féconde en théorie des graphes : remplacer une sélection par son complémentaire. Cette opération transforme une condition locale — aucune arête à l'intérieur d'un stable — en une condition globale — chaque arête touchée par la couverture complémentaire.

Le théorème de Gallai-Edmonds prolonge cette recherche sur un autre objet, le couplage. Il ne fournit pas seulement une valeur : il décrit la structure d'un graphe au regard de ses couplages maximum et relie ainsi optimisation et organisation du graphe.

Le portrait d'Erdös Paul situe le collaborateur avec lequel Gallai partage son intérêt pour les problèmes combinatoires élégants et les conjectures ouvertes.