Appariement à cardinalité maximaleModifié
Un problème fondamental en optimisation combinatoire est de trouver un appariement maximal. Ce problème a divers algorithmes pour différentes classes de graphes.
Dans un graphe biparti non pondéré, le problème d’optimisation est de trouver un appariement de cardinalité maximale. Le problème est résolu par l’algorithme de Hopcroft-Karp en temps O(√VE), et il existe des algorithmes randomisés plus efficaces, des algorithmes d’approximation, et des algorithmes pour des classes spéciales de graphes tels que les graphes planaires bipartites, comme décrit dans l’article principal.
Appariement à poids maximalModification
Dans un graphe biparti pondéré, le problème d’optimisation consiste à trouver un appariement à poids maximal ; un problème dual consiste à trouver un appariement à poids minimal. Ce problème est souvent appelé appariement biparti pondéré maximal, ou le problème d’affectation. L’algorithme de Hungarian résout le problème d’affectation et constitue l’un des débuts des algorithmes d’optimisation combinatoire. Il utilise une recherche modifiée du plus court chemin dans l’algorithme du chemin augmentant. Si l’algorithme de Bellman-Ford est utilisé pour cette étape, le temps d’exécution de l’algorithme de Hungarian devient O ( V 2 E ) {\displaystyle O(V^{2}E)}.
, ou le coût du bord peut être décalé avec un potentiel pour atteindre O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}.
temps d’exécution avec l’algorithme de Dijkstra et le tas de Fibonacci.
Dans un graphe pondéré non bipartite, le problème de l’appariement à poids maximum peut être résolu en temps O ( V 2 E ) {\displaystyle O(V^{2}E)}.
en utilisant l’algorithme blossom d’Edmonds.
Appariements maximauxModification
Un appariement maximal peut être trouvé avec un algorithme simple de type greedy. Un appariement maximal est aussi un appariement maximal, et donc il est possible de trouver un plus grand appariement maximal en temps polynomial. Cependant, on ne connaît pas d’algorithme en temps polynomial pour trouver un appariement maximal minimal, c’est-à-dire un appariement maximal qui contient le plus petit nombre possible d’arêtes.
Un appariement maximal avec k arêtes est un ensemble à dominance d’arêtes avec k arêtes. Inversement, si l’on nous donne un ensemble à dominance d’arêtes minimale avec k arêtes, nous pouvons construire un appariement maximal avec k arêtes en temps polynomial. Par conséquent, le problème de la recherche d’un appariement maximal minimum est essentiellement égal au problème de la recherche d’un ensemble à dominance d’arêtes minimum. Ces deux problèmes d’optimisation sont connus pour être NP-hard ; les versions de décision de ces problèmes sont des exemples classiques de problèmes NP-complets. Les deux problèmes peuvent être approximés au facteur 2 en temps polynomial : il suffit de trouver un appariement maximal arbitraire M.
Problèmes de comptageEdit
Le nombre d’appariements dans un graphe est connu comme l’indice de Hosoya du graphe. Il est #P-complet de calculer cette quantité, même pour les graphes bipartis. Il est également #P-complet de compter les appariements parfaits, même dans les graphes bipartis, parce que le calcul de la permanente d’une matrice 0-1 arbitraire (un autre problème #P-complet) est le même que le calcul du nombre d’appariements parfaits dans le graphe biparti ayant la matrice donnée comme sa matrice de biadjacence. Cependant, il existe un schéma d’approximation aléatoire en temps entièrement polynomial pour compter le nombre d’appariements bipartis. Un théorème remarquable de Kasteleyn affirme que le nombre d’appariements parfaits dans un graphe planaire peut être calculé exactement en temps polynomial via l’algorithme FKT.
Le nombre d’appariements parfaits dans un graphe complet Kn (avec n pair) est donné par la double factorielle (n – 1) ! !!. Les nombres d’appariements dans les graphes complets, sans contraindre les appariements à être parfaits, sont donnés par les numéros de téléphone.
Trouver toutes les arêtes maximalement apparentesModifier
Un des problèmes de base de la théorie de l’appariement est de trouver dans un graphe donné toutes les arêtes qui peuvent être étendues à un appariement maximal dans le graphe (de telles arêtes sont appelées arêtes maximalement appariables, ou arêtes permises). Les algorithmes pour ce problème incluent :
- Pour les graphes généraux, un algorithme déterministe en temps O ( V E ) {\displaystyle O(VE)}.
et un algorithme randomisé en temps O ~ ( V 2.376 ) {\displaystyle {\tilde {O}}(V^{2.376})}.
.
- Pour les graphes bipartis, si un seul appariement maximal est trouvé, un algorithme déterministe s’exécute en temps O ( V + E ) {\displaystyle O(V+E)}.
.
Appariement bipartite en ligneEdit
Le problème du développement d’un algorithme en ligne pour l’appariement a été considéré pour la première fois par Richard M. Karp, Umesh Vazirani, et Vijay Vazirani en 1990.
Dans le cadre en ligne, les nœuds d’un côté du graphe bipartite arrivent un par un et doivent soit être immédiatement appariés à l’autre côté du graphe, soit être écartés. Il s’agit d’une généralisation naturelle du problème du secrétaire, qui trouve des applications dans les enchères publicitaires en ligne. Le meilleur algorithme en ligne, pour le cas de maximisation non pondérée avec un modèle d’arrivée aléatoire, atteint un rapport compétitif de 0.696.