Une correspondance parfaite

En théorie des graphes , une correspondance parfaite dans un graphe est une correspondance qui couvre tous les sommets du graphe. Plus formellement, étant donné un graphe G = ( V , E ) , une correspondance parfaite dans G est un sous-ensemble M de l'ensemble d'arêtes E , tel que chaque sommet de l'ensemble de sommets V soit adjacent à exactement une arête de M .

Une correspondance parfaite est également appelée correspondance à 1 facteur ; voir Factorisation de graphes pour une explication de ce terme. Dans certaines publications, le terme correspondance complète est utilisé.

Toute correspondance parfaite est une correspondance à cardinalité maximale , mais l'inverse n'est pas vrai. Par exemple, considérons les graphiques suivants :

Dans le graphique (b), il y a une correspondance parfaite (de taille 3) puisque les 6 sommets sont appariés ; dans les graphiques (a) et (c), il y a une correspondance de cardinalité maximale (de taille 2) qui n'est pas parfaite, puisque certains sommets ne sont pas appariés.

Une correspondance parfaite est également une taille minimale de recouvrement des bords . S'il y a une correspondance parfaite, alors le numéro de correspondance et le numéro de recouvrement des bords sont tous deux égaux à | V | / 2 .

Une correspondance parfaite ne peut se produire que lorsque le graphe a un nombre pair de sommets. Une correspondance quasi parfaite est celle dans laquelle un seul sommet ne correspond pas. Cela ne peut se produire que lorsque le graphe a un nombre impair de sommets, et une telle correspondance doit être maximale. Dans la figure ci-dessus, la partie (c) montre une correspondance quasi parfaite. Si, pour chaque sommet d'un graphe, il existe une correspondance quasi parfaite qui omet uniquement ce sommet, le graphe est également appelé factor-critical .

Le théorème de mariage de Hall fournit une caractérisation des graphes bipartis qui ont une correspondance parfaite.

Le théorème de Tutte fournit une caractérisation des graphes arbitraires.

Une correspondance parfaite est un sous-graphe régulier couvrant 1 , également appelé 1-facteur . En général, un sous-graphe régulier couvrant k est un k -facteur .

Une caractérisation spectrale pour qu'un graphe ait une correspondance parfaite est donnée par Hassani Monfared et Mallik comme suit : Soit un graphe sur des sommets pairs et des nombres purement imaginaires distincts non nuls . Alors a une correspondance parfaite si et seulement s'il existe une matrice antisymétrique réelle avec un graphe et des valeurs propres . Notez que le graphe (simple) d'une matrice symétrique ou antisymétrique réelle d'ordre a des sommets et des arêtes donnés par les entrées non nulles hors diagonale de . $\backslash lambda\; \_\{2\}>\backslash ldots\; >\backslash lambda\; \_\{\backslash frac\; \{n\}\{2\}\}>0{\lambda }_1>{\lambda }_2>\dots >{\lambda }_{\frac{n}{2}}>0$\lambda _{2}>\ldots >\lambda _{\frac {n}{2}}>0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/526adf4348fde4e0ed6c4101af52e084cd56b9f5">

Déterminer si un graphe admet une correspondance parfaite peut être fait en temps polynomial , en utilisant n'importe quel algorithme permettant de trouver une correspondance de cardinalité maximale .

Cependant, compter le nombre de correspondances parfaites, même dans les graphes bipartis , est #P-complet . En effet, calculer la permanente d'une matrice arbitraire 0–1 (un autre problème #P-complet) revient au même que calculer le nombre de correspondances parfaites dans le graphe biparti ayant la matrice donnée comme matrice de biadjacence .

Un théorème remarquable de Kasteleyn stipule que le nombre de correspondances parfaites dans un graphe planaire peut être calculé exactement en temps polynomial via l' algorithme FKT .

Le nombre de correspondances parfaites dans un graphe complet K _n (avec n pair) est donné par la factorielle double :

Un graphe à arêtes colorées peut induire un nombre de colorations de sommets (pas nécessairement appropriées) égal au nombre de correspondances parfaites, car chaque sommet est couvert exactement une fois dans chaque correspondance. Cette propriété a été étudiée en physique quantique et en théorie de la complexité computationnelle .

Le polytope d'appariement parfait d'un graphe est un polytope dans R ^|E| dans lequel chaque coin est un vecteur d'incidence d'un appariement parfait.